COS 216: Algorithms
Spring 2022
Exam 3 information
1. Allowed materials
During the exam:- You are strongly discouraged to use the textbook, your notes, homework, and PDFs I've given you.
- You are not allowed to use other resources (Internet search, friends, etc.).
- You may only use electronic devices (computer, smart phone) to the extent of following exam logistics (below).
2. Exam content
The exam covers everything we have done, up to and including Day 27 (end of dynamic programing). While the exam is cumulative, we will focus on what was not already tested. Here are some topics we emphasized since the last exam:- divide and conquer (chapter 5)
- applications: inversions, integer multiplication
- dynamic programming (chapter 6)
- techniques: recursion, memoization, iteration, record values only and then print solution
- applications: weighted interval scheduling, subset sum, sequence alignment, shortest paths
- famous named algorithm: Bellman–Ford
- sorting
We learned quicksort since the last exam; but please use this opportunity to do a comprehensive review to get a whole picture of sorting. Review other sorting algorithms; compare and contrast them.
- algorithms: selection sort, insertion sort (Day 2), heap sort (Day 5), mergesort (Day 17), quicksort (Day 21)
- pros and cons: running time (number of comparisons), stable, in-place, few swaps, adaptive (fast for nearly sorted), etc.
As usual, please note that this document is not a contract. I may have inadvertently left something off that ends up on an exam question. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.
3. Logistics
Logistics will be identical to Exam 1; review it if you don't remember the procedure.