CS/ECE 374 A (Spring 2022) Midterm Exam 2
Instructions:
Date/Time: April 11 Monday 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 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 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⌋)+n+4n2 ifn≥374 T(n) = 2022 if n < 374.
Justify your answer.
(b) [3 pts] True or False: The median-of-medians-of-5 algorithm given in class is faster than mergesort, when the input size is sufficiently large. Briefly justify your answer.
(c) [3 pts] Consider the following pseudocode to compute the number 374n:
2. fori=1tondo 3. X = 374 ∗ X 4. return X
What is the running time as a function of n, assuming that arithmetic operations take constant time?
(d) [3 pts] In the same pseudocode as (c), what is the running time as a function of n, when we take into account the bit complexity of the numbers? Justify your answer.
(e) [3 pts] Given a directed graph G = (V,E), consider a DFS tree T. True or False: if (u,v) ∈ E, then the finishing time for u must be greater than the finishing time for v. If true, justify your answer; if false, give a counterexample.
(f) [3 pts] Answer the same question as (e) but for a DAG G.
(g) [3 pts] True or False: In a directed graph G where every vertex has out-degree at least
one, 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 is sparse and has m = O(n) edges, and all edges have weight 1? (Here, n denotes the number of vertices.) Justify your answer.
2. [20 pts] We are given an array A of n numbers ⟨A[1],...,A[n]⟩, where n is a power of 2. We want to perform a perfect split, i.e., change the array to the following:
A[1],A[3],A[5],...,A[n−1],A[2],A[4],A[6],...,A[n].
For example, if the array initially contains ⟨3, 11, 2, 9, 100, 1, 25, 5⟩, it should contain
⟨3, 2, 100, 25, 11, 9, 1, 5⟩ at the end.
Now, the problem can easily be solved in O(n) time by copying to an extra array of O(n) size, and then copying back. However, in this question, we want an algorithm that is both time-efficient and space-efficient.
Describe a divide-and-conquer algorithm to solve this problem using just O(1) (or O(log n)) extra space. Give pseudocode using recursion, and analyze its running time using a recurrence. The running time should be strictly better than O(n2) to receive full credit.
3. [28 pts] For a sequence ⟨b1,...,bm⟩, we say that position i is an up-turn iff i ≥ 2 and bi >bi−1,andpositioniisadown-turn iffi≥2andbi
max (C(j,k)+1) j∈{i+1,…,n} such that aj