 | Lecture 1 - Programming Style (also known as 學校裏沒教的事). Please download
the following document.
programming.style.ps |
| Lecture 2
 | Programming Style (cont.)
|
|
| Lecture 3 - 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 [呂品] |
|
| Lecture 4 - Divide and conquer
| Fast Exponentiation [Skiena] pp. 75. |
| Binary search [Skiena] pp. 76. |
| Quicksort. |
| Construct a binary tree from its inorder and preorder sequences. |
| L-shaped tiling problem. |
| Merge sort [Skiena] pp. 37. |
| Fast Fourier Transform (FFT) [Cormen] pp. 787. |
| Strassen's matrix multiplication [Cormen] pp. 739. |
| The nearest neighbor problem [Cormen] pp. 908. |
| Sorting and merging networks. |
| The fisherman's problem. [台大博士班資格考]. |
| Peano-Hilbert curve. [台大交大交流比賽] |
|
| 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. |
|
| Lecture 6 - Heuristic methods (1)
| Depth-first search
 | All subsets |
| All permutation |
| All paths from a single source |
| Bandwidth |
| Covering chessboard |
| Book assignment [呂品] pp.299. |
| Knight's tour [呂品] pp. 319. |
|
| Simulated Annealing |
|
| Lecture 7 - Heuristic methods (2)
| Breadth-first search
| Eight-puzzle [呂品] pp. 343 |
| Coin-flipping [呂品] pp. 363 |
| Portion problem [呂品] pp. 376 |
| Set of numbers [呂品] pp. 377 |
|
| 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 8 - Graph algorithms
| Terminology |
| Graph traversal
| Depth-first search |
| Breadth-first search |
| Application
| Connected component |
| Cycle dectection |
| Bipartite graph coloring |
| Topological sort |
| Articulation points |
|
|
| Minimum spanning tree
| Prim's method |
| Kruskal's method |
|
| Shortest path
| Single source
| Dijkstra's algorithm |
|
| All sources |
|
| Isomorphism
| Rooted tree |
|
| Cut and flow
| Maximum cut |
| Minimum flow |
|
|
| Lecture 9, 10, and 11
| ACM.zip |
| We will discuss the problem sets from China in the past 5 years.
Please download and print these problem sets. |
| Also this one. |
|
| Lecture 12
| We will discuss the following documents.
|
|
| Lecture 13
| 100
|
| 10405
|
| 10407
|
| 10409
|
| algebra
|
| reduction
|
|
