• Don’t panic!
CS/ECE 374 A Fall 2021 Final Exam
December 15, 2021
Directions
Copyright By PowCoder代写 加微信 powcoder
• If you brought anything except your writing implements, your two hand-written 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.
• We strongly recommend reading the entire exam before trying to solve anything. If you think a question is unclear or ambiguous, please ask for clarification as soon as possible.
• The exam has six numbered questions, each worth 10 points. (Subproblems are not necessarily worth the same number of points.)
• You have 150 minutes to write your solutions, after which you have 30 minutes to scan your solutions, convert your scan to a PDF file, and upload your PDF file to Gradescope. (Both of these times are extended if you have time accommodations through DRES.)
• Proofs are required for full credit if and only if we explicitly ask for them, using the word prove in bold italics.
• Write your answers on blank white paper using a dark pen. Please start your solution to each numbered question on a new sheet of paper.
• If you are ready to scan your solutions and there are more than 15 minutes of writing time remaining, send a private message to the host of your Zoom call (“Ready to scan”) and wait for confirmation before leaving the Zoom call.
• Gradescope will only accept PDF submissions. Please do not scan your cheat sheets or scratch paper. Please make sure your solution to each numbered problem starts on a new page of your PDF file.
• Finally, if something goes seriously wrong, send email to as soon as possible explaining the situation. If you have already finished the exam but cannot submit to Gradescope for some reason, include a complete scan of your exam as a PDF file in your email. If you are in the middle of the exam, send Jeff email, continue working until the time limit, and then send a second email with your completed exam as a PDF file. Please do not email raw photos.
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,whatisthesizeofthelargestsubsetofvertices
in G that have no edges among them?
MaxClique: GivenanundirectedgraphG,whatisthesizeofthelargestcompletesubgraphofG?
MinVertexCover: GivenanundirectedgraphG,whatisthesizeofthesmallestsubsetofvertices that touch every edge in G?
MinSetCover: GivenacollectionofsubsetsS1,S2,…,SmofasetS,whatisthesizeofthesmallest subcollection whose union is S?
MinHittingSet: GivenacollectionofsubsetsS1,S2,…,SmofasetS,whatisthesizeofthesmallest subset of S that intersects every subset Si ?
3Color: GivenanundirectedgraphG,canitsverticesbecoloredwiththreecolors,sothateveryedge touches vertices with two different colors?
HamiltonianPath: GivengraphG(eitherdirectedorundirected),isthereapathinGthatvisitsevery vertex exactly once?
HamiltonianCycle: GivenagraphG(eitherdirectedorundirected),isthereacycleinGthatvisits every vertex exactly once?
TravelingSalesman: GivenagraphG(eitherdirectedorundirected)withweightededges,whatis the minimum total weight of any Hamiltonian path/cycle in G?
LongestPath: GivenagraphG(eitherdirectedorundirected,possiblywithweightededges),whatis the length of the longest simple path in G?
SteinerTree: GivenanundirectedgraphGwithsomeoftheverticesmarked,whatistheminimum number of edges in a subtree of G that contains every marked vertex?
SubsetSum: GivenasetXofpositiveintegersandanintegerk,doesXhaveasubsetwhoseelements sum to k?
Partition: Given a set X of positive integers, can X be partitioned into two subsets with the same sum?
3Partition: GivenasetXof3npositiveintegers,canXbepartitionedintonthree-elementsubsets, all with the same sum?
IntegerLinearProgramming: GivenamatrixA∈n×dandtwovectorsb∈nandc∈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 integerpointsmax{x∈d |Ax≤b,x≥0}isempty.
Draughts: Givenann×ninternationaldraughtsconfiguration,whatisthelargestnumberofpieces that can (and therefore must) be captured in a single move?
SteamedHams: Auroraborealis?Atthistimeofyear,atthistimeofday,inthispartofthecountry, localized entirely within your kitchen? see it?
CS/ECE 374A Final Exam (December 15, 2021) Fall 2021
1. For each statement below, write “YES” if the statement is always true and “NO” otherwise, and give a brief (at most one short sentence) explanation of your answer. Assume P ̸= NP. If there is any other ambiguity or uncertainty about an answer, write “NO”. For example:
NO — Suppose x = 3 and y = 4.
3SAT can be solved in polynomial time.
NO — 3SAT is NP-hard.
If P = NP then Jeff is the Queen of England.
YES — The hypothesis is false, so the implication is true.
Read each statement very carefully; some of these are deliberately subtle!
Which of the following statements are true?
(a) The solution to the recurrence T(n) = 4T(n/2) + O(n2) is T(n) = O(n2).
(b) The solution to the recurrence T(n) = 2T(n/4) + O(n2) is T(n) = O(n2).
(c) Every directed acyclic graph contains at least one sink.
(d) Given any undirected graph G, we can compute a spanning tree of G in O(V + E) time using whatever-first search.
(e) Suppose we want to iteratively evaluate the following recurrence:
loop and decreasing j in the inner loop.
Which of the following statements are true for at least one language L ⊆ {0, 1}∗?
(f) L∗=(L∗)∗
(g) L is decidable, but L∗ is undecidable. (h) L is neither regular nor NP-hard.
(i) L is in P, and L has an infinite fooling set.
(j) The language {〈M〉 | M accepts L} is undecidable.
What(i, j) =
What(i, j − 1)
if i > n or j < 0 otherwise
What(i + 1, j)
A[i] · A[ j] + What(i + 1, j − 1)
We can fill the array What[0..n,0..n] in O(n2) time, by decreasing i in the outer
CS/ECE 374A Final Exam (December 15, 2021) Fall 2021
2. For each statement below, write “YES” if the statement is always true and “NO” otherwise, and give a brief (at most one short sentence) explanation of your answer. Assume P ̸= NP. If there is any other ambiguity or uncertainty about an answer, write “NO”.
Read each statement very carefully; some of these are deliberately tricky!
(Please remember to start your answers to this problem on a new page. Yes, this is really
just a continuation of problem 1; we split it into two problems to make grading easier.)
Consider the following pair of languages:
• Acyclic := undirected graph G G contains no cycles
• HalfInd := undirected graph G = (V, E) G has an independent set of size |V |/2
(For concreteness, assume that in both of these languages, graphs are represented by their adjacency matrices.) The language HalfInd is actually NP-hard; you do not need to prove that fact.
Which of the following statements are true, assuming P ̸= NP? (a) Acyclic is NP-hard.
(b) HalfInd\Acyclic∈P
(Recall that X \ Y is the subset of elements of X that are not in Y .)
(c) HalfInd is decidable.
(d) A polynomial-time reduction from HalfInd to Acyclic would imply P=NP.
(e) A polynomial-time reduction from Acyclic to HalfInd would imply P=NP.
Suppose there is a polynomial-time reduction from some language A over the alphabet {0, 1} to some other language B over the alphabet {0, 1}. Which of the following statements are true, assuming P ̸= NP?
(f) AisasubsetofB.
(g) IfB∈P,thenA∈P.
(h) If B is NP-hard, then A is NP-hard.
(i) If B is decidable, then A is decidable. (j) If B is regular, then A is decidable.
CS/ECE 374A Final Exam (December 15, 2021) Fall 2021
3. Suppose you are asked to tile a 2 × n grid of squares with dominos (1 × 2 rectangles). Each domino must cover exactly two grid squares, either horizontally or vertically, and each grid square must be covered by exactly one domino.
Each grid square is worth some number of points, which could be positive, negative, or zero. The value of a domino tiling is the sum of the points in squares covered by vertical dominos, minus the sum of the points in squares covered by horizontal dominos.
Describe and analyze an efficient algorithm to compute the largest possible value of a domino tiling of a given 2 × n grid. Your input is an array Points[1 .. 2, 1 .. n] of point values.
As an example, here are three domino tilings of the same 2 × 6 grid, along with their values. The third tiling is optimal; no other tiling of this grid has larger value. Thus, given this 2 × 6 grid as input, your algorithm should return the integer 16.
value=−6 value=2 value=16
4. Submit a solution to exactly one of the following problems. Don’t forget to tell us which problem you’ve chosen!
(a) Let Φ be a boolean formula in conjunctive normal form, with exactly three literals per clause (or in other words, an instance of 3Sat). Prove that it is NP-hard to decide whether Φ has a satisfying assignment in which exactly half of the variables are True.
(b) Let G = (V, E) be an arbitrary undirected graph. Recall that a proper 3-coloring of G assigns each vertex of G one of three colors—red, blue, or green—so that every edge in G has endpoints with different colors. Prove that it is NP-hard to decide whether G has a proper 3-coloring in which exactly half of the vertices are red.
(In fact, both of these problems are NP-hard, but we only want a proof for one of them.)
5. Suppose you are given a height map of a mountain, in the form of an n × n grid of evenly spaced points, each labeled with an elevation value. You can safely hike directly from any point to any neighbor immediately north, south, east, or west, but only if the elevations of those two points differ by at most ∆. (The value of ∆ depends on your hiking experience and your physical condition.)
Describe and analyze an algorithm to determine the longest hike from some point s to some other point t, where the hike consists of an uphill climb (where elevations must increase at each step) followed by a downhill climb (where elevations must decrease at each step). Your input consists of an array Elevation[1 .. n, 1 .. n] of elevation values, the starting point s, the target point t, and the parameter ∆.
5 2 –3 2 –7 3 1 –6 0 –1 4 –2
5 2 –3 2 –7 3 1 –6 0 –1 4 –2
5 2 –3 2 –7 3 1 –6 0 –1 4 –2
5 2 –3 2 –7 3 1 –6 0 –1 4 –2
CS/ECE 374A Final Exam (December 15, 2021) Fall 2021
6. Recall that a run in a string w ∈ {0, 1}∗ is a maximal substring of w whose characters are all equal. For example, the string 00011111110000 is the concatenation of three runs:
00011111110000 = 000 • 1111111 • 0000
(a) Let La denote the set of all strings in {0, 1}∗ where every 0 is followed immediately by at least one 1.
For example, La contains the strings 010111 and 1111 and the empty string ε, but does not contain either 001100 or 1111110.
• Describe a DFA or NFA that accepts La and • Give a regular expression that describes La.
(You do not need to prove that your answers are correct.)
(b) Let Lb denote the set of all strings in {0,1}∗ whose run lengths are increasing; that is, every run except the last is followed immediately by a longer run.
For example, Lb contains the strings 0110001111 and 1100000 and 000 and the empty string ε, but does not contain either 000111 or 100011.
Prove that Lb is not a regular language.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com