Introduction to Analysis of Algorithms Final Exam Information and Practice
CS4820/5820 Fall 2021 “Due” December 16 2021
Rooms, Time, and Review for Final
� Final Exam is Thursday, December 16th 7pm in Statler 185 (possibly moved to
Barton) and online.
� A google form will be posted on Tuesday morning, where you can indicate whether
you want to take the exam online. Not filling in the form by Tuesday midnight means
you are taking the exam in-person.
� We’ll have review sessions by TAs on the 10th and the 14th. Times and locations
will be announced on Ed.
� Solutions to the practice questions will be released on Monday, Dec 13, but you can
use office hours to discuss solution with the TAs any time before the prelim.
Guidelines for the Final
The final is cumulative, covering all topics from the beginning of the course.
It will be closed book and closed notes.
In particular, the topics include
� From Prelim 1: (To review material, see the review packets from the prelim and
homeworks 1-5. New practice questions are included below.)
– Stable matching from Chapter 1.
– Greedy algorithms from Chapter 4, including unweighted interval scheduling
(and the greedy-stays-ahead proof technique), scheduling to minimize lateness
(and the exchange-argument proof technique), minimum spanning tree (Kruskal,
Prim).
– Dynamic programming from Chapter 6, including weighted interval scheduling,
knapsack, segmented least squares, sequence alignment (a.k.a. edit distance),
Bellman-Ford shortest path algorithm.
– Divide and conquer from Chapter 5, including integer multiplication, quickselect
(see also randomized algorithms), finding the closest pair of points in the plane.
– Randomized Algorithms from Section 13, including expected linear-time median
finding, finding the closest pair of points in the plane (using randomization and
hashing)
� From Prelim 2: (To review material, see the review packets from the prelim and
homeworks 6-9. New practice questions are included below.)
– Network flows from Chapter 7, including the Ford-Fulkerson max flow algorithm,
equivalence of max flows and min cuts, and network flow applications.
– NP-completeness from Chapter 8, including reductions and the problems SAT,
Independent Set, Vertex Cover, Hamiltonian Path/Cycle, TSP, Subset Sum,
and problems from the homeworks/exams.
� Since Prelim 2: (see summary and review questions below, as well as homeworks 10.)
– Computability: Turing Machines, the non-decidability of the halting problem,
reductions to show problems are undecidable, Rice’s Theorem.
– Approximation Algorithms from Chapter 11 and the notes posted, including the
greedy knapsack 2-approximation algorithm (see notes on the web site), arbi-
trarily good approximation for the knapsack problem, simple 2-approximation
algorithm for unweighted vertex cover and linear programming rounding 2-
approximation algorithm for weighted vertex cover.
� Similar to the prelim exams, you will not be tested on sections in the afore-mentioned
chapters if we did not discuss them in lecture (the course outline (linked from canvas)
shows which sections we did cover). Some topics we covered briefly, such as hashing,
and you will not be tested on such topics.
Post-Prelim 2 Topics
The questions on computability will test your understanding of Turing Machines, and your
ability to decide which problems are computable, and which are not. Topics you need to
know about:
� Turing Machine definition, equivalence of different models (e.g. multiple and single
tapes, two-way and one-way infinite tapes),
� definition of recursive and recursively enumerable sets,
� definition of decidability, showing a problem is decidable,
� the Halting Problem, and empty-string-acceptance problem,
2
� proving a problem is undecidable by reduction from an undecidable problem (e.g.
the Halting Problem) or using Rice’s Theorem.
The questions on approximation algorithms will test your ability to do the following:
� showing an algorithm may give a solution that is much worse than optimum (we gave
examples of this for knapsack and vertex cover on November 29 and December 3)
� analyze greedy methods that give a good approximation algorithm: such as knapsack
(see handout), unweighted vertex cover (lecture December 3)
� use of dynamic programming to get an arbitrarily good approximation for knapsakc
(Section 11.8)
� use linear programming and rounding, (Section 11.6)
How to study
Here are a couple of recommendations on how to review:
� Read the lecture notes or book chapter on a specific topic, and take notes to sum-
marize the key concepts. Go take a walk, and try to tell yourself (or a friend) the
problem, algorithm, and analysis that you just read from memory.
� Try solving all the homework and exam problems again without looking at the solu-
tions, including your own solutions.
� Review the comments the TAs left for your solutions, and the solutions posted on
canvas.
� Review the rubric for the homework/exam problems. These are brief summaries of
what you need to solve the problem; familiarizing yourself with them helps to get
a good understanding of what it is your answer should include and how to allocate
your time when writing your answers.
Practice Questions on Approximation Algorithms
1. Consider the Move-It-Quik truck problem: items arrive one at-a-time and the truck
weight capacity is K pounds. The loading site only has room for one truck to be
loaded at a time. Rather than planning which items should go in which truck in
3
advance, the movers just load one item at a time in whatever order they find items
to pack, disregarding their weight, until the next item wouldn’t fit. Then, they move
on to the next truck.
Consider the pseudocode for a greedy truck-loading :
Truck Loading:
c � K is the capacity remaining for the current truck
m � 1 is the number of trucks used so far.
While there is an item i with weight wi left to load:
If c ‘ wi:
// The item fits; load item i on the current truck
Set c �� c � wi
Else:
// The item won’t fit; send off the current truck
// and get a new one to load item i
Set m� � 1
Set c � K � wi
Endif
Endwhile
Return m as the total number of trucks used.
Suppose at the end of one of these moving jobs, n items with weights w1, w2, . . . , wn
are packed up in that order.
(a) Prove that the number of trucks used by this algorithm, m, is at most a factor
of 2 larger than the minimum number possible for taking the n items. That is, if
OPT denotes that minimum number of trucks possible by carefully ordering the
n items, show that m & 2OPT . Solution: First, we upper-bound how well
the optimal packing OPT can get. We know that the optimal solution cannot
pack trucks beyond their weight capacity. Let W �