CS/ECE 374 A Spring 2018 FinalExam
May 8, 2018
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.
• Good luck! And thanks for a great semester!
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 Spring 2018 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 No 2+2=4 X
No x+y=5 X
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. TO indicate “I don’t know”, write IDK to the left of the Yes/No boxes; each IDK is worth +1/8 point.
(a) Which of the following statements is true for every language L ⊆ {0, 1}∗?
Yes No Yes No Yes No Yes No Yes No
Yes No Yes No Yes No
L is finite.
L∗ contains the empty string ε.
L∗ is decidable.
If L is regular then Σ∗ \ L∗ is regular.
If L is the intersection of two decidable languages, then L is decidable.
If L is the intersection of two undecidable languages, then L is undecid- able.
If L∗ is the complement of a regular language, then L is regular. If L is undecidable, then every fooling set for L is infinite.
L is decidable if and only if its complement L is undecidable.
(b) Which of the following statements is true for every directed graph G = (V, E)?
Yes No Yes No Yes No Yes No
Given the graph G as input, Floyd-Warshall runs in O(E3) time.
If G has at least one source and at least one sink, then G is a dag.
We can compute a spanning tree of G using whatever-first search.
If the edges of G are weighted, we can compute the shortest path from any node s to any node t in O(E log V ) time using Dijkstra’s algorithm.
(c) Which of the following languages over the alphabet {0, 1} are regular?
Yes No Yes No Yes No Yes No Yes No
{0m10n|m≥n}
{0m10n | m−n≥374}
Binary representations of all integers divisible by 374 xyyxisapalindrome
〈M〉 M accepts a finite number of non-palindromes
(d) Which of the following languages are decidable?
Yes No Yes No Yes No Yes No
Binary representations of all integers divisible by 374
xy∈{0,1}∗yxisapalindrome
〈M〉 M accepts the binary representation of every integer divisible by 374
〈M〉 M accepts a finite number of non-palindromes
The set of all regular expressions that represent the language {0,1}∗. (This is a language over the alphabet {Ø, 3, 0, 1, *, +, (, )}.)
1 (continued)
(e) Which of the following languages can be proved undecidable using Rice’s Theorem?
Yes No Yes No Yes No Yes No
〈M〉 M accepts an infinite number of strings
〈M〉 M accepts either 〈M〉 or 〈M〉R
〈M〉 M accepts 001100 but rejects 110011
〈M〉 M accepts some string w after at most |w|2 steps
(f) Suppose we want to prove that the following language is undecidable. Chalmers := 〈M〉 M accepts both STEAMED and HAMS
Professor Skinner suggests a reduction from the standard halting language Halt := 〈M〉#w M halts on inputs w.
Specifically, suppose there is a Turing machine Ch that decides Chalmers. Professor Skinner claims that the following algorithm decides Halt.
DecideHalt(〈M 〉#w):
Encode the following Turing machine:
return Ch(〈AuroraBorealis〉)
AuroraBorealis( x ):
if x =STEAMEDor x =HAMSor x =ALBANY run M on input w
return True else
return False
Which of the following statements is true for all inputs 〈M〉#w?
Yes No Yes No Yes No Yes No
If M accepts w, then AuroraBorealis accepts CLAMS.
If M rejects w, then AuroraBorealis rejects UTICA.
If M hangs on w, then AuroraBorealis accepts every input string.
If M accepts w, then Ch accepts 〈AuroraBorealis〉.
DecideHalt decides the language Halt. (That is, Professor Skinner’s reduction is actually correct.)
DecideHalt actually runs (or simulates) M .
We could have proved Chalmers is undecidable using Rice’s theorem
instead of this reduction.
1 (continued)
(g) Consider the following pair of languages:
• 3Color := G G is a 3-colorable undirected graph
• Tree := G G is a connected acyclic undirected graph
(For concreteness, assume that in both of these languages, graphs are represented by adjacency
matrices.) Which of the following must be true, assuming P̸=NP?
Yes No Yes No Yes No Yes No Yes No
Tree ∪ 3Color is NP-hard.
Tree ∩ 3Color is NP-hard.
3Color is undecidable.
There is a polynomial-time reduction from 3Color to Tree. There is a polynomial-time reduction from Tree to 3Color.
1 (continued)
CS/ECE 374 A Spring 2018 Final Exam Problem 2
Gradescope name:
A wye is an undirected graph that looks like the capital letter Y. More formally, a wye consists of three paths of equal length with one common endpoint, called the hub.
This grid graph contains a wye whose paths have length 4.
Prove that the following problem is NP-hard: Given an undirected graph G, what is the largest wye that is a subgraph of G? The three paths of the wye must not share any vertices except the hub, and they must have exactly the same length.
CS/ECE 374 A Spring 2018 Final Exam Problem 3
Gradescope name:
Fix the alphabet Σ = {0, 1}. Recall that a run in a string w ∈ Σ∗ is a maximal non-empty substring in which all symbols are equal. For example, the string 000001000111111101 consists of exactly six runs: 00000100011111110 = 00000 • 1 • 000 • 1111111 • 0 • 1.
(a) Let L be the set of all strings in Σ∗ that contains at least one run whose length is divisible by 3. For example, L contains the string 00111111000, but L does not contain the string 1000011.
Describe both a regular expression for L and a DFA that accepts L.
(b) Let L′ be the set of all strings in Σ∗ that have the same number of even-length runs and odd-length runs. For example, L′ does not contain the string 000011101, because it has three odd-length runs but only one even-length run, but L′ does contain the string 0000111011, because it has two runs of each parity.
Prove that L′ is not regular.
CS/ECE 374 A Spring 2018 Final Exam Problem 4
Gradescope name:
Suppose we want to split an array A[1 .. n] of integers into k contiguous intervals that partition the sum of the values as evenly as possible. Specifically, define the quality of such a partition as the minimum, over all k intervals, of the sum of the values in that interval; our goal is to maximize quality. Describe and analyze an algorithm to compute the maximum quality of a partition of A into k intervals, given the array A and the integer k as input.
For example, given the array A = [1,6,−1,8,0,3,3,9,8,8,7,4,9,8,9,4,8,4,8,2] and the integer k = 3 as input, your algorithm should return the integer 35, which is the quality of the following partition:
1,6,−1,8,0,3,3,9,8 8,7,4,9,8 9,4,8,4,8,2
The numbers above each interval show the sum of the values in that interval.
CS/ECE 374 A Spring 2018 Final Exam Problem 5
Gradescope name:
(a) Fix the alphabet Σ = {0, 1}. Describe and analyze an efficient algorithm for the following problem: Given a DFA M over Σ, does M reject any string? Equivalently, is L(M) ̸= Σ∗?
(b) Recall from Homework 10 that the corresponding problem for NFAs is NP-hard. But any NFA can be transformed into equivalent DFA using the incremental subset construction. So why doesn’t your algorithm from part (a) imply that P=NP?
CS/ECE 374 A Spring 2018 Final Exam Problem 6
Gradescope name:
A number maze is an n × n grid of positive integers. A token starts in the upper left corner; your goal is to move the token to the lower-right corner. On each turn, you are allowed to move the token up, down, left, or right; the distance you may move the token is determined by the number on its current square. For example, if the token is on a square labeled 3, then you may move the token three steps up, three steps down, three steps left, or three steps right. However, you are never allowed to move the token off the edge of the board.
Describe and analyze an efficient algorithm that either returns the minimum number of moves required to solve a given number maze, or correctly reports that the maze has no solution.
35746 35746 53153 53153 28314 28314 45723 45723 3132 3132
A 5 × 5 number maze that can be solved in eight moves.
(scratch paper)
(scratch paper)
(scratch paper)
(scratch paper)
Some useful NP-hard problems. You are welcome to use any of these in your own NP-hardness proofs, except of course for the specific problem you are trying to prove NP-hard.
CircuitSat: Given a boolean circuit, are there any input values that make the circuit output True?
3Sat: Given a boolean formula in conjunctive normal form, with exactly three distinct literals per clause, does
the formula have a satisfying assignment?
MaxIndependentSet: Given an undirected graph G, what is the size of the largest subset of vertices in G that have no edges among them?
MaxClique: Given an undirected graph G, what is the size of the largest complete subgraph of G? MinVertexCover: Given an undirected graph G, what is the size of the smallest subset of vertices that
touch every edge in G?
MinSetCover: Given a collection of subsets S1, S2, . . . , Sm of a set S, what is the size of the smallest subcol-
lection whose union is S?
MinHittingSet: Given a collection of subsets S1, S2, . . . , Sm of a set S, what is the size of the smallest subset
of S that intersects every subset Si?
3Color: Given an undirected graph G, can its vertices be colored with three colors, so that every edge
touches vertices with two different colors?
HamiltonianPath: Given graph G (either directed or undirected), is there a path in G that visits every vertex exactly once?
HamiltonianCycle: Given a graph G (either directed or undirected), is there a cycle in G that visits every vertex exactly once?
TravelingSalesman: Given a graph G (either directed or undirected) with weighted edges, what is the minimum total weight of any Hamiltonian path/cycle in G?
LongestPath: Given a graph G (either directed or undirected, possibly with weighted edges), what is the length of the longest simple path in G?
SteinerTree: Given an undirected graph G with some of the vertices marked, what is the minimum number of edges in a subtree of G that contains every marked vertex?
SubsetSum: Given a set X of positive integers and an integer k, does X have a subset whose elements sum to k?
Partition: Given a set X of positive integers, can X be partitioned into two subsets with the same sum? 3Partition: Given a set X of 3n positive integers, can X be partitioned into n three-element subsets, all
with 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
pointsmax{x∈d |Ax≤b,x≥0}isempty.
Draughts: Given an n × n international draughts configuration, what is the largest number of pieces that
can (and therefore must) be captured in a single move?
SuperMarioBrothers: Given an n × n Super Mario Brothers level, can Mario reach the castle?
SteamedHams: Aurora borealis? At this time of year, at this time of day, in this part of the country, localized entirely within your kitchen? see it?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com