COS 216: Algorithms
Spring 2024
Exam 3 information
1. Logistics
- Notes and textbooks are not allowed on exams.
- Electronic devices (calculator, laptop, smart phone) are not allowed on exams.
- Since this class is scheduled within the 70-minute C4 block, you may use the entire 70 minutes.
2. Exam content
The exam covers everything we have done, up to and including Day 26 (end of dynamic sets). 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
- 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 3), heap sort (Day 6), merge sort (Day 17), quicksort (Day 21)
- pros and cons: running time (number of comparisons), stable, in-place, few swaps, adaptive (fast for nearly sorted), etc.
- data structures: abstract data types (ADTs) and common implementations, big Oh bounds of common operations
- Set ADT and Map ADT: Init, Add, Lookup (Map), Contains, Remove
- hashing
- hash table to implement Set ADT and Map ADT
- separate chaining
- open addressing: linear probing, quadratic probing, double hashing
- load factor, rehashing
- 2-3 tree
- 2-3 tree to implement Set ADT and Map ADT
- add and remove
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.