首页 >
> 详细

COMP9020 Assignment 2 2021 Term 2

Due: Monday, 19th July, 12:00 (AEST)

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

Let S be a set.

(a) Show that for any set T and any function f : S→ T, the relation R f ? S× S, defined as:

(s, s′) ∈ R f if and only if f (s) = f (s′)

is an equivalence relation. (9 marks)

(b) Show that if R ? S× S is an equivalence relation, then there exists a set T and a function fR : S → T

such that:

(s, s′) ∈ R if and only if fR(s) = fR(s′)

(6 marks)

Problem 2 (34 marks)

Let R ? S× S be any binary relation on a set S. Consider the sequence of relations R0, R1, R2, . . ., defined

as follows:

R0 := I = {(x, x) : x ∈ S}, and

Rn+1 := Rn ∪ (R; Rn) for n ≥ 0

Suppose there exists i ∈N such that Ri = Ri+1.

(a) Prove that Rj = Ri for all j ≥ i. (6 marks)

(b) Prove that Rj ? Ri for all j ≥ 0. (4 marks)

(c) If |S| = k, explain why Rk2 = Rk2+1. (4 marks)

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

Hint: Use results from Assignment 1 (6 marks)

(e) If |S| = k, show that Rk2 is transitive. (4 marks)

(f) If |S| = k, show that (R ∪ R←)k2 is an equivalence relation. (6 marks)

1

(g)? If |S| = k show that (R ∪ R←)k2 is the minimum (with respect to ?) of all equivalence relations that

contain R. (4 marks)

Remark

The relation at the limita as n tends to infinity, R? = limn→∞ Ri, is known as the reflexive, transitive

closure of R, and is closely connected to the Kleene star operator.

aBecause Rj ? Ri ? S× S for all j ≤ i, the Knaster-Tarski theorem ensures this limit always exists, even for infinite S.

Problem 3 (20 marks)

Let B = {0, 1} and consider the function f : N→ B given by

f (n) =

{

1 if n > 0,

0 otherwise.

(a) Show that for all a, b ∈N:

(i) f (a + b) = max{ f (a), f (b)}

(ii) f (ab) = min{ f (a), f (b)}

(6 marks)

From Problem 1, we know that R f ?N×N, the relation given by:

(m, n) ∈ R f if and only if f (m) = f (n)

is an equivalence relation. Let E ? Pow(N) be the set of equivalence classes of R f , and for n ∈ N, let

[n] ∈ E denote the equivalence class of n.

We would like to define binary operations, and , on E as follows:

[x] [y] := [x + y]

[x] [y] := [xy].

The difficulty is that the operands [x] and [y] can have multiple representations (e.g. if z ∈ [x] then

[x] = [z]), and so it is not clear that such a definition makes sense: if we take a different representation of

the operands, do we still end up with the same result? That is, if [x] = [x′] and [y] = [y′] is it the case that

[x + y] = [x′ + y′] and [xy] = [x′y′]? Our next step is to show that such a definition makes sense.

(b) Define relations , ? E2 ×E as follows:

((X, Y), Z) ∈ if and only if there is x ∈ X and y ∈ Y such that x + y ∈ Z

((X, Y), Z) ∈ if and only if there is x ∈ X and y ∈ Y such that xy ∈ Z

(i) Show that is a function.

(ii) Show that is a function.

(6 marks)

2

Part (b) shows that the informal definition of and given earlier is well-defined, so from now we will

view and as binary operations on E, that is , : E×E→ E.

(c) Show that for all A, B, C ∈ E:

(i) A [1] = A

(ii) A B = B A

(iii) A (B C) = (A B) (A C)

(8 marks)

Remark

Objects that have a concept of “addition” () and “multiplication” () where:

addition and multiplication are associative,

both operations have identities (see (c)(i)),

addition is commutative (see (c)(ii)), and

multiplication distributes over addition (see (c)(iii))

are known as semirings. We have already seen a number of semirings in this course:

The natural numbers with usual addition and multiplication,

Integers modulo n with addition and multiplication modulo n,

Subsets of a set X with union and intersection,

Languages with union and concatenation,

Binary relations with union and relational composition (see Assignment 1),

Matrices with matrix addition and matrix multiplication.

Problem 4? (6 marks)

Let f (n) be defined recursively as follows:

f (0) = 0 f (n) = f (bn

3

c) + 3 f (bn

5

c) + n for n ≥ 1

Show that f (n) ∈ O(n).

Problem 5 (20 marks)

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

3

If we include empty binary trees (trees with no nodes) as part of the definition, then we can simplify the

description of the data structure. Rather than saying a node has 0, 1, or 2 successor nodes, we can instead

say that a node has exactly two children, where a child is a binary tree. That is, we can abstractly define

the structure of a binary tree as follows:

(B): An empty tree, τ

(R): An ordered pair (Tleft, Tright) where Tleft and Tright are trees.

So, for example, the above tree would be defined as the tree T where:

T = (T1, T2), where

T1 = (T3, T4) and T2 = (T5, τ), where

T3 = T4 = T5 = (τ, τ)

That is,

A leaf in a binary tree is a node that has no successors (i.e. it is of the form (τ, τ)). A fully-internal node in

a binary tree is a node that has exactly two successors (i.e. it is of the form (T1, T2) where T1, T2 6= τ). The

example above has 3 leaves (T3, T4, and T5) and 2 fully-internal nodes (T and T1). For technical reasons

(that will become apparent) we assume that an empty tree has 0 leaves and ?1 fully-internal nodes.

(a) Based on the recursive definition above, recursively define a function count(T) that counts the number

of nodes in a binary tree T. (4 marks)

(b) Based on the recursive definition above, recursively define a function leaves(T) that counts the number

of leaves in a binary tree T. (4 marks)

(c) Based on the recursive definition above, recursively define a function internal(T) that counts the num-

ber of fully-internal nodes in a binary tree T. (4

marks)

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

for all binary trees T. Your proof should be based on your answers given in (b) and (c). (8 marks)

Problem 6? (5 marks)

Let Σ be a finite set, totally ordered by <. Give a formal, recursive definition of the lexicographic ordering

≤lex? Σ? × Σ?.

4

Advice on how to do the assignment

Collaboration is encouraged, but all submitted work must be done individually without consulting some-

one 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.

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

swers. 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 referenced1 – however, answers that depend too heavily on

external resources may not receive full marks if you have not adequately demonstrated ability/un-

derstanding.

1Proper 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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp2

- 辅导comp30027帮做python编程 2021-08-02
- 辅导csse2002/7023-Assignment 1辅导留学... 2021-08-02
- 辅导rush2辅导c/C++ 2021-08-02
- 辅导r语言编程|辅导spss|辅导web开发|辅导... 2021-05-10
- Data留学生编程辅导、辅导analysis程序、Sql语言程序调试辅导r语 2021-05-10
- 辅导31748程序语言、辅导programming编程设计、Java，Pyt 2021-05-10
- 辅导cis 657编程、辅导c/C++程序、C++编程调试帮做haskell 2021-05-10
- Com1005程序辅导、辅导java编程语言、辅导java程序辅导留学生pr 2021-05-10
- 辅导sit283程序、辅导c/C++，Python编程设计、Cs，Java程 2021-05-09
- C++程序辅导、辅导c++程序、辅导program编程语言辅导r语言编程|辅 2021-05-09
- 辅导0ccs0cse编程、辅导r，Java，Python程序语言辅导web开 2021-05-09
- Comp124编程语言辅导、Java程序辅导、辅导program语言编程辅导 2021-05-09
- Comp122编程语言辅导、辅导java程序语言、Java程序调试帮做has 2021-05-09
- 辅导ele00041i 调试java Programming 2021-05-08
- 辅导econ 2014-Assignment 1 Managerial... 2021-05-08
- 辅导mast90044-Assignment 1 Thinking An... 2021-05-08
- 辅导cs310-Assignment 2 Hash Tables 2021-05-08
- 辅导5pm 调试java编程、Java编程辅导 2021-05-08
- 辅导cs544 Final Exam Preparation Guide... 2021-05-08
- 辅导infs7450 Social Media Analytics 2021-05-08