COMP9020 Assignment 4 2024 Term 1 Due: Thursday, 18th April, 18:00 (AEST)
Submission is through inspera. Your assignment will be automatically submitted at the above due date. If you manually submit before this time, you can reopen your submission and continue until the deadline.
If you need to make a submission after the deadline, please use this link to request an extension:
Answers are expected to be provided either:
• In the text box provided using plain text, including unicode characters and/or the built-in formula editor (diagrams can be drawn using the built-in drawing tool); or
• as a pdf (e.g. using LATEX) – each question should be submitted on its own pdf, with at most one pdf per question.
Handwritten solutions will be accepted if unavoidable, but we don’t recommend this approach as the assessments are designed to familiarise you with typesetting mathematics in preparation for the final exam and for future courses.
Discussion of assignment material with others is permitted, but the work submitted must be your own in line with the University’s plagiarism policy.
Problem 1 (12 marks) Proof assistant
Prove, using the laws of boolean algebras (and any results proven in lectures), the following identities hold ∀x, y ∈ T.
Partial marks are available for showing these identities in a particular boolean algebra
a) (x∧1′)∨(x′∧1)=x′ b) (x∧y)∨x=x
c) x∨(x′∧y)=x∨y Problem 2
Proof assistant
a) ¬(p→q)≡(¬p→¬q)
b) ((p∧q)→r)≡(p→(q→r))
c) ((p∨(q∨r))∧(r∨p))≡((p∧q)∨(r∨p))
4 marks
4 marks
(12 marks)
4 marks
4 marks
4 marks
4 marks
Problem 3 (18 marks) a) Remember our graph from Assignment 2:
You were asked to find the number of 3-colourings of this graph. Give a formula that will return the number of k-colourings.
b) An integer is called snakelike if its decimal representation a1 a2 a3 · · · ak satisfies ai < ai+1 if i is odd and ai > ai+1 if i is even. How many snakelike integers between 1000 and 9999 have four distinct digits?
c) Six people of different heights are getting in line to buy donuts. Compute the number of ways they can arrange themselves in line such that no three consecutive people are in increasing order of height, from front to back
Problem 4 (17 marks) Recall from Assignment 1 the neighbourhood of eight houses:
As before, each house wants to set up its own wi-fi network, but the wireless networks of neighbouring houses – that is, houses that are either next to each other (ignoring trees) or over the road from one another (directly opposite) – can interfere, and must therefore be on different channels. Houses that are sufficiently far away may use the same wi-fi channel. Again we would like to solve the problem of finding the minimum number of channels needed, but this time we will solve it using techniques from logic and from probability. Rather than directly asking for the minimum number of channels required, we ask if it is possible to solve it with just 2 channels. So suppose each wi-fi network can either be on channel hi or on channel lo. Is it possible to assign channels to networks so that there is no interference?
• Your first goal is to formulate this problem as a problem in propositional logic. In particular:
a) Define your propositional variables
b) Define any propositional formulas that are appropriate and indicate what propositions they represent.
c) Indicate how you would solve the problem (or show that it cannot be done) using proposi- tional logic. It is sufficient to explain the method, you do not need to provide a solution.
d) Explain how to modify your answer(s) to (a) and (b) if the goal was to see if it is possible to solve with 3 channels rather than 2.
6 marks
6 marks
6 marks
4 marks
3 marks
2 marks
4 marks
• Now we will consider solving this problem with a random approach.
e) Suppose each house chooses, uniformly at random, one of the two network channels. What is the probability that there will be no interference?
Let T(n) denote the number of binary trees with n nodes. For example T(3) = 5 because there are five binary trees with three nodes:
a) Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equa- tion for T(n).
A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is a fully-internal node) or two empty children (i.e. is a leaf).
b) Using observations from Assignment 2, or otherwise, explain why a full binary tree must have an odd number of nodes.
c) Let B(n) denote the number of full binary trees with n nodes. Derive an expression for B(n), involving T(n′) where n′ ≤ n. Hint: Relate the internal nodes of a full binary tree to T(n).
A well-formed formula is in Negated normal form if it consists of just ∧, ∨, and literals (i.e. propo- sitional variables or negations of propositional variables). For example, (p ∨ (¬q ∧ ¬r)) is in negated normal form; but (p ∨ ¬(q ∨ r)) is not.
Let F(n) denote the number of well-formed, negated normal form formulas1 there are that use precisely n propositional variables exactly one time each. For example, there are 16 formulas in negated normal form that use two variables:
(p ∧ q) (p ∨ q) (q ∧ p) (q ∨ p) (¬p ∧ q) (¬p ∨ q) (¬q ∧ p) (¬q ∨ p) (p∧¬q) (p∨¬q) (q∧¬p) (q∨¬p) (¬p∧¬q) (¬p∨¬q) (¬q∧¬p) (¬q∨¬p)
Some values for F are: F(1) = 2, F(2) = 16, and F(4) = 15360.
d) Using your answer for part (c), give an expression for F(n).
Remark
The T(n) are known as the Catalan numbers. As this question demonstrates they are very useful for counting various tree-like structures.
Problem 5
Recall from Assignment 3 the definition of a binary tree data structure: either an empty tree, or a node with two children that are trees.
1Note: we do not assume ∧ and ∨ are associative
(16 marks)
4 marks
6 marks
2 marks
4 marks
4 marks
Advice on how to do the assignment
Collaboration is encouraged, but all submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
• Assignments are to be submitted in inspera.
• When giving answers to questions, we always would like you to prove/explain/motivate your answers. You are being assessed on your understanding and ability.
• Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for your worst answer, as this indicates how well you understood the question.
• Some of the questions are very easy (with the help of external resources). You may make use of external material provided it is properly referenced2 – however, answers that depend too heavily on external resources may not receive full marks if you have not adequately demonstrated ability/understanding.
• Questions have been given an indicative difficulty level:
Credit Distinction High distinction
This should be taken as a guide only. Partial marks are available in all questions, and achievable
by students of all abilities.
Pass
2Proper referencing means sufficient information for a marker to access the material. Results from the lectures or textbook can be used without proof, but should still be referenced.
