xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Python代写-CCS2FC2

时间：2020-12-20

5CCS2FC2: Foundations of Computing II

Coursework 2

Issued: 7 December 2020 Deadline: 21 December 2020

Notice to Candidates:

This assessment is to be completed independently and submitted on KEATS by 18:00

on the date specified above. You should submit your solutions via the KEATS quiz

provided on the module page.

The assessment is ‘open book’ but you should complete your work independently.

Your work will be checked for plagiarism and collusion and discipliniary action will be

taken against any candidates caught colluding.

Please see the Plagiarism Declaration on KEATS.

Answer all parts of TWO out of THREE question (A, B, and C).

The total number of marks available for this assessment is 20 marks.

Question A

(i) Construct a recurrence relation for T (n), with T (1) = 1, such that

n2 log2(n) ≤ T (n) ≤ 3n2 log2(n) + 1 (†)

for all n ≥ 1. [3 marks]

(ii) Prove by induction on n that your recurrence relation satisfies either the upper bound or

lower bound provided in criteria (†). Note that if your recurrence relation involves floor

or ceiling functions then one bound will be easier to prove than the other.

Marks will be awarded for the clarity of your proof.

[7 marks]

Page 1 of 3

Question B

(i) Consider the following function M that returns True (resp. False) if the number of

iterations of the Collatz function required for the input string w, interpretted as a binary

integer, to reach 1 is < 100 (resp. ≥ 100).

def M(w) :

n = i n t (w, 2 )

k = 0

whi le True :

i f n==1: return ( k<100)

i f ( n%2)==0: n = n/2

e l s e : n = 3∗n + 1

k += 1

Construct a pair of functions M1(s) and M2(s) such that the language of M1 is equivalent

to the language of M2 if and only if M rejects the input word w = 1101.

Your construction must NOT require you to compute whether or not M rejects w.

You can make use of the function UTM(M,w) which simulates a Universal Turing Machine

and will return True (resp. False) if and only if M returns True (resp. False) on

input w.

[4 marks]

(ii) Given an (undisclosed) function reject(M,w) that takes two inputs: M an algorithm and

w an input String, and claims to return True if and only if M rejects the input word w.

Construct a function paradox(w) that takes a single String as input and outputs a

boolean True or False, such that

reject(paradox,paradox) = True ⇐⇒ paradox(paradox) = True

thereby proving that it is not possible for reject(M,w) to function as claimed, and

therefore that the Rejecting problem RTM is undecidable.

[4 marks]

(iii) What does this say about the decidability of the equivalence problem EQTM and why?

[2 marks]

Page 2 of 3

Question C

(i) Construct a Probabilistic Turing Machine (PTM) M and an input word w ∈ {0, 1}∗ that

has the following properties

— M has at least 5 states, including the initial, accepting and rejecting states,

— M has a non-terminating computation on your chosen input w,

— The expected termination time E [T ] of M on input w is finite.

[7 marks]

(ii) What is the probability of our proposed machine M accepting your proposed input

word w? i.e what is Prob (M(w) = 1)?

[3 marks]

End of Questions

Page 3 of 3

Coursework 2

Issued: 7 December 2020 Deadline: 21 December 2020

Notice to Candidates:

This assessment is to be completed independently and submitted on KEATS by 18:00

on the date specified above. You should submit your solutions via the KEATS quiz

provided on the module page.

The assessment is ‘open book’ but you should complete your work independently.

Your work will be checked for plagiarism and collusion and discipliniary action will be

taken against any candidates caught colluding.

Please see the Plagiarism Declaration on KEATS.

Answer all parts of TWO out of THREE question (A, B, and C).

The total number of marks available for this assessment is 20 marks.

Question A

(i) Construct a recurrence relation for T (n), with T (1) = 1, such that

n2 log2(n) ≤ T (n) ≤ 3n2 log2(n) + 1 (†)

for all n ≥ 1. [3 marks]

(ii) Prove by induction on n that your recurrence relation satisfies either the upper bound or

lower bound provided in criteria (†). Note that if your recurrence relation involves floor

or ceiling functions then one bound will be easier to prove than the other.

Marks will be awarded for the clarity of your proof.

[7 marks]

Page 1 of 3

Question B

(i) Consider the following function M that returns True (resp. False) if the number of

iterations of the Collatz function required for the input string w, interpretted as a binary

integer, to reach 1 is < 100 (resp. ≥ 100).

def M(w) :

n = i n t (w, 2 )

k = 0

whi le True :

i f n==1: return ( k<100)

i f ( n%2)==0: n = n/2

e l s e : n = 3∗n + 1

k += 1

Construct a pair of functions M1(s) and M2(s) such that the language of M1 is equivalent

to the language of M2 if and only if M rejects the input word w = 1101.

Your construction must NOT require you to compute whether or not M rejects w.

You can make use of the function UTM(M,w) which simulates a Universal Turing Machine

and will return True (resp. False) if and only if M returns True (resp. False) on

input w.

[4 marks]

(ii) Given an (undisclosed) function reject(M,w) that takes two inputs: M an algorithm and

w an input String, and claims to return True if and only if M rejects the input word w.

Construct a function paradox(w) that takes a single String as input and outputs a

boolean True or False, such that

reject(paradox,paradox) = True ⇐⇒ paradox(paradox) = True

thereby proving that it is not possible for reject(M,w) to function as claimed, and

therefore that the Rejecting problem RTM is undecidable.

[4 marks]

(iii) What does this say about the decidability of the equivalence problem EQTM and why?

[2 marks]

Page 2 of 3

Question C

(i) Construct a Probabilistic Turing Machine (PTM) M and an input word w ∈ {0, 1}∗ that

has the following properties

— M has at least 5 states, including the initial, accepting and rejecting states,

— M has a non-terminating computation on your chosen input w,

— The expected termination time E [T ] of M on input w is finite.

[7 marks]

(ii) What is the probability of our proposed machine M accepting your proposed input

word w? i.e what is Prob (M(w) = 1)?

[3 marks]

End of Questions

Page 3 of 3