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 7-9:30pm in Statler 185
� If you need a special arrangement, you should have heard from Jordan
Staiti. If you have a conflicting exam, or have 3 exams in a 24 hour period,
you must contact me and Jordan Staiti (jas2262) by December 9.
� 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 .
(b) In part (a), you showed that if OPT is the number of trucks used in the opti-
mal solution, 2OPT is an upper bound on the number of trucks used by this
algorithm. In general, an upper bound is called “tight” if there is an instance
where the upper-bound is actually achieved: in this case, we know there can’t
possibly be a smaller upper bound. Show that this 2-optimal bound is tight:
describe how to construct a sequence of objects for any value of OPT that will
ensure that while the optimal algorithm uses OPT trucks, the Truck Loading
algorithm uses at least 2OPT �2 trucks. An example that works for some single
value of OPT but not for any OPT can get 2/4 points.
(c) Now, assume that the system has no items that are too heavy. Concretely,
assume that wi & K©3 for all i. Prove that in this case the above algorithm
satisfies a better bound of m & 1.5OPT � 1.
4
2. Consider the following expert selection problem. For a movie project you need a
bunch of different experts, from legal experts, through experts on the computer sci-
ence company cultures, etc. You have a set S of possible experts that you can hire,
but some of them are quite expensive. You need help with a set A of areas. Expert
i needs a fee of ci to be hired. The good news is that some of the experts have more
than one expertise, though no single expert has more than two skills on your list of
areas A. You would like to hire a subset I of the experts so that you have an expert
on the payroll in all areas in the set A, while minimizing the total cost.