CSC 545 Final Exam 

CSC 545 Final Exam 
Name
Instructions This exam consists of a single problem worth 100 points. From Problems (1)–(3),
choose one. (If you do more than one problem, only one will be graded.)
In general, when asked to design an algorithm, you should:
(a) describe your algorithm using prose and pictures,
(b) argue that your algorithm is correct, and
(c) analyze its running time.
Pseudocode is not required.
During this take-home exam, the only resources you are allowed to use are: your personal
course notes, the course handouts, the textbook, and the videos of recorded lectures from this course.
Individual work is required. Use of any resource in preparing your answers must be cited.
You must submit your answers on Gradescope (at www.gradescope.com) for the course CSC 545
by 11:59pm MST on Wednesday, May 11. Upload a single PDF file containing your submission,
and be sure to mark which pages of your submission correspond to which problem. If you write
your answers by hand on paper, use an application to scan your pages such as CamScanner (a free
smartphone app).
I will be available online through Zoom during 3:30–4:30pm MST to answer questions concerning
the exam at:
https://arizona.zoom.us/j/5128057331
Please only enter the waiting room if you have a question about the exam.
Good luck!
2
(1) (Greedy algorithms) (100 points) Given a list x1, x2, . . . , xn of distinct real numbers,
and another list y1, y2, . . . , yn of distinct real numbers, reorder the xi
into a new list xi
0
,
and reorder the yi
into a new list yi
0
, so as to
minimize max
1 ≤ i ≤ n
 
 
 xi
0 − yi
0
 
 
 .
Design an efficient greedy algorithm that finds an optimal solution, analyze its running
time, and prove that it is correct.
(Note: For your correctness proof, be sure to prove a greedy augmentation lemma.)
(2) (Amortized algorithms) (100 points) Suppose we want to support a balanced search
tree data structure that does automatic backup according to the following scheme. After
executing each search tree operation, we check whether at least n operations on the tree
have elapsed since the last backup was performed, where n is the current size of the tree.
If this many operations have elapsed, a backup is performed by writing a copy of the entire
tree to a file.
Show how to implement automatic backup of balanced search trees so that all tree
operations, including those that cause backups to occur, run in O(log n) amortized time.
(Hint: Use the accounting method in your analysis.)
(3) (Graph algorithms) (100 points) Given an undirected graph G = (V, E), a cloak for G
is an edge subset C ⊆ E such that every vertex in V is touched by some edge in C. The
minimum cloak problem is, given graph G, to find a cloak C of minimum cardinality |C|.
Design an efficient graph algorithm that, given G, finds a cloak for G of minimum
cardinality. You may assume that every vertex in graph G is touched by some edge, so that
a cloak always exists.
(Note: Be sure to prove that your algorithm finds an optimal cloak.)