Sessions Held By: Swaminathan Sankararaman
| Session Index | Date | Topics Covered |
|---|---|---|
| 1 | 08/29/2008 | Perturbation method for finding closed form of summation(Example 12 from Lecture Notes), Induction Proof(Proof of closed form for Example 12) |
| 2 | 09/05/2008 | Brief Lectura/Unix Tutorial, Finding closed form of Recurrence Relation(Example 17 from Lecture Notes), Example Algorithm(Fibonacci Numbers, both Iterative and Recursive) with Analysis of its Running Time |
| 3 | 09/12/2008 | Example Algorithms(Prefix-Sum and Maximum Subsequence in Arrays - both quadratic and linear algorithms for each) with Analysis, Implementation of Stacks using 2 Queues (Problem C-2.3 in Text) |
| 4 | 09/19/2008 | Huffman Tree example, TreeSort using BST(Example 46 from lecture notes) |
| 5 | 09/26/2008 | Examples 48 and 50 from Lecture Notes, Review of Recurrence Relations(Exercise 1a from Handout) |
| 6 | 10/03/2008 | Hashing(Examples 53 from lecture notes and R-2.20 from Textbook), Review of Question 2 from Midterm review exercises |
| 7 | 10/10/2008 | Double Hashing Example, Heap Example(Insertion and Deletion) |
| 8 | 10/17/2008 | Application of Union/Find(Finding connected components in a graph), BFS and DFS using Queue and Stack respectively, Topological Sort Example |
| 9 | 10/24/2008 | Example of Dijkstra's Algorithm, Overview of Correctness Proof of Dijkstra, Retrieval of Shortest Paths in Dijkstra(Problem 11 from Lecture Notes), Example of Floyd's Algorithm |
| 10 | 10/31/2008 | Kruskal's Algorithm Example(11(d) from Sample Questions for Midterm II, application of Union/Find to Kruskal's algorithm), Application of MST for Euclidean Traveling Salesman Problem(Prim's Algorithm Example for Euclidean MST), Question 8 from Sample Questions for Midterm II |
| 11 | 11/14/2008 | QuickSort Example, Issues with Selection of Pivot in QuickSort |
| 12 | 11/21/2008 | Radix Sort Example, Shell Sort example using Hibbard's method, Trie Example(Example 79 from Lecture Notes) with illustration of Radix Sort using Tries |