Description
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.
General Information
Books
1) Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein.
2) Algorithm Design by Kleinberg and Tardos.
Grading Scheme
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.
Detailed Syllabus
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.