CS/ECE 374 A (Spring 2022)
Algorithm代写 – 这是一个关于Algorithm的题目, 主要考察了关于Algorithm的内容,是一个比较经典的题目, 涉及了Algorithm等代写方面
Final Exam
Instructions:
Date/Time: May 12 Thursday 8:00am11:00am Central Time.
Except for your two double-sided handwritten 8. 5 11 cheat sheets, exams areclosed-
everything. In particular: No medically unnecessarily electronic devices are allowed in
exams, including smart watches and headphones/earbuds.
You will write your solutions on paper, scan your solutions using a scanning app, convert
your scans to PDF, and upload the PDF to Gradescope. (You arenotallowed to write
your solutions on tablets, unlike in some past semesters.) Gradescope will only accept PDF
submissions. Please make sure your solution to each numbered problem starts on a new page
of your submitted PDF file. Please do not scan your cheat sheets or scratch paper.
You havetwo and a half hours (i.e., 150 minutes)to write your solutions. We are
providing 30 minutes at the end of each exam period for students to scan and upload their
exams, and to deal with any unexpected technical difficulties that may arise. Gradescope
will stop accepting submissions precisely at 11:00am. We will not accept submissions after
the Gradescope deadline. All work on the exam must stop 30 minutes before the
Gradescope deadline, i.e., at 10:30am.
Please make sure that your scans are clear and easy to read. We very strongly recommend
that you write with black ink on unlined white paper. Submissions consisting of raw photos
or low-quality scans will be penalized.
If you are ready to scan your solutions before 10:30am, send a private message to the host of
your Zoom call (Ready to scan) and wait for confirmation before leaving the Zoom call.
If something goes seriously wrong during the exam, send email to Timothy ([email protected])
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 email to Timothy, 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.
You are reminded about the courses, the departments, and the universitys academic in-
tegrity policies.
Avoid the deadly sins. Write complete solutions, not examples. Declare all your variables.
Write concisely and precisely.
Good luck!
- [22 pts] True or False questions.
(a) [2 pts] True or False: The language{x 1 x:x { 0 , 1 }}is regular. Justification is not
necessary.
(b) [3 pts] True or False: The language generated by the following context-free grammar
is precisely{x 1 x:x{ 0 , 1 }is a palindrome}:
S A 1 A
A 0 A 0 | 1 A 1 || 0 | 1
Briefly justify your answer.
(c) [3 pts] Suppose that Algorithm A has running time (n^2 ), and Algorithm B has running
time satisfying the recurrenceTB(n) = 3TB(n/2) + 374nwith base caseTB(1) = 2022.
True or False: Algorithm B is faster than Algorithm A for a sufficiently largen. Briefly
justify your answer.
(d) [3 pts] True or False: If there is a polynomial-time reduction from Problem A to
Problem B, and Problem B is NP-complete, then Problem A is NP-complete. Briefly
justify your answer.
(e) [3 pts] Assume P 6 = NP. True or False: Given an undirected weighted graphGand a
value`, the problem of deciding whetherGcontains a tree that uses all the vertices and
has total weight at most`is NP-complete. Briefly justify your answer.
(f) [3 pts] True or False: For every languageL, ifLis undecidable, then the complement
ofLis decidable. Briefly justify your answer.
(g) [2 pts] True or False: The language
{M: the Turing machineMaccepts exactly two palindromes of each length}
is decidable. (Here,Mdenotes an encoding ofM.) Justification is not necessary.
(h) [3 pts] True or False: For every languageL, ifLis finite, thenLis decidable. Briefly
justify your answer.
- [20 pts] Automata and graph algorithms.
(a) [5 pts] (Easy) In the NFAMshown, give a string accepted byMthat has strictly
fewer 0s than 1s.
ss a b
c
0 0 0
1 1
f
e d
0,
0
(^0) 0 0 (b) [10 pts] More generally, suppose we are given an NFAM= (,Q,s,,A), with alphabet ={ 0 , 1 }, a setQofnstates, a start statesQ, a transition function:Q{ 0 , 1 ,} 2 Q, and accepting statesA Q. We want to decide whether there exists a string accepted byMthat has strictly fewer 0s than 1s. Give an efficient algorithm to solve this problem, by constructing a graph and using the BellmanFord algorithm. Remember to define the vertices and edges and weights of your graph precisely. Analyze the running time as a function ofn. Note: you may use the following known fact: in a weighted graph where negative edge weights are allowed, there is a version of the BellmanFord algorithm (with the same running time as the original) that computes the shortest-path distanced[s,v] from a source vertexsto every vertexv, where the distanced[s,v] is defined asif there is a walk fromstovthat contains a negative-weight cycle. Also, you may assume that BellmanFord can handle graphs that may have self-loops and parallel edges. (c) [5 pts] Given an NFAMwithnstates, we want to decide whether there exists a string that isnotaccepted byMand has strictly fewer 0s than 1s. Give a (not necessarily efficient) algorithm to solve this problem. Analyze the running time as a function ofn. Hint: Use part (b)^1 and known automata constructions.
- [16 pts] Dynamic programming.We have three types of toys:n 1 toys of valuec 1 ,n 2 toys of valuec 2 , andn 3 toys of valuec 3. We are also given a positive integerH. (You may assume that the given valuesc 1 ,c 2 ,c 3 are positive integers at mostH.) We would like to put the toys in gift bags, maximizing the number of bags, such that each gift bag has value at leastH. In order to develop a dynamic programming algorithm for this problem, we define the following subproblems: Forin 1 ,jn 2 ,kn 3 , andhH, letf(i,j,k,h) be the maximum number of bags that can be created fromitoys of valuec 1 ,jtoys of valuec 2 , andktoys of valuec 3 , such that the first bag has value at leasthand each of the other bags has value at leastH. (In other words, think of the first bag as already pre-loaded with valueHh.) The answer we want isf(n 1 ,n 2 ,n 3 ,H).
(^1) In multi-part questions, even if you are unable to do part (b) correctly, you can still do part (c) by assuming the result from part (b).
(a) [10 pts] Give a recursive formula forf. Remember to include appropriate base cases,
and briefly justify your answer.
(b) [3 pts] Specify a valid evaluation order for your formula. (Pseudocode is not necessary.)
(c) [3 pts] Bound the running time needed to computef(n 1 ,n 2 ,n 3 ,H), as a function of
n 1 ,n 2 ,n 3 ,H. Briefly justify your answer.
- [21 pts] Greedy algorithms. Consider the following problem: We are given a setSofn intervals{[a 1 ,b 1 ],…,[an,bn]}and an additional interval [A,B]. (You may assume that all theais andbis are distinct.) We want to choose a subsetTofSwith the smallest number of intervals such that the union of the intervals inTcover [A,B]. Example: forS = {[1,8],[2,7],[6,20],[10,30],[18,36]} and [A,B] = [5,35], one optimal solution isT={[2,7],[6,20],[18,36]}, which uses 3 intervals and has union [2,36] which covers [5,35]. (This is not the only optimal solution; there may be other solutions using the same number of intervals.)
(a) [5 pts] (Easy) Consider the following greedy strategy: select the interval which covers
the longest length of the uncovered portion of [A,B]; then remove this interval, and
repeat until all of [A,B] is covered. Give a counterexample showing that this algorithm
does not always give an optimal solution.
(b) [8 pts] Consider an optimal solutionT. Consider the interval [ai,bi] fromSwith the
largestbisuch thataiAbi. Prove that ifTdoes not use the interval [ai,bi], then
we can modifyTto get another optimal solution that uses [ai,bi].
(c) [8 pts] (Easy) Using part (b),^2 describe a correct greedy algorithm to solve the problem.
Analyze the running time. (There is no need to prove correctness, since it should follow
from (b).)
- [21 pts] NP-completeness.Consider the following problemAmerican-Ham-Cycle:
Input: a directed graphGwhere each edge is colored red, white, or blue, and the
number of verticesnis divisible by 3.
Output: yes iff there exists a cycleCsuch thatCvisits every vertex inGexactly
once, and the colors of the edges alongCalternate according to the pattern red-
white-blue-red-white-blue-(i.e., thei-th edge inCis red ifi1 mod 3, white
ifi2 mod 3, and blue ifi0 mod 3).
(a) [5 pts] (Easy) Prove thatAmerican-Ham-Cycleis in NP.
Note: all you need to do is to state what is the certificate, and what is the condition to
verify, and the time needed for the verification procedure.
(^2) See earlier footnote.
(b) [16 pts] Prove thatAmerican-Ham-Cycleis NP-hard.
Note: you may use the fact that the standardHamiltonian-Cycleproblem is NP-
complete (where the input is a directed graphH, and the output is yes iff there exists
a cycle that visits every vertex ofH exactly once). Partial credit may be given for
following the format and main steps of an NP-hardness proof (specifying the direction
of reduction, indicating what is given and what you are constructing, and what it means
for the reduction to be correct, etc.).