- 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.
- The Role of Algorithms in Computing
-
Growth of Functions, Solving Recurrences
-
Insertion Sort, Merge Sort, Heapsort, Quicksort, Sorting in Linear Time, Medians and Order Statistics
-
Dynamic Programming, Greedy Algorithms
-
Amortized Analysis, Data Structures and Disjoint Sets
-
Graph Algorithms: BFS, DFS, Topological Sort, Minimum Spanning Trees, Single-source Shortest Paths, All-pairs Shortest Paths, Network Flows
-
Special Topics: Sorting Networks, Matrix Multiplication, String Matching
-
NP-Completeness, Approximation Algorithms
- Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3rd Edition, 2009, The MIT Press.
|