| 1 | Course overview | Chapters 1 through 3. |
pdf012 pdf014 |
| 2 | Insertion sort and practical complexities. | Section 3.5. |
pdf022 pdf024 pdf026 |
| 3 | Run-time measurement. | Chapter 4. |
pdf032 pdf034 pdf036 |
| 4 | Merge sort, natural merge sort, and quick sort. | Sections 19.2.2 and 19.2.3. |
pdf352 pdf354 pdf356 |
| 5 | Greedy method and application to bin packing, loading, and knapsack problems. | Sections 18.1, 18.2, 18.3.1, and 18.3.2. |
pdf302 pdf304 pdf306 |
| 6 | Graph operations and representation. | Sections 17.4-17.7. |
pdf282 pdf284 pdf286 |
| 7 | Breadth-first and depth-first search. Application to path finding, connected components, and spanning trees. | Sections 17.8 and 17.9. |
pdf292 pdf294 pdf296 |
Middle Exam(期中考)
| 8 | All pairs shortest paths. | Section 20.2.3. |
pdf402 pdf404 pdf606 |
| 9 | Single source shortest paths with negative edge weights. | Section 20.2.4. |
pdf412 pdf414 pdf416 |
| 10 | Dynamic programming, 0/1 knapsack problem, recursive and iterative solutions. | Sections 20.1 and 20.2.1. |
pdf372 pdf374 pdf376 |
| 11 | Matrix multiplication chains, dynamic programming recurrence, recursive solution. | Section 20.2.2. |
pdf382 pdf384 pdf386 |
| 12 | Solution space trees and backtracking. | Section 21.1. |
pdf422 pdf424 pdf426 |
| 13 | Branch and bound. | Section 22.1. |
pdf432 pdf434 pdf436 |
Final Exam(期末考)