CS/ECE 374 A Fall 2019
Final Exam Study Questions
This is a “core dump” of potential questions for Midterm 1. This should give you a good idea of the types of questions that we will ask on the exam—in particular, there will be a series of True/False questions—but the actual exam questions may or may not appear in this handout. This list intentionally includes a few questions that are too long or difficult for exam conditions; these are indicated with a ∗star.
Don’t forget to review the study problems for Midterms 1 and 2; the final exam is cumulative!
Copyright By PowCoder代写 加微信 powcoder
How to Use These Problems
Solving every problem in this handout is not the best way to study for the exam. Memorizing
the solutions to every problem in this handout is the absolute worst way to study for the exam.
What we recommend instead is to work on a sample of the problems. Choose one or two problems at random from each section and try to solve them from scratch under exam conditions—by yourself, in a quiet room, with a 30-minute timer, without your notes, without the internet, and if possible, even without your cheat sheet. If you’re comfortable solving a few problems in a particular section, you’re probably ready for that type of problem on the exam. Move on to the next section.
Discussing problems with other people (in your study groups, in the review sessions, in office hours, or on Piazza) and/or looking up old solutions can be extremely helpful, but only after you have (1) made a good-faith effort to solve the problem on your own, and (2) you have either a candidate solution or some idea about where you’re getting stuck.
If you find yourself getting stuck on a particular type of problem, try to figure out why you’re stuck. Do you understand the problem statement? Are you stuck on choosing the right high-level approach? Are you stuck on the technical details? Or are you struggling to express your ideas clearly? (We strongly recommend writing solutions that follow the homework grading rubrics bullet-by-bullet.)
Similarly, if feedback from other people suggests that your solutions to a particular type of problem are incorrect or incomplete, try to figure out what you missed. For NP-hardness proofs: Are you choosing a good problem to reduce from? Are you reducing in the correct direction? Are you designing your reduction with both good instances and bad instances in mind? You’re not trying solve the problem, are you? For undecidability proofs: Does the problem have the right structure to apply Rice’s theorem? If you are arguing by reduction, are you reducing in the correct direction? You’re not using pronouns, are you?
Remember that your goal is not merely to “understand” the solution to any particular problem, but to become more comfortable with solving a certain type of problem on your own. “Understanding” is a trap; aim for mastery. If you can identify specific steps that you find problematic, read more about those steps, focus your practice on those steps, and try to find helpful information about those steps to write on your cheat sheet. Then work on the next problem!
CS/ECE 374 A Final Exam Study Problems Fall 2019
True or False? (All from previous final exams)
For each of the following questions, indicate every correct answer by marking the “Yes” box, and indicate every incorrect answer by marking the “No” box. Assume P ̸= NP. If there is any other ambiguity or uncertainty about an answer, mark the “No” box. For example:
Yes XNo x+y=5
Yes XNo XYes No XYes No
3SAT can be solved in polynomial time. Jeff is not the Queen of England.
If P = NP then Jeff is the Queen of England.
The actual exam will include forty true/false questions. Each correct choice will be worth 1⁄2 point, each incorrect choice will be worth −1⁄4 point, and each IDK will be worth +1⁄8 point.
1. Which of the following are a good English specifications of a recursive function that could possibly be used to compute the edit distance between two strings A[1 .. n] and B[1 .. n]?
Yes No Yes No
Yes No Yes No Yes No
Yes No Yes No
Edit(i, j) is the answer for i and j.
Edit(i, j) is the edit distance between A[i] and B[j].
Edit[i, j] =
Edit[i − 1, j − 1]
ifj=0 ifi=0 ifA[i]=B[j]
1+Edit[i,j−1]
1 + Edit[i − 1, j] 1 + Edit[i − 1, j − 1]
Edit[1 .. n, 1 .. n] stores the edit distances for all prefixes. Edit(i, j) is the edit distance between A[i .. n] and B[ j .. n].
Edit[i, j] is the value stored at row i and column j of the table.
Edit(i, j) is the edit distance between the last i characters of A and the
last j characters of B.
Edit(i, j) is the edit distance when i and j are the current characters in A
Edit(i, j, k, l) is the edit distance between substrings A[i .. j] and B[k .. l]. [I don’t need an English description; my pseudocode is clear enough!]
CS/ECE 374 A Final Exam Study Problems Fall 2019
2. Which of the following statements are true for every language L ⊆ {0, 1}∗?
Yes No Yes No Yes No Yes No Yes No Yes No
Yes No Yes No Yes No Yes No Yes No
Yes No Yes No Yes No Yes No Yes No
L is non-empty.
L is infinite.
L contains the empty string ε.
L∗ is infinite.
L∗ is regular.
L is accepted by some DFA if and only if L is accepted by some NFA.
L is described by some regular expression if and only if L is rejected by some NFA.
L is accepted by some DFA with 42 states if and only if L is accepted by some NFA with 42 states.
If L is decidable, then L is infinite.
If L is not decidable, then L is infinite.
If L is not regular, then L is undecidable.
If L has an infinite fooling set, then L is undecidable.
If L has a finite fooling set, then L is decidable.
If L is the union of two regular languages, then its complement L is regular.
If L is the union of two regular languages, then its complement L is context-free.
If L is the union of two decidable languages, then L is decidable.
If L is the union of two undecidable languages, then L is undecidable. If L ̸∈ P, then L is not regular.
L is decidable if and only if its complement L is undecidable.
Both L and its complement L are decidable.
CS/ECE 374 A Final Exam Study Problems Fall 2019
3. Which of the following statements are true for at least one language L ⊆ {0, 1}∗?
Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No
Yes No Yes No Yes No
L is non-empty.
L is infinite.
L contains the empty string ε.
L∗ is finite.
L∗ is not regular.
L is not regular but L∗ is regular.
L is finite and L is undecidable.
L is decidable but L∗ is not decidable.
L is not decidable but L∗ is decidable.
L is the union of two decidable languages, but L is not decidable.
L is the union of two undecidable languages, but L is decidable.
L is accepted by an NFA with 374 states, but L is not accepted by a DFA
with 374 states.
L is accepted by an DFA with 374 states, but L is not accepted by a NFA with 374 states.
L is regular and L ̸∈ P.
There is a Turing machine that accepts L.
There is an algorithm to decide whether an arbitrary given Turing machine accepts L.
4. Which of the following languages over the alphabet {0, 1} are regular?
Yes No Yes No Yes No Yes No Yes No
{0m1n|m≥0andn≥0}
All strings with the same number of 0s and 1s
Binary representations of all positive integers divisible by 17 Binary representations of all prime numbers less than 10100 ww w is a palindrome
CS/ECE 374 A Final Exam Study Problems Fall 2019
4. (continued) Which of the following languages over the alphabet {0, 1} are regular?
Yes No Yes No Yes No
wxw w is a palindrome and x ∈ {0,1}∗
〈M〉 M accepts a regular language
〈M〉 M accepts a finite number of non-palindromes
5. Which of the following languages/decision problems are decidable?
Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No
Yes No Yes No
0n12n0n12n n ≥ 0
ww w is a palindrome
〈M〉Maccepts〈M〉•〈M〉
〈M〉 M accepts a finite number of non-palindromes
〈M〉•wMacceptsww
〈M〉 • w M accepts ww after at most |w|2 transitions
Given an NFA N , is the language L(N ) infinite?
Given a context-free grammar G and a string w, is w in the language L(G)?
CircuitSat
Given an undirected graph G, does G contain a Hamiltonian cycle?
Given two Turing machines M and M′, is there a string w that is accepted by both M and M′?
CS/ECE 374 A Final Exam Study Problems Fall 2019
6. Which of the following languages can be proved undecidable using Rice’s Theorem?
Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No
0n12n0n12n n ≥ 0
ww w is a palindrome
〈M〉 M accepts an infinite number of strings
〈M〉 M accepts a finite number of strings
〈M〉 M accepts either 〈M〉 or 〈M〉R
〈M〉 M accepts both 〈M〉 and 〈M〉R
〈M〉 M does not accept exactly 374 palindromes
〈M〉 M accepts some string w after at most |w|2 transitions
〈M〉#w M rejects w after at most |w|2 transitions
Given two Turing machines M and M′, is there a string w that is accepted by both M and M′?
7. Recall the halting language Halt = {〈M〉 • w | M halts on input w}. Which of the following statements about its complement Halt = Σ∗ \ Halt are true?
Yes No Yes No Yes No Yes No Yes No Yes No
Halt is empty.
Halt is regular.
Halt is infinite.
Halt is decidable.
Halt is acceptable but not decidable. Halt is not acceptable.
CS/ECE 374 A Final Exam Study Problems Fall 2019
8. Suppose some language A ∈ {0, 1}∗ reduces to another language B ∈ {0, 1}∗. Which of the following statements must be true?
Yes No Yes No Yes No Yes No Yes No
A Turing machine that recognizes A can be used to construct a Turing machine that recognizes B.
A is decidable.
If B is decidable then A is decidable.
If A is decidable then B is decidable.
If B is NP-hard then A is NP-hard.
If A has no polynomial-time algorithm then neither does B.
9. Suppose there is a polynomial-time reduction from problem A to problem B. Which of the following statements must be true?
Yes No Yes No Yes No Yes No Yes No Yes No
Problem B is NP-hard.
A polynomial-time algorithm for B can be used to solve A in polynomial
If B has no polynomial-time algorithm then neither does A.
If A is NP-hard and B has a polynomial-time algorithm then P = NP. If B is NP-hard then A is NP-hard.
If B is undecidable then A is undecidable.
CS/ECE 374 A Final Exam Study Problems Fall 2019
10. Consider the following pair of languages:
• HamPath := G G is an undirected graph with a Hamiltonian path
• Connected := G G is a connected undirected graph
(For concreteness, assume that in both of these languages, graphs are represented by their
adjacency matrices.) Which of the following must be true, assuming P̸=NP?
Yes No Yes No Yes No Yes No Yes No
Connected ∈ NP
HamPath ∈ NP
HamPath is decidable.
There is no polynomial-time reduction from HamPath to Connected. There is no polynomial-time reduction from Connected to HamPath.
11. Consider the following pair of languages:
• DirHamPath := G G is a directed graph with a Hamiltonian path
• Acyclic := G G is a directed acyclic graph
(For concreteness, assume that in both of these languages, graphs are represented by their
adjacency matrices.) Which of the following must be true, assuming P̸=NP?
Yes No Yes No Yes No Yes No Yes No
Acyclic ∈ NP
Acyclic ∩ DirHamPath ∈ P
DirHamPath is decidable.
There is a polynomial-time reduction from DirHamPath to Acyclic. There is a polynomial-time reduction from Acyclic to DirHamPath.
CS/ECE 374 A Final Exam Study Problems Fall 2019
12. Suppose we want to prove that the following language is undecidable. AlwaysHalts := 〈M〉 M halts on every input string
Rocket J. Squirrel suggests a reduction from the standard halting language Halt:=(〈M〉,w) M haltsoninputsw.
Specifically, given a Turing machine DecideAlwaysHalts that decides AlwaysHalts, Rocky claims that the following Turing machine DecideHalt decides Halt.
DecideHalt(〈M〉,w):
Encode the following Turing machine M′:
return DecideAlwaysHalts(〈Bullwinkle〉)
Bullwinkle( x ): if M accepts w
if M rejects w accept
Which of the following statements is true for all inputs 〈M〉#w?
Yes No Yes No Yes No Yes No Yes No Yes No Yes No
If M accepts w, then M′ halts on every input string.
If M rejects w, then M′ halts on every input string.
If M diverges on w, then M′ halts on every input string.
If M accepts w, then DecideAlwaysHalts accepts 〈Bullwinkle〉.
If M rejects w, then DecideHalt rejects (〈M〉,w).
If M diverges on w, then DecideAlwaysHalts diverges on 〈Bullwinkle〉. DecideHalt decides Halt. (That is, Rocky’s reduction is correct.)
CS/ECE 374 A Final Exam Study Problems Fall 2019
13. Suppose we want to prove that the following language is undecidable. Muggle := 〈M〉 M accepts SCIENCE but rejects MAGIC
Professor Potter, your instructor in Defense Against Models of Computation and Other Dark Arts, suggests a reduction from the standard halting language
Halt:=(〈M〉,w) M haltsoninputsw.
Specifically, suppose there is a Turing machine DetectoMuggletum that decides Muggle.
Professor Potter claims that the following algorithm decides Halt.
DecideHalt(〈M〉,w):
Encode the following Turing machine:
return DetectoMuggletum(〈RubberDuck〉)
RubberDuck(x): run M on input w
if x = MAGIC return False
return True
Which of the following statements is true for all inputs 〈M〉#w?
Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No
Yes No Yes No
If M accepts w, then RubberDuck accepts SCIENCE.
If M accepts w, then RubberDuck accepts CHOCOLATE.
If M rejects w, then RubberDuck rejects MAGIC.
If M rejects w, then RubberDuck halts on every input string.
If M diverges on w, then RubberDuck rejects every input string.
If M accepts w, then DetectoMuggletum accepts 〈RubberDuck〉.
If M rejects w, then DecideHalt rejects (〈M〉,w).
If M diverges on w, then DecideHalt rejects (〈M〉,w).
DecideHalt decides the language Halt. (That is, Professor Potter’s reduction is actually correct.)
DecideHalt actually runs (or simulates) RubberDuck. Muggle is decidable.
CS/ECE 374 A Final Exam Study Problems Fall 2019
NP-hardness
1. A boolean formula is in disjunctive normal form (or DNF) if it consists of a disjunction (Or) or several terms, each of which is the conjunction (And) of one or more literals. For example, the formula
(x ∧ y ∧z)∨(y ∧z)∨(x ∧ y ∧z)
is in disjunctive normal form. DNF-Sat asks, given a boolean formula in disjunctive normal
form, whether that formula is satisfiable.
(a) Describe a polynomial-time algorithm to solve DNF-Sat. (b) What is the error in the following argument that P=NP?
Suppose we are given a boolean formula in conjunctive normal form with at most three literals per clause, and we want to know if it is satisfiable. We can use the distributive law to construct an equivalent formula in disjunctive normal form. For example,
(x∨y∨z)∧(x∨y) ⇐⇒ (x∧y)∨(y∧x)∨(z∧x)∨(z∧y)
Now we can use the algorithm from part (a) to determine, in polynomial time, whether the resulting DNF formula is satisfiable. We have just solved 3Sat in polynomial time. Since 3Sat is NP-hard, we must conclude that P=NP!
2. A relaxed 3-coloring of a graph G assigns each vertex of G one of three colors (for example, red, green, and blue), such that at most one edge in G has both endpoints the same color.
(a) Give an example of a graph that has a relaxed 3-coloring, but does not have a proper 3-coloring (where every edge has endpoints of different colors).
(b) Prove that it is NP-hard to determine whether a given graph has a relaxed 3-coloring.
3. An ultra-Hamiltonian cycle in G is a closed walk C that visits every vertex of G exactly once,
except for at most one vertex that C visits more than once.
(a) Give an example of a graph that contains a ultra-Hamiltonian cycle, but does not contain
a Hamiltonian cycle (which visits every vertex exactly once).
(b) Prove that it is NP-hard to determine whether a given graph contains a ultra-Hamiltonian cycle.
4. An infra-Hamiltonian cycle in G is a closed walk C that visits every vertex of G exactly once, except for at most one vertex that C does not visit at all.
(a) Give an example of a graph that contains a infra-Hamiltonian cycle, but does not contain a Hamiltonian cycle (which visits every vertex exactly once).
(b) Prove that it is NP-hard to determine whether a given graph contains a infra-Hamiltonian cycle.
5. A quasi-satisfying assignment for a 3CNF boolean formula Φ is an assignment of truth values to the variables such that at most one clause in Φ does not contain a true literal. Prove that it is NP-hard to determine whether a given 3CNF boolean formula has a quasi-satisfying assignment.
CS/ECE 374 A Final Exam Study Problems Fall 2019
6. A subset S of vertices in an undirected graph G is half-independent if each vertex in S is adjacent to at most one other vertex in S. Prove that finding the size of the largest half-independent set of vertices in a given undirected graph is NP-hard.
7. A subset S of vertices in an undirected graph G is sort-of-independent if if each vertex in S is adjacent to at most 374 other vertices in S. Prove that finding the size of the largest sort-of-independent set of vertices in a given undirected graph is NP-hard.
8. A subset S of vertices in an undirected graph G is almost independent if at most 374 edges in G have both endpoints in S. Prove that finding the size of the largest almost-independent set of vertices in a given undirected graph is NP-hard.
9. Let G be an undirected graph with weighted edges. A heavy Hamiltonian cycle is a cycle C that passes through each vertex of G exactly once, such that the total weight of the edges in C is more than half of the total weight of all edges in G. Prove that deciding whether a graph has a heavy Hamiltonian cycle is NP-hard.
12 7 8 3 9
A heavy Hamiltonian cycle. The cycle has total weight 34; the graph has total weight 67.
10. (a) A tonian path in a graph G is a path that goes through at least half of the vertices of G. Show that determining whether a graph has a tonian path is NP-hard.
(b) A tonian cycle in a graph G is a cycle that goes through at least half of the vertices of G. Show that determining whether a graph has a tonian cycle is NP-hard. [Hint: Use part (a). Or not.]
11. Prove that the following variants of SAT is NP-hard. [Hint: Describe reductions from 3SAT.]
(a) Given a boolean formula Φ in conjunctive normal form, where each variable appears in at most three clauses, determine whether F has a satisfying assignment. [Hint: First consider the variant where each variable appears in at most five clauses.]
(b) Given a boolean formula Φ in conjunctive normal form and given one satisfying assignment for Φ, determine whether Φ has at least one other satisfying assignment.
12. JerrySpringerandMauryPovichhavedecidednottocompetewitheachotheroverscheduling guests during the next talk-show season. There is only one set of Weird People who either host would consider having on their show. The hosts want to divide the Weird People into two (disjoint) groups: those to appear on Jerry’s show, and those to appear on Maury’s show. (Neither wants to “recycle” a guest that appeared on the other’s show.)
CS/ECE 374 A Final Exam Study Problems Fall 2019
Both Jerry and Maury have preferences about which Weird People they are particularly interested in. For example, Jerry wants to be sure to get at least one
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com