CS计算机代考程序代写 chain University of Sussex 2 May 2019

University of Sussex 2 May 2019
Limits of Computation Test
⇒→→→→→→→→→→ → → CandidateNo.
• Please answer ALL questions by writing on THIS SHEET. You are not
allowed to use any other documents or devices.
• Please write your candidate number in the box above.
• Questions are equally weighted (but Q1 – Q2 which have 2 extra marks each). Special “Spring” treat: your lowest scoring answer won’t count.
• You have 40 minutes to answer all 17 questions.
1. On the right hand side, write the program-as-data representation of the WHILE- program on the left (variable numbers start at 0):
test read A { [0,
if tl A {
while hd B
{ B:= tl A } }
else{ } }
write B
􏰎 ⟨ ⟨ nil.nil ⟩.⟨ nil.nil ⟩ ⟩ 􏰎 ⟨ [0].[0,1] ⟩ 􏰎 ⟨ [0,1].⟨ nil.nil ⟩ ⟩
􏰎 ⟨1.⟨0.[1]⟩⟩ 􏰎 ⟨1.[nil,1]⟩ 􏰎 ⟨⟨nil.nil⟩.⟨nil.⟨nil.nil⟩⟩⟩
3. Which of the following problems are undecidable? Tick the ones that are.
􏰎 Halting 􏰎 Graph Colouring 􏰎 Postman 􏰎 Primality 􏰎 Tiling 􏰎 TSP
4. Complete the sentence: “For an L-program p, the term [p]L denotes the semantics of which is a function of type → .”
5. The class of problems decidable by a WHILE-program is the same as the class of programs decidable by a TM-program. Is this correct? Tick: 􏰎 yes 􏰎 no.
Give a short reason: .
6. Complete the sentence: “A L-semidecidable problem is L-decidable if, and only if, .”
7. Complete the sentence: “To show that the Halting Problem, HALT, is WHILE- semidecidable we proved that
is a semidecision procedure for it.”
8. Complete the definition of the operational semantics of WHILE assignment :
X := E ⊢ σ→σ[ := ] if E􏰖 􏰗 = v.
9. Rice’s Theorem says that certain kind of problems are undecidable. Complete: “To
satisfy the conditions of Rice’s Theorem a problem must be . . .
1 2 3 ”. P.T.O
]
2. Tick those terms below that are encoded by the same binary tree as list [1, 0, 1] .

10. Which of the following problems x ∈ A? can be shown to be undecidable by applying Rice’s Theorem? Tick the right box in each case:
(a) A = { p ∈ D | p is a WHILE-program-as-data that tests whether its argument is 􏰯6􏰰 } 􏰎 decidable 􏰎 undecidable by Rice’s theorem
(b) A = { p ∈ D | p is a WHILE-program-as-data such that timeWHILE(nil) > 456 } p
􏰎 decidable 􏰎 undecidable by Rice’s theorem
(c) A = { p ∈ D | p is a WHILE-program-as-data that returns nil for any input }
􏰎 decidable 􏰎 undecidable by Rice’s theorem
11. Complete the Cook-Karp (Cobham Edmonds) thesis: “The
problems are exactly those in .”
12. Assume we have a WHILE-program p such that timeWHILE(d) = 2|d|2 + 300.
Tick only the statements that are correct.
􏰎 p ∈ WHILEtime(f ) where f (n) = 9n2 + 291 􏰎 p has a runtime bound in O(n2 log n)
􏰎 p ∈ WHILEtime(f) where f(n) = n2 + 300n
p
􏰎 p ∈ WHILElintime 􏰎 p ∈ WHILEptime
􏰎 timeWHILE is in o(n2) p
13. Define the class NPTM (either of the two definitions is fine): “A problem A is in NPTM iff
. 􏰎 TSPisinPTAS 􏰎 TSPisinAPX 􏰎 0-1KnapsackisinPTAS
14. Tick only the correct statements:
􏰎 P⊆RP 􏰎 PTAS⊆APX 􏰎 MetricTSPisinAPX
15. Complete: “SAT is defined as follows: F ∈ SAT iff F is a Boolean formula in normal form and .
16. True, false or unknown? Tick the correct box for each case.
TIMEWH1 LE (6n) 􏰴 TIMEWH1 LE (7n) TIMETM(O(4n)) 􏰴 TIMETM(O(n2)) PTM ⊆ NPTM
Graph Colouring is in P
0-1 Knapsack is NP-complete P􏰴EXP
􏰎 unknown 􏰎 true 􏰎 false 􏰎 unknown 􏰎 true 􏰎 false 􏰎 unknown 􏰎 true 􏰎 false 􏰎 unknown 􏰎 true 􏰎 false 􏰎 unknown 􏰎 true 􏰎 false 􏰎 unknown 􏰎 true 􏰎 false
17. The CANDYCRUSH Problem is defined as follows.
Instance: an n×m board filled with coloured candies (6 possible colours), a number k and a score s to be achieved or beaten. The score for a sequence of swaps equals the number of chains of 3 identical candies deleted.
Question: Is there a sequence of k swaps which obtains a score of s or more?
Tick all correct answers: CANDYCRUSH is known to be
􏰎 decidable 􏰎 inLIN 􏰎 inP 􏰎 inNP
Give an example of a statement that if proven would imply that CANDYCRUSH is NP-hard. The statement must not involve the definition of NP-hard.
.