COMP 9020代写 计算机作业代写

COMP 9020 – Assignment 3

COMP 9020代写 Note: In your assignment, how you arrived at your solution is as important(if not more so) than the solution itself

Note: In your assignment, how you arrived at your solution is as important (if not more so) than the solution itself and will be assessed accordingly. There may be more than one way to find a solution, and your approach should contain enough detail to justify its correctness. Lecture content can be assumed to be common knowledge.

1.Let(T, ∧, ∨,^j , 0, 1) be a Boolean COMP 9020代写

Define ∗ : T × T → T and ◦ : T × T → T as follows:

x ∗ y := (x ∨ y)^j x ◦ y := (x ∧ y)^j

(a)Show, using the laws of Boolean Algebra, how to define x ∗ y using only x, y, ◦ and

(b)Show, using the laws of Boolean Algebra, how to define x ◦ y using only x, y, ∗ and

(10 marks)COMP 9020代写

Define R ⊆ T × T as follows:

(x, y) ∈ R if, and only if, (x ∧ y) ∨ (x^j ∧ y^j) = 1

(c)Show, using the laws of Boolean Algebra, that R is an equivalence relation. Hint: You may want to use the observation that if A = B = 1 then A ∧ B ∧ C = A ∧B implies C = 1 (why?) COMP 9020代写

(10 marks)

2.Let P F denote the set of well-formed propositional formulas made upof propositional variables,  丅, 丄  , and the connectives   ,   ∧, and  ∨ .  Recall from Quiz 7 the definitions of dual and flip as functions from P F to P F :

• dual(p)= p flip(p) = ¬p
• dual(T) = ⊥; dual(⊥)= T flip(T) = T; flip(⊥) = ⊥
• dual(¬ϕ)= ¬dual(ϕ) flip(¬ϕ) = ¬flip(ϕ)
• dual(ϕ∧ ψ) = dual(ϕ) ∨ dual(ψ)  flip(ϕ ∧ ψ) = flip(ϕ) ∧ flip(ψ)
• dual(ϕ∨ ψ) = dual(ϕ) ∧ dual(ψ)  flip(ϕ ∨ ψ) = flip(ϕ) ∨ flip(ψ)

(a)For the formula ϕ = p ∨ (q ∧¬r):  COMP 9020代写

(i)What isdual(ϕ)?

(ii)What  isflip(ϕ)?

(b)Prove that for all ϕ ∈ P F :  flip(ϕ) is logically equivalent to¬dual(ϕ).

(10 marks)

3.Let P (n) be the proposition that: for all k, with 1 ≤ k ≤n, COMP 9020代写

(a)Prove  that P (n)holds  for all n (Note: it is possible to do this without using induction)

(10 marks)

We can compute ⁿ from the formula given in lectures,  however  this  can often require computing unnecessarily large numbers.  For  example,

100  = 253338471349988640 which can be expressed as a 64-bit integer,

but 100! is larger than a 512-bit integer. We can, however, make use of the equation above to compute  ⁿ  more efficiently.  Here are two algorithms  COMP 9020代写

for doing this:

chooseRec(n, k) : chooseIter(n, k) :

if k = 0  or  k = n : return 1 Let C be a n n array else : for m = 1 to n :

x := chooseRec(n 1, k 1) C[m][0]=C[m][m]=1  COMP 9020代写

y := chooseRec(n 1, k) for  j = 1 to m 1 :

return  x + y C[m][j]=C[m 1][j 1]

+ C[m 1][j]

return C[n][k]

Let t_rec(n, k) be the running time for chooseRec(n, k), and let t_iter(n) be the running time for chooseIter(n, k). Let T_rec(n) = max_0≤k≤n t_rec(n, k) and T_iter(n) = max_0≤k≤n t_iter(n, k) (so T_rec(n) ≥ t_rec(n, k) for all k, and likewise for T_iter(n)).

(a)Give an asymptotic upper bound for T_rec(n).  Justify your answer.

(b)Give an asymptotic upper bound for T_iter(n).  Justify your answer.

(10 marks)

Advice on how to do the assignment COMP 9020代写

All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Pla- giarism” policies.

Assignments are to be submitted via WebCMS (or give) as a single pdf (max size 2Mb). In Linux, the following command

pdfjoin –outfile output.pdf input1.pdf input2.pdf …

can be used to combine multiple pdf files. The command  COMP 9020代写

convert -density 150×150 -compress jpeg input.pdf output.pdf

can be used to reduce the filesize of a pdf (change 150 to reduce/improve quality/filesize). Please ensure your files are legible before submitting.

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/exp- lain/motivate your answers. COMP 9020代写

If you use further resources (books, scientific papers, the internet,…) to formulate your answers, then add references to your sources.

其他代写：代写CS C++代写 java代写 matlab代写 web代写 app代写 作业代写 物理代写 数学代写 考试助攻 paper代写 r代写 assignment代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写