演算法

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.

Students will have the slides. Slides do not cover all the details, reading book is required.

One midterm exam, one final exam (70% of final score). At most 3 programming assignments, some homework (reading assignments), and some quizs.

Introduction to Algorithms, 3rd edition, MIT press. By Cormen, Leiserson, Rivest, and Stein.

地點

EC115[KF]

時間

Office hour, to be announced, or appointment.

聯絡方式

ytc@cs.nctu.edu.tw