課程概述與目標：
Shall know the way to design efficient algorithms and analyze the time and space complexity of algorithms. Some advance data structures those are needed to design efficient algorithms. Introduce some graph algorithms. To a computational problem, is it tractable (NP)? Or how fast we can solve it (lower bound).
Courses will cover
1. An introduction, sorting algorithms, asymptotic notations, recursion, 2 to 3 weeks.
2. \Omega(n log n) Lower bound to sorting algorithm, Why there are sorting algorithms beat this lower bound. 1 week,
3. Selection, a computational problem similar to but easier than sorting.
4. Review the way to design algorithms, iteration, divide and conquer, randomize, prune and search.
5. Random variable and analysis of quick sort.
6. balance tree, red-black tree,
7. Other ways to design efficient algorithms, greedy approach, dynamic programming, amortized analysis,
8. Heap structures, binomial heap, Fibonacci Heap
9. Union/Find operations, Function that grows very fast or very slowly.
10. graph algorithms, Minimum Spanning Tree, BFS, DFS, application of DFS.
11. Some graph algorithms are not tractable, NP
12. hopefully, some computational geometry, parallel algorithms, FFT, Linear programming, ...
先修科目或先備能力：
Prerequisites: Know at least a programming language (have take a related course and done programming assignments), C/C++ will be better. Data structures.
金額：18,300元
