CS/ECE 374 A (Spring 2022) Conflict Midterm Exam 2
Instructions:
Date/Time: April 12 Tuesday 7:00pm–9:30pm Central Time.
Except for your one double-sided handwritten 8.5′′ × 11′′ cheat sheet, exams are closed- everything. In particular: No medically unnecessarily electronic devices are allowed in exams, including smart watches and headphones/earbuds.
Copyright By PowCoder代写 加微信 powcoder
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 are not allowed 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 have two hours (i.e., 120 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 for each midterm precisely at 9:30pm. 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 9:00pm.
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 9:00pm, 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 and the proctor 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 and the proctor, 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 course’s, the department’s, and the university’s academic in- tegrity policies.
Avoid the deadly sins. Write complete solutions, not examples. Declare all your variables. Write concisely and precisely.
Good luck!
1. [28 pts] Short questions.
(a) [6 pts] Give an asymptotically tight solution to the following recurrence:
3T(⌊n/2⌋) + n3/2 if n ≥ 2022 T(n) = 374 if n < 2022.
Justify your answer.
(b) [3 pts] True or False: quicksort is always faster than mergesort. Briefly justify your answer.
(c) [3 pts] Consider the following pseudocode to compute the Fibonacci number Fn:
1. 2. 3. 4.
when we take into account the bit complexity of the numbers? Justify your answer.
(e) [3 pts] Given an undirected graph G = (V,E), consider a BFS tree T. True or False: There cannot be an edge between a vertex at level i to a vertex with level at i + 3 of the tree T . If true, justify your answer; if false, give a counterexample.
(f) [3 pts] For a DAG G with n vertices, what is the minimum number of strongly connected components that G can have as a function of n? Explain.
(g) [3 pts] True or False: In an undirected graph G where every vertex has degree at least two, G must have a cycle. Justify your answer.
(h) [4 pts] Which algorithm from class gives the most efficient solution to the all-pairs shortest paths (APSP) problem in the case when the input graph has m = n3/2 edges, and all edges have positive weights? (Here, n denotes the number of vertices.) Justify your answer.
2. [20 pts] We are given a list of n exam scores ⟨a1, . . . , an⟩; the list is not sorted. We are also given a value S. We want to find the smallest k such that the sum of the top k scores is at least S.
For example, for ⟨51, 93, 62, 100, 31, 77, 85, 49⟩ and S = 275, then the answer is k = 3, since the top 3 scores 100,93,85 sum to 278, which is greater than S.
Describe an algorithm to solve this problem in strictly better than O(nlogn) time. Give pseudocode using recursion, and analyze its running time using a recurrence. You may use the linear-time median finding algorithm from class as a subroutine.
X=0,Y=1 fori=2tondo
Z=X,X=Y,Y =Z+Y return Y
is the running time as a function of n, assuming that arithmetic operations take (d) [3 pts] In the same pseudocode as (c), what is the running time as a function of n,
constant time?
3. [28 pts] Consider the following problem:
Given a sequence of points ⟨p1,...,pn⟩ in two dimensions and a value L, find a subsequence ⟨pj1,...,pjm⟩ (with j1 < j2 < ··· < jm) that maximizes the length m subject to the constraint that d(pji,pji+1) ≤ L for all i ∈ {1,...,m − 1}. (Here, d(p,q) denotes the Euclidean distance between p and q, which is computable in O(1) time.)
Consider the following dynamic programming approach. Define the following subproblems: for each i ∈ {0,...,m} and j ∈ {0,...,n}, let C(i) be the length of the longest subsequence of ⟨pi, . . . , pn⟩ that starts at pi and satisfies the above distance constraint.
We have the following recursive formula: for each i ∈ {1, . . . , m},
C(i)=max 1, max (C(j)+1) . j∈{i+1,...,n} such that d(pi,pj)≤L
(You may assume correctness of the above formula without proof.)
(a) [15 pts] Write pseudocode to solve the problem using the above formula. Your pseu- docode should output the length of the longest subsequence of the original problem (you are not required to output the optimal subsequence itself). Analyze the running time of your pseudocode as a function of n (it must run in polynomial time).
(b) [13 pts] Consider the following modified problem:
Given a sequence of points ⟨p1,...,pn⟩ in two dimensions, a value L, and an
integer r, find a subsequence ⟨pj1,...,pjm⟩ (with j1 < j2 < ··· < jm) that
maximizes m−1 d(pj ,pj ), such that |{i ∈ {1,...,m − 1} : d(pj ,pj ) >
i=1 i i+1 i i+1
Describe a dynamic programming algorithm to solve this modified problem, i.e., give a new definition of subproblems, give recursive formulas (including base cases, and how to obtain the optimal value), and specify the evaluation order. You do not need to give pseudocode for this part of the question (and you do not need to give justifications of your formula if it is clear enough). Analyze the running time of your algorithm as a function of n and L.
[Hint: you may want to add one more parameter to C(·), i.e., use a two-dimensional table.]
4. [24 pts]
(a) [9 pts] We are given a DAG G with n vertices and m edges, where each edge is colored
red or blue. We are also given two vertices s and t.
We want to decide whether there is a path from s to t such that at least 25%
of the edges in the walk are red.
Describe an efficient solution to this problem by applying a known algorithm. Bound the running time.
[Hint: if it is helpful, perhaps warm up with a variant of the problem with 25% changed to 50%.]
(b) [15 pts] We are given a directed graph G with n vertices and m edges. We are also given two vertices s and t, where each vertex (not edge) is colored red or blue.
We want to compute a walk from s to t that has strictly more red vertices than blue vertices, while minimizing the total number of red vertices.
Describe an efficient solution to this problem by constructing a new graph and applying a known algorithm. Remember to clearly define the vertices and edges of your new graph, and analyze the total running time.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com