Description

1. [2 pts] (Multiple choice) Assume there is a decider M, and a language L(M) recognized by M. Which of the following statements is/are TRUE?
A. M must be a Turing Machine
B. L(M) must be a finite set
C. L(M) must be Turing-decidable
D. L(M) must be Turing-recognizable
E. M will halt on all inputs
2. [2 pts] (Multiple choice) If a language 𝐴 is Turing-decidable, then the subset of 𝐴 can be _____.
A. Turing-decidable
B. Turing-undecidable
C. Turing-recognizable
D. Turing-unrecognizable
3. [2 pts] (True or False) A language 𝐿 is Turing-recognizable if and only if both 𝐿 and its complement 𝐿𝐶 are Turing-decidable.
4. [1 pts] (True or False) If 𝑓(𝑛) = 𝑂(𝑔(𝑛)) and 𝑔(𝑛) = 𝑂(ℎ(𝑛)), then 𝑓(𝑛) = 𝑂(ℎ(𝑛)).
5. [1 pts] (True or False) For an arbitrary size input, an algorithm with O(1) time complexity will definitely solve the problem faster than an algorithm with O(n) time complexity.
6. [2 pts] Give the Big-O estimates for the following functions:
1) 𝑓(𝑛) = 2𝑛(𝑛2 + 1) + 10𝑛𝑙𝑜𝑔𝑛
2) 𝑓(𝑛) = 14 + 24 + 34 + ⋯+𝑛4