By Sartaj Sahni
| Lecture | Content | Reading | Slides |
|---|---|---|---|
| 1 | Course overview and insertion sort. | Chapters 1 through 3. | Powerpoint |
| 2 | Insertion sort and practical complexities. | Section 3.5. | Powerpoint |
| 3 | Run-time measurement. | Chapter 4. | Powerpoint |
| 4 | Linear lists. | Sections 5.1-5.2. | Powerpoint |
| 5 | Array representation and array resizing. | Section 5.3. | Powerpoint |
| 6 | Walk through of code forArrayLinearList. | Section 5.3. | Powerpoint |
| 7 | Iterators. Linked representation of a linear list. | Sections 5.3 and 6.1. | Powerpoint |
| 8 | Walk through of code forChain. Head nodes, circular lists, doubly linked lists. | Sections 6.2 and 6.3. | Powerpoint |
| 9 | Simulated pointers and available-space lists. | Sections 7.1 and 7.2. | Powerpoint |
| 10 | Row-major and column-major indexing, and special matrices. | Sections 8.1, 8.2, and 8.3. | Powerpoint |
| 11 | Sparse matrices. | Section 8.4. | Powerpoint |
| 12 | Stacks--application to parentheses matching, towers-of-hanoi, railroad car rearrangement, and switchbox routing; array stacks. | Sections 9.1, 9.2, 9.5. | Powerpoint |
| 13 | Array and linked stacks. | Section 9.3 and 9.4. | Powerpoint |
| 14 | Nonapplicability of queues for parantheses matching, towers-of-hanoi, railroad problem with LIFO tracks, and switchbox routing. Application of queues to railroad problem with FIFO tracks, wire routing, and component labeling. Array and linked queues. | Sections 10.1-10.4, 10.5.1-10.5.3. | Powerpoint |
| 15 | Exam. | - | - |
| 16 | Dictionaries, linear list representation, and hashing. | Sections 11.1, 11.2, 11.3, and 11.5. | Powerpoint |
| 17 | Hashing and hash table design. | Section 11.5. | Powerpoint |
| 18 | LZW compression. | Section 11.6. | Powerpoint |
| 19 | Trees, binary trees, and properties. | Sections 12.1-12.3. | Powerpoint |
| 20 | Binary tree representation and operations. | Sections 12.4 and 12.5. | Powerpoint |
| 21 | Binary tree traversal methods-- preorder, inorder, postorder, level order. Reconstruction from two orders | Sections 12.6-12.8. | Powerpoint |
| 22 | Online equivalence classes. | Section 12.9.2. | Powerpoint |
| 23 | Application of priority queues to heap sort and machine scheduling. Min and max heaps. | Sections 13.1-13.3, 13.6.1, and 13.6.2. | Powerpoint |
| 24 | Initialization of min and max heaps. Height- and weight-biased leftist trees. | Sections 13.4.4 and 13.5. | Powerpoint |
| 25 | Winner and loser trees and application to k-way merging, run generation, and first-fit bin packing. | Chapter 14. | Powerpoint |
| 26 | Binary search trees and indexed binary search trees. | Sections 15.1-15.5. | Powerpoint |
| 27 | Definition of AVL trees. Graph applications and properties. | Sections 16.1, 17.1-17.3. | Powerpoint |
| 28 | Graph operations and representation. | Sections 17.4-17.7. | Powerpoint |
| 29 | Breadth-first and depth-first search. Application to path finding, connected components, and spanning trees. | Sections 17.8 and 17.9. | Powerpoint |
| 30 | Greedy method and application to bin packing, loading, and knapsack problems. | Sections 18.1, 18.2, 18.3.1, and 18.3.2. | Powerpoint |
| 31 | Exam. | - | - |
| 32 | Single source all destinations shortest paths algorithm. | Section 18.3.5. | Powerpoint |
| 33 | Kruskal's and Prim's minimum-cost spanning tree algorithms. | Section 18.3.6. | Powerpoint |
| 34 | Divide and conquer, and application to defective chessboard and min-max problem. Iterative min-max implementation. | Sections 19.1 and 19.2.1. | Powerpoint |
| 35 | Merge sort, natural merge sort, and quick sort. | Sections 19.2.2 and 19.2.3. | Powerpoint |
| 36 | Selection and closest pair of points. | Sections 19.2.4 and 19.2.5. | Powerpoint |
| 37 | Dynamic programming, 0/1 knapsack problem, recursive and iterative solutions. | Sections 20.1 and 20.2.1. | Powerpoint |
| 38 | Matrix multiplication chains, dynamic programming recurrence, recursive solution. | Section 20.2.2. | Powerpoint |
| 39 | Iterative solution to matrix multiplication chains. | Section 20.2.2. | Powerpoint |
| 40 | All pairs shortest paths. | Section 20.2.3. | Powerpoint |
| 41 | Single source shortest paths with negative edge weights. | Section 20.2.4. | Powerpoint |
| 42 | Solution space trees and backtracking. | Section 21.1. | Powerpoint |
| 43 | Branch and bound. | Section 22.1. | Powerpoint |