Home Page > > Details

COMP9020 Assignment 2 2019 Term 3

Due: Sunday, 3rd November, 23:59

Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should

be typed, not handwritten. Use of LATEX is encouraged, but not required.

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 (20 marks)

Recall the relation composition operator ; defined as:

R1; R2 = {(a, c) : there is a b with (a, b) ∈ R1 and (b, c) ∈ R2}

For any set S, and any binary relations R1, R2, R3 ⊆ S × S, prove or give a counterexample to disprove the

following:

(a) (R1; R2); R3 = R1;(R2; R3) (4 marks)

(b) I; R1 = R1; I = R1 where I = {(x, x) : x ∈ S} (4 marks)

(c) (R1; R2)← = R←

(4 marks)

(d) (R1 ∪ R2); R3 = (R1; R3) ∪ (R2; R3) (4 marks)

(e) R1;(R2 ∩ R3) = (R1; R2) ∩ (R1; R3) (4 marks)

Problem 2 (30 marks)

Let R ⊆ S × S be any binary relation on a set S. Consider the sequence of relations

as follows:

(a) Prove that if there is an i such that R

for all j ≥ i. (4 marks)

(b) Prove that if there is an i such that R

for all k ≥ 0. (4 marks)

(c) Let P(n) be the proposition that for all m ∈ N: Rn+m. Prove that P(n) holds for all n ∈ N.

(8 marks)

(d) If |S| = k, explain why R

k = Rk+1. (Hint: Show that if (a, b) ∈ Rk+1

then (a, b) ∈ Ri

for some i < k + 1.)

(4 marks)

(e) If |S| = k, show that Rk

is transitive. (4 marks)

(f) If |S| = k, show that (R ∪ R←)k

is an equivalence relation. (6 marks)1

Problem 3 (26 marks)

A binary tree is a data structure where each node is linked to at most two successor nodes:

If we allow empty binary trees (trees with no nodes), then we can simplify the description by saying a

node has exactly two children which are binary trees.

(a) Give a recursive definition of the binary tree data structure. Hint: review the recursive definition of a

Linked List (6 marks)

A leaf in a binary tree is a node that has no successors (i.e. it has two empty trees as children). A fullyinternal

node in a binary tree is a node that has two successors. The example above has 3 leaves and 2

fully-internal nodes.

(b) Based on your recursive definition above, define the function count(T) that counts the number of nodes

in a binary tree T. (4 marks)

(c) Based on your recursive definition above, define the function leaves(T) that counts the number of

leaves in a binary tree T. (4 marks)

(d) Based on your recursive definition above, define the function internal(T) that counts the number of

fully-internal nodes in a binary tree T. Hint: it is acceptable to define an empty tree as having −1 fullyinternal

nodes. (4

marks)

(e) If T is a binary tree, let P(T) be the proposition that leaves(T) = 1 + internal(T). Prove that P(T) holds

for all binary trees T. (8 marks)

Problem 4 (24 marks)

Four wifi networks, Alpha, Bravo, Charlie and Delta, all exist within close proximity to one another as

shown below.

Alpha Bravo Charlie Delta

Networks connected with an edge in the diagram above can interfere with each other. To avoid interference

networks can operate on one of two channels, hi and lo. Networks operating on different channels will not

interfere; and neither will networks that are not connected with an edge.

Our goal is to determine (algorithmically) whether there is an assignment of channels to networks so

that there is no interference. To do this we will transform the problem into a problem of determining if a

propositional formula can be satisfied.

(a) Carefully defining the propositional variables you are using, (4 marks)

write propositional formulas for each of the following requirements:

(i) ϕ1: Alpha uses channel hi or channel lo; and so does Bravo, Charlie and Delta. (4 marks)

(ii) ϕ2: Alpha does not use both channel hi and lo; and the same for Bravo, Charlie and Delta.(4 marks)

(iii) ϕ3: Alpha and Bravo do not use the same channel; and the same applies for all other pairs of

networks connected with an edge. (4 marks)

(b) (i) Show that ϕ1 ∧ ϕ2 ∧ ϕ3 is satisfiable; so the requirements can all be met. Note that it is sufficient

to give a satisfying truth assignment, you do not have to list all possible combinations. (4 marks)

(ii) Based on your answer to the previous question, which channels should each network use in order

to avoid interference? (4 marks)

Advice on how to do the assignment

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 via WebCMS (or give) as a single pdf file.

• 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 the lecture notes or book). You can use the

material presented in the lecture or book (without proving it). You do not need to write more than

necessary (see comment above).

• When giving answers to questions, we always would like you to prove/explain/motivate your answers.

• If you use further resources (books, scientific papers, the internet,...) to formulate your answers, then

add references to your sources.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Rtos Kernel Assignmenthelp With ,Ghost... 2019-11-14
- Algorithm Course Assignmentghostwriter... 2019-11-14
- Help With Fpu Assignment,Ghostwriter P... 2019-11-14
- Ghostwriter Msc/Icy Course Assignment,... 2019-11-14
- Cse105 Assignmenthelp With ,Java Progr... 2019-11-14
- Ghostwriter Fm 9528 Assignment,Help Wi... 2019-11-14
- Cmt115 Assignmenthelp With ,Programmin... 2019-11-14
- Eng5298 Assignmenthelp With ,Ghostwrit... 2019-11-14
- Stat 432 Assignmentghostwriter ,R Prog... 2019-11-14
- Jit104 Assignmenthelp With ,Ghostwrite... 2019-11-13
- Help With Stat 3675Q Assignment,Ghostw... 2019-11-13
- Csc 360 Assignmentghostwriter ,Help Wi... 2019-11-13
- Ghostwriter Cpt120 Assignment,Ghostwri... 2019-11-13
- Comp9444 Assignmenthelp With ,Python P... 2019-11-13
- Help With Cs1026 Assignment,Analysis C... 2019-11-13
- Lp002 Assignmenthelp With ,Ghostwriter... 2019-11-13
- Ghostwriter Comp 250 Assignment,Help W... 2019-11-13
- Cmt107 Assignmenthelp With ,Ghostwrite... 2019-11-12
- Econometrics Assignmenthelp With ,Ghos... 2019-11-12
- Help With Dataset Course Assignment,Gh... 2019-11-12

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2014 www.asgnhelp.com

Programming Assignment Help！