Topics for Unit C Exam: CS4102 Algorithms  Spring 2022
Document Version: 1.0, 4/14/2022
Overview
The Unit C Exam is on lectures and readings from March 17 through April 12 (maybe a bit at the start of April 14). The following topic list is a guide, and we may update it before the exam in response to student questions. See the slides and recordings for more details and readings associated with these topics. A basic rule we’ll try to follow is this: if it’s in the readings, but we didn’t mention it in lecture, it will not be on the exam.
Basic homeworks 1 and 2 for this unit are designed to help prepare you for the exam.
How the Exams Will Be Given and Other Rules
The Exam will first be given on paper and inclass on April 19, 2022. You will have a chance to retake the Exam (a updated version) during the final exam period if you are not satisfied with your grade.
The Exam will be closedbook, closednotes, etc. Getting information from any electronic devices is not allowed while taking an exam. It is an honor violation to communicate information about the exam to anyone who might not have yet taken it. You will sign a pledge about these rules.
Topics that might be covered on the Unit C Exam include:
 For any algorithm studied in this unit, know…
 Optimal substructure property for the problem the algorithm solves
 Time and space complexity for the algorithm
 For dynamic programming algorithms, know how to build the “table” bottomup, and also how recover the values that produced the optimal value for a given input
 Dynamic Programming (general topics)
 Good for overlapping subproblems. Good when we can’t guarantee we find best solution by solving just one subproblem.
 Finds solutions to smallest subproblems first
 Two implementation approaches: topdown with memoization, and bottomup
 For each algorithm we studied, know…
 The recursive structure of the solution in terms of its subproblems
 How to build the table from small solutions to the overall solution
 How to recover the values that led to the optimal solution from the table
 Log Cutting Problem
 Bottomup dynamic programm (DP) solution
 Matrix Chain Multiplication Problem
 What value are we optimizing, and why the order you multiply pairs matters
 Bottomup dynamic programm (DP) solution, storing values for a range of given size long diagonals in the table
 LCS Problem
 Prefixstrings as subproblems
 Definition of the LCS problem
 The cases of recursive structure
 This is one example where the slides show you a topdown version that uses memoization
 Seam Carving
 How minimum seam values are stored in the m x n table, and recursive definition used to build this from bottom up
 How to find minimum cost seam
 No questions on details of updating the table when removing a seam!
 Gerrymandering
 Be able to answer general questions about how the problem is defined
 Be able to explain the components of the recursive definition
 Know the timecomplexity and why it’s pseudopolynomial
 You do NOT need to know how optimal substructure applies to gerrymandering!

Pseudopolynomial time: what does this mean?
 Greedy Algorithms (general topics)
 Terminology: optimization problems, feasible solutions, objective function, optimal solutions, etc.
 Greedy choice property (greedy choice): what this means, and what it is for each algorithm we studied
 Compare and contrast DP and Greedy: what’s similar/shared, how different
 Why Dijkstra’s and Prim’s are greedy algorithms
 Proving a greedy algorithm correct using an exchange argument
 Coin changing
 The greedy algorithm
 Understand overall structure of its proof of correctness for a given coinset. (For a given range, what do we try to show?)
 What might make the greedy fail? Know that a DP solution with a table can be used, though you don’t need to know the details of how to implement this.
 Interval Scheduling Problems (AKA Activity Selection)
 Greedy approach for this, and proof of correctness using exchange argument
 Know how optimal substructure applies to this
 Huffman coding
 Know the problem, prefixfree codes, the optimization function
 How the greedy choice produces a smaller subproblem and lets us create a larger tree, step by step
 You won’t be asked to recreate the exchange argument proof for this, but might be asked some specific questions about how we did it and why
 Cache Replacement
 Know the problem, the inputs and their meanings, what we’re trying to minimize, our greedy choice, etc.
 We’ll be kind and not ask you questions about this one’s proof! :)
Topics that will not be covered on the exam include:
 No questions on details of updating the table when removing a seam!
 You do NOT need to know how optimal substructure applies to gerrymandering!
 No questions on the proof related to Belady cache replacement
 No questions on Seinfeld episodes or on the relative cuteness of baby ducks