This is a quick reminder of material that you should know from your undergraduate algorithms course.
Introduction to the course. What is an algorithm? Models of computation.
Asymptotic notations. Summations.
More on summations. Recurrences: Substitution method.
Recurrences: More on the substitution method. Tree method.
More on the Tree method. Master theorem. Heaps.
More on heaps. Randomized quicksort. Worst-case expected analysis.
Analysis of randomized quicksort. Lower bounds for sorting.
Order statistics. Quickselect. Deterministic linear time selection.
Preview Test 1. Hash tables.
Test 1 Review Sheet
Covers Lectures 1-8 (Chapters 1-9 and Appendix A.) Average score 112 (Q1:17, Q2:22, Q3:22, Q4:23, Q5:17, Q6:13). [test1-sol.pdf]
More on hash tables. Balanced binary search trees.
Office hours are cancelled for today.
Augmenting data structures.
Canceled due to weather.
Use this time to catch up on the Homeworks 8-10. No lecture, due to instructor's travel.
Dynamic programming. Amortized analysis.
Potential method for amortized analysis.
Test 2 Review Sheet
Test 2 preview. Fibonacci heaps: Basic structure, insert.
Covers Lectures 9-19. Average score: 114 (Q1:21, Q2:21, Q3:22, Q4:14, Q5:17, Q6:20)
Fibonacci heaps: ExtractMin including Consolidate, DecreaseKey including cascading cuts.
Fibonacci heaps: Delete, analysis for maximum degree. Disjoint sets.
Disjoint set forests. Elementary graph algorithms.
(no votes recorded) [hw13.pdf]
Minimum spanning trees.
Shortest paths on graphs.
NP-Completeness: Decision problems. Deciding a language. Verifying a language. P and NP.
NP-Completeness: Definitions of NP-hard and NP-complete. Reductions.
Wrap up. Preview final exam. Course evaluations.
Final Exam Review Sheet
Office Hour for Final Exam Questions
9am until 11am
12:30pm. Covers Lectures 1-28, with emphasis on Lectures 21-28. Average score: 178/240 (Q1:21, Q2:18, Q3:22, Q4:14, Q5:17, Q6:20 Q7:14 Q8:19 Q9:16 Q10:14)
Final grades are posted now. I will be happy meet with any of you next week to review final exam papers for mistakes and miscalculations. As a reminder, I will politely decline any requests for grades higher than those you've earned on the exams.