| 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 for ArrayLinearList. |
Section 5.3. |
Powerpoint
|
| 7 |
Iterators. Linked representation of a linear list. |
Sections 5.3 and 6.1. |
Powerpoint
|
| 8 |
Walk through of code for Chain. 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 |
No comments :
Post a Comment