This class is designed to introduce the students basic algorithm design techniques. In the first a third of the class incremental algorithm design, divide and conquer paradigm, probabilistic analysis will be discussed through well-known sorting algorithms. In the remaining part of the class greedy algorithms, dynamic programming, network flows, NP-completeness, linear programming and a brief introduction to approximation algorithms will be covered.
1) Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
2) Algorithm Design by Kleinberg and Tardos.
Each midterm (there are two of them) will be worth at least 300 points, the final will be worth at least 400 points, homework assignment and pop quizzes will be worth at least 300 points in total.
The total amount of points collected in midterms, final, homework and quizzes will determine your letter grade.
You need to collect at least 900 points for AA, 850 points for BA, 800 points for BB, 750 points for CB, 700 points for CC, 650 points for DC, and 600 points for DD.
Lecture 1: Definition of Computational Problems, Instances, Countable vs. Uncountable Sets, Dovetailing, Diagonalization.
Lecture 2: Finite State Machines, Universal Model of Computation.
Lecture 3: Insertion Sort and Algorithm Analysis.
Lecture 4: Divide and Conquer Paradigm via Merge Sort, Growth of Functions and Asymptotic Notations.
Lecture 5: Solving Asymptotic Recurrences.
Lecture 6: Heaps, Priority Queues and Heapsort.
Lecture 7: Probabilistic Analysis.
Lecture 8: Quicksort and Randomized Quicksort.
Lecture 9: Select and Randomized Select.
Lecture 10: Linear Time Sorting Algorithms.
Lecture 11: Stable Matching Problem.
Lecture 12: Graphs.