 |
Lecture 1 and 2 - Programming Style (also known as 學校裏沒教的事). Please download
the following document.
programming_style |
| Lecture 3 and 4 - Dynamic programming
 | Fibonacci number [Skiena] pp. 54. |
| Partition [Skiena] pp. 56. |
| String matching [Skiena] pp. 60 |
| Longest increasing sequence [Skiena] pp. 62. |
| Minimum weight triangulation [Skiena] pp. 64. |
| Matrix multiplication [Cormen] pp. 302. |
| Longest common subsequence [Cormen] pp. 312. |
| One-direction traveling salesman [呂品] |
| Shortest path in matrix [呂品] |
| Computer and boxes. (Problem C in
this document). |
| Fast food ACM online-judge
662. |
| Algebraic problem (大乙2002) |
| Fast and slow talk (大乙2002) |
|
| Lecture 5 - Greedy method
| Activity selection problem. [Cormen] pp. 329. |
| Fractional knapsack problem [Cormen] pp. 335. |
| As-few-stops-as-possible problem. [Cormen] pp. 337. |
| Hoffman code [Cormen] pp. 337. |
| Minimum sum of pairs problem. [台大博士班資格考]. |
| Coin-changing problem [Cormen] pp. 353. |
| Dijkstra's single source shortest path algorithm. [Cormen] pp. 527. |
| Kruskal's minimum spanning tree algorithm. [Cormen] pp. 504. |
| Job scheduling with deadlines [大甲2003] |
| Minimal Coverage [ACM
10020] |
| Advertisement [ACM
10148] |
|
| Lecture 6 and 7 - Divide and Conquer
| Fast Exponentiation [Skiena] pp. 75. |
| Big Mod [ACM 374] |
| Binary search [Skiena] pp. 76. |
| Quicksort. |
| Construct a binary tree from its inorder and preorder sequences. [ACM
536] |
| Tower of Hanoi [ACM 254] |
| L-shaped tiling problem. [C2003
homework 5] |
| Merge sort [Skiena] pp. 37. |
| Fast Fourier Transform (FFT) [Cormen] pp. 787. Also
here. |
| Sorting/merging/permutation networks. Also
here. |
| Different ways to compute (n k). [Cormen] pp. 103. |
| # of ways to give hats to persons so that nobody get his own hats. |
| Critical Mass [ACM 580]. |
| Strategy [ACM 174]. |
| The fisherman's problem. [台大博士班資格考]. |
| Peano-Hilbert curve. [台大交大交流比賽] |
| Quad tree [ACM 297] |
| Tree summing [ACM 112] |
| Strassen's matrix multiplication [Cormen] pp. 739. |
| The nearest neighbor problem [Cormen] pp. 908. |
|
| Lecture 8
| Code review for midterm examination (part 1) |
|
| Lecture 9
| Code review for midterm examination (part 2) |
| Heuristic methods, depth-first search
 | All subsets, [Skiena] pp. 117. |
| All permutation, [Skiena] pp. 118. |
| All paths from a single source, [Skiena] pp. 118. |
| Bandwidth, [Skiena] pp. 120. |
| Covering chessboard, [Skiena] pp. 122. |
| Book assignment [呂品] pp.299. |
| Knight's tour [呂品] pp. 319. |
| Simulated Annealing. |
|
|
| Lecture 10
| Breadth-first search
| Eight-puzzle [呂品] pp. 343 |
| Coin-flipping [呂品] pp. 363 |
| Portion problem [呂品] pp. 376 |
| Set of numbers [呂品] pp. 377 |
|
|
| Lecture 11
| Heuristic search
| Eight-puzzle [呂品] pp. 380 |
| Knight's tour [呂品] pp. 319 |
| Coin moving problem [呂品] pp. 389 |
|
| A* search
| Coin moving problem [呂品] pp. 389 |
| A* optimal solution theorem [呂品] pp. 399 |
| Search efficiency vs. optimality [呂品] pp. 400
| Weighted evaluation function. |
|
|
| Branch-and-bound
| Traveling salesman [呂品] pp. 403 |
|
|
| Lecture 12 - Graph algorithms
| Terminology |
| Graph traversal
| Depth-first search, [Skiena] pp. 91. |
| Breadth-first search, [Skiena] pp. 89. |
| Application
| Connected component, [Skiena] pp. 92. |
| Cycle detection, [Skiena] pp. 93. |
| Bipartite graph coloring, [Skiena] pp. 93. |
| Topological sort, [Skiena] pp. 94. |
| Articulation points, [Skiena] pp. 95. |
|
|
| Minimum spanning tree
| Prim's method, [Skiena] pp. 98. |
| Kruskal's method, [Skiena] pp. 99. |
|
| Shortest path
| Single source
| Dijkstra's algorithm, [Skiena] pp. 100. |
|
| All sources, [Skiena] pp. 102. |
|
| Cut and flow
| Maximum cut, [Skiena] pp. 297. |
| Minimum flow, [Skiena] pp. 297. |
|
|
| Lecture 13 - Data Structures
| Stack |
| Queue |
| Heap |
| Hash table |
| Dictionary |
| Priority Queue |
| Bounded Height Priority Queue
| Peeling triangle stripes from a 3D model. [Skiena] pp. 39. |
|
| Sorted Array
| Expressing a number as the sum of pyramidal numbers. [Skiena] pp.
43. |
|
|
| Lecture 14 - Data Structures
| Union-and-Find Tree
| Disjoint Sets. [Tarjan] pp. 23. |
|
| Balanced Binary Trees
| Self-adjusting
| Splay Tree [Tarjan] pp. 53. |
|
| Non-self-adjusting
| Red black tree [Tarjan] pp. 48. |
|
|
| Amortized analysis
| Stack and multi-pop [Cormen] pp. 357. |
| Increasing a binary counter [Cormen] pp. 358. |
| Accounting method [Cormen] pp. 360. |
| Potential method [Cormen] pp. 363. |
|
|
