CMPS 102 Final Exam Information, Spring 2020 version 1.0
The 102 Final exam will be held on Tuesday June 9 from 8:30 to 11 am (2 1/2 hours)
on Canvas. The Final will start at 8:30am.
The exam will have 4 questions, one multi-part short answer question, one greedy algo-
rithm algorithm design question, one divide and conquer algorithm design question, and one
dynamic programming algorithm design question. The three algorithm design questions are
intended to be about the difficulty of the easier homework problems and are often somewhat
related to problems you would have seen in class or on the homework.
The final exam will be comprehensive. In addition to the homework and quiz problems,
you are also responsible for the following from lecture and/or the textbook:
1. Chapter 1 (Stable matching),
2. Chapter 2 (Basic algorithm analysis, asymptotic notation, priority queues, proofs by
induction),
3. Chapter 3 (Graph definitions, Graph representations, BFS and DFS traversals and
their runtimes),
4. Chapter 5 (Divide and conquer):
• Mergesort, mergesort recurrence, merging lists
• recursion tree method of finding the (asymptotic) value of a recurrence
• bounding a recurrence with a formal proof by induction
• The common recurrence forms in Chapter 5
• Divide and Conquer example algorithms: Counting inversions; closest pair of
points in the plane; integer multiplication (Karatsuba); Matrix Multiplication
(Strassen); FFTs and their use for converting between representations of polyno-
mials.
5. Chapter 4 (Greedy algorithms)
• Examples: Interval Scheduling, Selecting breakpoints (Tesla charging stations),
Interval partitioning (classroom scheduling), Scheduling to minimize maximum
lateness, Optimal caching, Dijkstra’s Algorithm, Minimum Cost Spanning Trees
(Prim’s and Kruskal’s algorithms).
• Concepts: Greedy stays ahead, Morphing an arbitrary optimal solution into the
greedy solution, directly showing greedy is optimal (as in classroom scheduling),
finding counterexamples showing that a greedy algorithm can fail to produce an
optimal solution.
6. Chapter 6 (Dynamic Programming)
• Methodology: focus on value first. Look at solutions and try and find a ”last deci-
sion”. Find which subproblems an optimal solution contains (optimal) solutions
for, derive a recurrence for the optimal value. Envision a recursive algorithm,
add memoization for efficiency, and convert to a bottom-up iterative table-filling
algorithm. See how to trace back through the table to recover an optimal solution.
• Weighted interval scheduling (binary choice)
• Segmented least squares (multi-way choice)
• Knapsack problem (additional constraint)
• RNA secondary structure (a single choice leads to two subproblems that must be
solved, subproblems need not start at the front of the original input)
• Sequence alignment (three-way choice)
• Bellman-Ford-Moore shortest paths (consider paths in order of increasing number
of edges), negative cost edges, negative cycles, and finding/detecting negative cost
cycles.