Computer Science 385
Design and Analysis of Algorithms
Spring 2019, Siena College
Lecture 25: Problem Set Recap; Dynamic Programming Practice; Quiz 3
Date: Friday, March 22, 2019
Agenda
- Announcements
- Academic Celebration Project: [HTML] [PDF]: next deadline is a proposal next Monday
- Problem Set 5: [PDF] continues
- Lab 8: Search Trees and Dynamic Programming back, and a couple quick thoughts about it
- Exam 2 information
- Tuesday, April 2
- Exam available 2:35-4:35 in RB 302 or 6-10 PM in RB 202
- Topics covered are those in the first 8 chapters of
Levitin, lectures up to 25 (today), labs up to 9 (next week),
and the first five problem sets
- decrease and conquer algorithms, including insertion sort, topological sort, generating permutations and subsets, fake coin problems
- divide and conquer algorithms, including mergesort, quicksort, divide and conquer 2D closest pairs
- setting up and solving recurrences, master theorem
- drawing recursive call trees
- search trees, including standard BST, AVL, 2-3 trees
- hashing (not in great detail, but know the idea and benefits/weaknesses)
- dynamic programming, comparison with recursive exhaustive search, top-down and bottom-up approaches
- using pre-sorting to improve efficiency
- There will be a strong focus on material since Exam 1, but
keep in mind that some is cumulative by nature, and in other
cases, we might want to compare more advanced solution techniques
like divide and conquer or dynamic programming with the simpler
ones we saw earlier such as brute force
- some practice questions coming soon
- You will be provided with all needed summation and log
formulas, and you will be permitted a single double-sided sheet of
handwritten notes as a reference
- That Tuesday morning's lab meeting will be extra office hours
- Problem Set 4: [PDF] recap of more problems
- More dynamic programming
- knapsack problem: both top down and bottom up example
- first look at Warshall's and Floyd's algorithms
- Quiz