329 Midterm 2

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/32

encourage image

There's no tags or description

Looks like no tags are added yet.

33 Terms

1
New cards
Which statement about the cardinalities of the set of natural numbers N = {1, 2, 3, ... } and the set of even natural numbers 2N = {0, 2, 4, 6, ... } is correct? / a. |N| < |2N| / b. |N| = |2N| / c. |N| > |2N| / d. The cardinalities |N| and |2N| are incomparable
b. |N| = |2N|
2
New cards
Which statement about the cardinalities of the set A and its power set P(A) is correct? / a. The cardinalities |A| and |P(A)| are incomparable / b. |A| = |P(A)| / c. |A| > |P(A)| / d. |A| < |P(A)|
d. |A| < |P(A)|
3
New cards
How are the cardinalities of the sets N of natural numbers, Q of rational numbers, and R of real numbers related to each other? / a. |N| = |Q| = |R| / b. |N| < |Q| = |R| / c. |N| = |Q| < |R| / d. |N| < |Q| < |R|
c. |N| = |Q| < |R|
4
New cards
What does the Church-Turing-Thesis say? / a. Any real-world computation can be translated into an equivalent computation performed by a Turing machine. / b. The λ-calculus can compute more than the Turing machine. / c. The Halting-Problem of the Turing machine is undecidable. / d. The Turing machine can compute more than the λ-calculus.
a. Any real-world computation can be translated into an equivalent computation performed by a Turing machine.
5
New cards
Which of the following languages are decidable? / a. EQDFA = { | A and B are DFAs and L(A) = L(B)} / b. ADFA = { | B is a DFA and B accepts w} / c. ATM = { | M is a TM and M accepts w } / d. ANFA = { | B is a NFA and B accepts w}
a. EQDFA = { | A and B are DFAs and L(A) = L(B)} / b. ADFA = { | B is a DFA and B accepts w} / d. ANFA = { | B is a NFA and B accepts w}
6
New cards
What is a Turing machine? / a. An early computing device invented by Alan Turing. / b. A theoretical machine to model and reason about computation. / c. A device invented by Alan Turing to discriminate humans from computers. / d. A machine created by Alan Turing to decipher Enigma codes.
b. A theoretical machine to model and reason about computation.
7
New cards
The complexity class P does depend on the model of computation
Yes, but it is equivalent for all reasonable deterministic models of computation.
8
New cards
Languages in P can be efficiently decided / a. Not at all, problems in P generally have a high time complexity. / b. Yes, that's the meaning of the class P. / c. Not necessarily. The time complexity might be O(n^k) with a very large value for k
c. Not necessarily. The time complexity might be O(n^k) with a very large value for k
9
New cards
Which of the following statements are correct (mark all that apply): / a. All languages in P are decidable / b. All regular languages are in the complexity class P / c. All decidable languages are in the complexity class P. / d. All languages in P are T-recognizable.
a. All languages in P are decidable / b. All regular languages are in the complexity class P / d. All languages in P are T-recognizable.
10
New cards
What is the definition of the Bachmann-Landau big O notation? / f(n)∈O(g(n))⟺ / a. ∃k>0∀n0∃n>n0:|f(n)|≥kg(n) / b. ∀k>0∃n0∀n>n0:|f(n)|<kg(n) / c. ∃k>0∃n0∀n>n0:|f(n)|≤kg(n) / d. ∃k1>0∃k2>0∃n0∀n>n0:k1g(n)≤f(n)≤k2g(n)
c. ∃k>0∃n0∀n>n0:|f(n)|≤kg(n)
11
New cards
What is the definition of mapping reducibility (also called many-one reducibility)? / The language A⊆Σ∗ is mapping reducible to the language B⊆Γ∗ and we write A≤mB / a. if there is a computable function f:Σ∗→Γ∗ such that w∈B⟺f(w)∈A. / b. if there is a computable function f:Γ∗→Σ∗ such that w∈B⟺f(w)∈A. / c. if there is a computable function f:Σ∗→Γ∗ such that w∈A⟺f(w)∈B. / d. if there is a computable function f:Γ∗→Σ∗ such that w∈A⟺f(w)∈B.
c. if there is a computable function f:Σ∗→Γ∗ such that w∈A⟺f(w)∈B.
12
New cards
Are all regular languages in the complexity class P ? / a. No, because a PDA might not halt. / b. No, because a DFA reads one input symbol per state transition. / c. No, because an NFA could take exponential time to accept. / d. Yes, because a DFA reads one input symbol per state transition.
d. Yes, because a DFA reads one input symbol per state transition.
13
New cards
Two models of computation are polynomially related if each can simulate the other with a polynomial overhead, i.e. if the computation takes t(n) time on one model it may take t k(n) time on the other model, for some k . / Which of the following are polynomially related to a 1-tape Turing Machine? / a. cellular automata / b. random access machines (RAM) / c. multi-dimensional Turing Machines / d. multi-tape TMs
a,b,c,d: random access machines (RAM), multi-dimensional Turing Machines, multi-tape TMs, cellular automata
14
New cards
Alan Turing proved the undecidability of the halting problem. Which proof technique from set theory did inspire Turing? / a. Feynman's technique / b. Cantor's diagonal argument / c. Newton's method / d. Zorn's lemma
b. Cantor's diagonal argument
15
New cards
What is the output (on the tape) of the Turing Machine M on input 10010111 where / a. 10011000 / b. 01101001 / c. 01100111 / d. 10010110
a. 10011000
16
New cards
Is the complexity class P closed under union, ie. does L1 ∈ P and L2 ∈ P imply that L1 ∪ L2 ∈ P? / a. This is unknown / b. No / c. Yes
c. Yes
17
New cards
Which of the following are true? / a. n^2 ∈ O(n) / b. 2n ∈ O(n) / c. n log n ∈ O(n^2) / d. 3^n ∈ 2^O(n)
b. 2n ∈ O(n) / c. n log n ∈ O(n^2) / d. 3^n ∈ 2^O(n)
18
New cards
Match the Bachmann-Landau asymptotic notation with the correct definition: / a) eK > 0En0 Vn > n0: |f(n) ≤ kg(n) / b) ek1 > 0ek2 > 0en0 > n0: k1g(n) ≤ f(n) k2g(n) / c) ek > 0en0 Vn > n0: f(n) ≥ kg(n) / d) Vk > 0en0 Vn > n0: |(fn)| < kg(n) / 1. f(n) e 0(g(n)) (average case) -> / 2. f(n) e O(g(n)) (worse case) -> / 3. f(n) e o(g(n)) (loose upper bound) -> / 4. f(n) e N(g(n)) (best case) ->
1. B / 2. A / 3. D / 4. C
19
New cards
Decidability of languages does not depend on the model of computation. / a. This is an open problem / b. True / c. False
b. True
20
New cards
What are T-decidable close under? / Choose all that apply / A) union / B) complement / C)kleenex / D)intersection
A) union / B) complement / C)kleenex / D)intersection
21
New cards
What are T-recognizable close under? / Choose all that apply / A) union / B) complement / C)kleenex / D)intersection
A) union / C)kleenex / D)intersection
22
New cards
Match the language with the smallest class it's contained in. / A) {a,b,c} / B) { | The TM M accepts the input w.}C) {a^k | k e N0}D) {a^kb^k | k e N0}E) {a^kb^kc^k | k e N0}Context FreeDecidableFiniteRegularT-recognizable
Context Free -> D / Decidable -> E / Finite -> A / Regular -> C / T-recognizable -> B
23
New cards
What are the known relationships between the complexity classes P and NP / a. NP ⊆ P / b. P ⊆ NP / c. P ≠ NP / d. P = NP
b. P ⊆ NP
24
New cards
A language B is NP-Complete iff / a. B is not in NP and no language A in NP can be polynomially reduced to B. / b. B is not in NP and any language A in NP can be polynomially reduced to B. / c. B is in NP and no language A in NP can be polynomially reduced to B. / d. B is in NP and any language A in NP can be polynomially reduced to B.
d. B is in NP and any language A in NP can be polynomially reduced to B.
25
New cards
Which of these languages are NP-Complete? / a. 3-SAT (3-CNF Boolean Satisfiability) / b. HALT (Halting Problem) / c. PATH (Path Problem) / d. SAT (Boolean Satisfiability)
a,d: 3-SAT (3-CNF Boolean Satisfiability), SAT (Boolean Satisfiability)
26
New cards
A language A ⊆ Σ* is polynomial time reducible to the language B ⊆ Γ* and we write A ≤p B / a. if there is a computable function f: Σ* → Γ* such that w ∈ A ⟺ f(w) ∈ B. / b. if there is a function f: Σ* → Γ* computable in polynomial time such that w ∈ A ⟺ f(w) ∈ B. / c. if there is a polynomial f: Σ* → Γ* such that w ∈ A ⟺ f(w) ∈ B. / d. if there is a function f: Σ* → Γ* such that w ∈ A ⟺ f(w) ∈ B.
b. if there is a function f: Σ* → Γ* computable in polynomial time such that w ∈ A ⟺ f(w) ∈ B.
27
New cards
If we would find a proof for SAT ∈ P then this would imply that / a. P ≠ NP / b. P ⊂ NP / c. P = NP / d. P ⊃ NP
c. P = NP
28
New cards
How can we describe the complexity classes P and NP informally? / a. NP = All languages where we can guess membership quickly. P = All languages where we can test membership quickly / b. NP = All languages where we can verify membership quickly. P = All languages where we can guess membership quickly / c. NP = All languages where we can verify membership quickly. P = All languages where we can test membership quickly / d. NP = All languages where we can verify membership quickly. P = All languages where we cannot test membership quickly
c. NP = All languages where we can verify membership quickly. P = All languages where we can test membership quickly
29
New cards
Which of the following boolean expressions are in 3-CNF? / a. (u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!) / b. (x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!) / c. (u ∧ y! ∧ z) ∨ (x ∧ v ∧ z) ∨ (x ∧ y! ∧ w!) / d. (x ∧ y! ∧ z) ∨ (x ∧ y ∧ z) ∨ (x ∧ y! ∧ z!)
a. (u ∨ y! ∨ z) ∧ (x ∨ v ∨ z) ∧ (x ∨ y! ∨ w!) / b. (x ∨ y! ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y! ∨ z!)
30
New cards
Is SAT NP-complete? / a. Only if P=NP / b. This is unknown / c. Yes / d. No
c. Yes
31
New cards
Is the following formula satisfiable? (x ∨ y) ∧ (x ∨ y!) ∧ (x! ∨ y) ∧ (x! ∨ y!) / a. Yes / b. No
b. No
32
New cards
What is the significance of NP-hard problems in computational complexity? / A) They are at least as hard as the hardest problems in NP. / B) They can be solved in polynomial time. / C) They are exactly the problems in NP. / D) They are easier than any problem in NP.
A) They are at least as hard as the hardest problems in NP.
33
New cards
Match each problem with the smallest class we know it is in: SAT, 3SAT, 2SAT, Sorting integers
SAT -> NP-Complete / 3SAT -> NP-Complete / 2SAT -> P / Sorting integers -> P