Course Introduction

• Prerequisite：Introduction to Computer Science, Data Structures
• Recommended for： graduate students
• Introduction：

This course is a fundamental course in Computer Science. Its purpose is to learn the techniques for designing an algorithm and the techniques for analyzing an algorithm.

• Syllabus：

1. The Role of Algorithms in Computing
2. Growth of Functions, Solving Recurrences
3. Insertion Sort, Merge Sort, Heapsort, Quicksort, Sorting in Linear Time, Medians and Order Statistics
4. Dynamic Programming, Greedy Algorithms
5. Amortized Analysis, Data Structures and Disjoint Sets
6. Graph Algorithms: BFS, DFS, Topological Sort, Minimum Spanning Trees, Single-source Shortest Paths, All-pairs Shortest Paths, Network Flows
7. Special Topics: Sorting Networks, Matrix Multiplication, String Matching
8. NP-Completeness, Approximation Algorithms

• Reference：

1. Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Edition, 2009, The MIT Press.