| 26th Aug, 2008 | Discussed syllabus, Introduction to algorithms, worstcase vs Average case |
| 28th Aug, 2008 | Asymptotics: Big O, Big Omega, Theta; limit method. Pretest |
|
| 02nd Sept, 2008 | Analysis of Algorithms: Nonrecursive using summation |
| 04th Sept, 2008 | Analysis of Algorithms: Recursive using recurrences. Discrete math: Induction |
|
| 09th Sept, 2008 | Bruteforce
Algorithms: Selection sort, Bubble sort, String matching, closest pair, convex hull. Discrete math: Induction cont. |
| 11th Sept, 2008 | Bruteforce
Algorithms: Exhaustive Search, Divide and Conquer: Master theorm. Discrete math: Inclusion-Exclusion |
|
| 16th Sept, 2008 | Divide and Conquer: Mergesort, Quicksort, Binary search. Quiz 1 |
| 18th Sept, 2008 | Integer Multiplication, Strassens Matrix Multiplication, Closest Pair and Convex Hull |
|
|
23rd Sept, 2008 | Decrease and Conquer; Insertion sort, graph representations, DFS. |
| 25th Sept, 2008 | BFS, Topological sorting, Generating permutations and subsets. |
|
| 30th Sept, 2008 | Euclids Algorithm, Median finding, Gaussian Elimination |
| 02nd Oct, 2008 | Application of Gaussian Elimination, LU decomposition, Finding inverse of a matrix, Quiz 2 |
|
| 07th Oct, 2008 | Balanced BSTs: AVL tree |
| 09th Oct, 2008 | Greedy Algorithms: Prims and
Kruskals MST algorithms, Huffman Coding (Lecturer: Raghu Tewari) |
|
| 14th Oct, 2008 | 2-3 trees, Heaps and Heap sorting |
| 16th Oct, 2008 | Midterm | <>
|
| 21st Oct, 2008 | Fall Break |
| 23rd Oct, 2008 | String Matching : Horspools Algorithm and Intro to BM algorithm |
|
| 28th Oct, 2008 | Boyer Moore Cont. Dynamic Programming Floyd Warshal All Pairs Shortest Path |
| 30th Oct, 2008 | Dynamic Programming: Optimal Binary Search Trees |
|
| 04th Nov, 2008 | Introduction to Linear Programming
|
| 06th Nov, 2008 |
LP cont: Simplex Algorithm
|
|
| 11th Nov, 2008 | Network Flows; Ford Fulkerson
|
| 13th Nov, 2008 |
Ford Fulkerson cont; Matching using flows.
|
|
| 18th Nov, 2008 |
Game day
|
| 20th Nov, 2008 |
Theory of NP-completeness
|
|
| 25th Nov, 2008 |
Theory of NP-completeness
|
| 27th Nov, 2008 |
Thanks Giving
|
|
| 02nd Dec, 2008 |
Approximation Algorithms
|
| 04th Nov, 2008 |
Finite Automata
|
|