CS/ECE 374 A Fall 2019 Final Exam
December 13, 2019
Real name: NetID:
Gradescope name: Gradescope email:
Copyright By PowCoder代写 加微信 powcoder
• Don’t panic!
• If you brought anything except your writing implements and your two double-sided 81⁄2″ × 11″ cheat sheets, please put it away for the duration of the exam. In particular, please turn off and put away all medically unnecessary electronic devices.
• Please clearly print your real name, your university NetID, your Gradescope name, and your Gradescope email address in the boxes above. We will not scan this page into Gradescope.
• Please also print only the name you are using on Gradescope at the top of every page of the answer booklet, except this cover page. These are the pages we will scan into Gradescope.
• Please do not write outside the black boxes on each page; these indicate the area of the page that the scanner can actually see.
• Please read the entire exam before writing anything. Please ask for clarification if any question is unclear.
• The exam lasts 180 minutes.
• If you run out of space for an answer, continue on the back of the page, or on the blank pages at the end of this booklet, but please tell us where to look. Alternatively, feel free to tear out the blank pages and use them as scratch paper.
• As usual, answering any (sub)problem with “I don’t know” (and nothing else) is worth 25% partial credit. Yes, even for problem 1. Correct, complete, but suboptimal solutions are always worth more than 25%. A blank answer is not the same as “I don’t know”.
• Please return your cheat sheets and all scratch paper with your answer booklet.
• May the Sith be with you.
Beware of the man who works hard to learn something, learns it, and finds himself no wiser than before.
He is full of murderous resentment of people who are ignorant without having come by their ignorance the hard way.
CS/ECE 374 A Fall 2019 Final Exam Problem 1
Gradescope name:
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, mark the “No” box. For example:
Yes XNo IDK x+y=5
Yes XYes XYes
XNo IDK No IDK No IDK
3SAT can be solved in polynomial time.
Jeff is not the Queen of England.
If P = NP then Jeff is the Queen of England.
There are 40 yes/no choices altogether. Each correct choice is worth +1⁄2 point; each incorrect choice is worth −1⁄4 point; each checked “IDK” is worth +1/8 point.
(a) Which of the following statements is true for every language L ⊆ {0, 1}∗?
Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK
Yes No IDK
Yes No IDK
L∗ is non-empty.
L∗ is regular.
L∗ is decidable.
If L is NP-hard, then L is not regular.
If L is not regular, then L is undecidable. If L is context-free, then L is infinite.
L is the intersection of two regular languages if and only if L is regular. L is decidable if and only if L∗ is decidable.
L is decidable if and only if its reversal LR = {wR | w ∈ L} is decidable. (Recall that wR denotes the reversal of the string w.)
L is decidable if and only if its complement L is undecidable.
(b) Consider the following sets of undirected graphs:
• Trees is the set of all connected undirected graphs with no cycles.
• 3Color is the set of all undirected graphs that can be properly colored using at most 3 colors.
(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 IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK
Trees ⊆ 3Color
There is a polynomial-time reduction from Trees to 3Color There is a polynomial-time reduction from 3Color to Trees Trees is NP-hard.
(c) Let M be the following NFA:
Which of the following statements about M are true?
Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK
M accepts the empty string ε δ∗(s,010)={s,a,c}
ε-reach(a) = {s, a, c}
M rejects the string 11100111000 L(M)=(00)∗ +(111)∗
1 (continued)
(d) Which of the following languages over the alphabet Σ = {0, 1} are regular? Recall that #(a, w) denotes the number of times symbol a appears in string w.
Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK
The intersection of two regular languages w∈Σ∗|w|isprime
{w∈Σ∗ | #(0,w)+#(1,w)>374} {w∈Σ∗ | #(0,w)−#(1,w)>374}
The language generated by the context-free grammar S → 0S | 10S | ε (e) Which of the following languages or problems are decidable?
Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK
{〈M〉 | M accepts every string whose length is prime}
{〈M〉 | M accepts all strings in 0∗ and rejects all strings in 1∗} {〈M〉 | M is a Turing machine with at least two states}
(f) Which of the following languages or problems can be proved undecidable using Rice’s Theorem?
Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK
{〈M〉 | M accepts every string whose length is prime}
{〈M〉 | M accepts all strings in 0∗ and rejects all strings in 1∗} {〈M〉 | M is a Turing machine with at least two states}
1 (continued)
(g) Suppose we want to prove that the following language is undecidable. Marvin := 〈M〉 M rejects an infinite number of strings
Professor Prefect, your instructor in Vogon Poetry and Knowing Where Your Towel Is, suggests a reduction from the standard halting language
Halt:=(〈M〉,w) M haltsoninputsw.
Specifically, suppose there is a program ParanoidAndroid that decides Marvin. Professor Prefect
claims that the following algorithm decides Halt.
DecideHalt(〈M〉,w):
Write code for the following algorithm:
return ParanoidAndroid(〈HoopyFrood〉)
HoopyFrood( x ): run M on input w
if x = DONTPANIC return True
return False
Which of the following statements is true for all inputs (〈M〉,w)?
Yes No IDK Yes No IDK Yes No IDK Yes No IDK Yes No IDK
If M accepts w, then HoopyFrood accepts BEEBLEBROX.
If M rejects w, then HoopyFrood rejects BEEBLEBROX.
If M hangs on w, then HoopyFrood rejects DONTPANIC. ParanoidAndroid accepts 〈HoopyFrood〉.
DecideHalt decides Halt; that is, Professor Prefect’s proof is correct.
1 (continued)
CS/ECE 374 A Fall 2019 Final Exam Problem 2
Gradescope name:
You are planning a hiking trip in Jellystone National Park over winter break. You have a complete map of the park’s trails; the map indicates that some trail segments have a high risk of bear encounters. All visitors to the park are required to purchase a canister of bear repellent. You can safely traverse a high-bear-risk trail segment only by completely using up a full canister of bear repellent. The park rangers have installed refilling stations at several locations around the park, where you can refill empty canisters at no cost. The canisters themselves are expensive and heavy, so you cannot carry more than one. Because the trails are narrow, each trail segment allows traffic in only one direction.
You have converted the trail map into a directed graph G = (V, E), whose vertices represent trail intersections, and whose edges represent trail segments. A subset R ⊆ V of the vertices indicate the locations of the Repellent Refilling stations, and a subset B ⊆ E of the edges are marked as having a high risk of Bears. Your campsite appears on the map as a particular vertex s ∈ V , and the visitor center is another vertex t ∈ V .
(a) Describe and analyze an algorithm to decide if you can safely walk from your campsite s to the visitor center t. Assume there is a refill station at your camp site, and another refill station at the visitor center.
(b) Describe and analyze an algorithm to decide if you can walk safely from any refill station any other refill station. In other words, for every pair of vertices u and v in R, is there a safe path from u to v?
2 (continued)
CS/ECE 374 A Fall 2019 Final Exam Problem 3
Gradescope name:
Recall that a proper 3-coloring of a graph G assigns each vertex of G one of three colors, so that every edge of G has endpoints with different colors. A proper 3-coloring is balanced if each color is assigned to exactly the same number of vertices.
A balanced proper 3-coloring. A proper 3-coloring that is not balanced.
The Balanced3Color problem asks, given an undirected graph G, whether G has a balanced proper 3-coloring. Prove that Balanced3Color is NP-hard.
CS/ECE 374 A Fall 2019 Final Exam Problem 4
Gradescope name:
For each of the following languages, state whether the language is regular or not, and then justify your answer as follows:
• If the language is regular, either give an regular expression that describes the language, or draw/describe a DFA or NFA that accepts the language. You do not need to prove that your automaton or regular expression is correct.
• If the language is not regular, prove that the language is not regular. [Hint: Exactly one of these languages is regular.]
(a) x y x, y ∈ Σ+ and x and y are both palindromes (b) x y x, y ∈ Σ+ and x is not a palindrome
CS/ECE 374 A Fall 2019 Final Exam Problem 5
Gradescope name:
(a) Recall that a palindrome is any string that is equal to its reversal, like REDIVIDER or POOP. Describe an algorithm to find the length of the longest subsequence of a given string that is a palindrome.
(b) A double palindrome is the concatenation of two non-empty palindromes, like POOPREDIVIDER or POOPPOOP. Describe an algorithm to find the length of the longest subsequence of a given string that is a double palindrome. [Hint: Use your algorithm from part (a).]
For both algorithms, the input is an array A[1 .. n], and the output is an integer. For example, given the string MAYBEDYNAMICPROGRAMMING as input, your algorithm for part (a) should return 7 (for the palindrome subsequence NMRORMN), and your algorithm for part (b) should return 12 (for the double palindrome subsequence MAYBYAMIRORI).
CS/ECE 374 A Fall 2019 Final Exam Problem 6
Gradescope name:
Let M be an arbitrary DFA. Describe and analyze an efficient algorithm to decide whether M rejects an infinite number of strings.
(scratch paper)
(scratch paper)
(scratch paper)
SomeusefulNP-hardproblems. YouarewelcometouseanyoftheseinyourownNP-hardnessproofs,except of course for the specific problem you are trying to prove NP-hard.
CircuitSat: Givenabooleancircuit,arethereanyinputvaluesthatmakethecircuitoutputTrue?
3Sat: Givenabooleanformulainconjunctivenormalform,withexactlythreedistinctliteralsperclause,does
the formula have a satisfying assignment?
MaxIndependentSet: GivenanundirectedgraphG,whatisthesizeofthelargestsubsetofverticesinGthat have no edges among them?
MaxClique: GivenanundirectedgraphG,whatisthesizeofthelargestcompletesubgraphofG? MinVertexCover: GivenanundirectedgraphG,whatisthesizeofthesmallestsubsetofverticesthattouch
every edge in G?
MinSetCover: GivenacollectionofsubsetsS1,S2,…,Sm ofasetS,whatisthesizeofthesmallestsubcollection
whose union is S?
MinHittingSet: GivenacollectionofsubsetsS1,S2,…,SmofasetS,whatisthesizeofthesmallestsubset
of S that intersects every subset Si ?
3Color: GivenanundirectedgraphG,canitsverticesbecoloredwiththreecolors,sothateveryedgetouches
vertices with two different colors?
HamiltonianPath: GivengraphG(eitherdirectedorundirected),isthereapathinGthatvisitseveryvertex exactly once?
HamiltonianCycle: Given a graph G (either directed or undirected), is there a cycle in G that visits every vertex exactly once?
TravelingSalesman: GivenagraphG(eitherdirectedorundirected)withweightededges,whatisthemini- mum total weight of any Hamiltonian path/cycle in G?
LongestPath: GivenagraphG(eitherdirectedorundirected,possiblywithweightededges),whatisthelength of the longest simple path in G?
SteinerTree: GivenanundirectedgraphGwithsomeoftheverticesmarked,whatistheminimumnumber of edges in a subtree of G that contains every marked vertex?
SubsetSum: GivenasetXofpositiveintegersandanintegerk,doesXhaveasubsetwhoseelementssumto k?
Partition: GivenasetXofpositiveintegers,canXbepartitionedintotwosubsetswiththesamesum? 3Partition: GivenasetXof3npositiveintegers,canXbepartitionedintonthree-elementsubsets,allwith
the same sum?
IntegerLinearProgramming: Given a matrix A ∈ n×d and two vectors b ∈ n and c ∈ Zd, compute
max{c · x | Ax ≤ b, x ≥ 0, x ∈ d }.
FeasibleILP: Given a matrix A ∈ n×d and a vector b ∈ n, determine whether the set of feasible integer points
max{x ∈d |Ax ≤ b,x ≥0}isempty.
Draughts: Givenann×ninternationaldraughtsconfiguration,whatisthelargestnumberofpiecesthatcan
(and therefore must) be captured in a single move?
SuperMarioBrothers: Givenann×nSuperMarioBrotherslevel,canMarioreachthecastle?
SteamedHams: Auroraborealis?Atthistimeofyear,atthistimeofday,inthispartofthecountry,localized entirely within your kitchen? see it?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com