CSCE 629-600 Analysis of Algorithms
Instructor: Sing-Hoi Sze
Meeting: TR 8-9:15 HELD 113
Office Hours: TR 9:30-10:30 HRBB 328B
TA: Peiming Liu
Office Hours: MW 4-5:30 HRBB 419D
- Midterm Exam (Mar. 8): up to amortized analysis
Cormen T.H., Leiserson C.E., Rivest R.L. and Stein C. (2009)
Introduction to Algorithms, Third Edition. The MIT Press.
This course studies different types of computational problems and techniques
to solve them. The course will focus on analyzing the efficiency of these
- Sums, asymptotic notations, sorting lower bound.
- Divide-and-conquer: Master's theorem, matrix multiplication, fast Fourier
- Greedy algorithms: minimum spanning tree, matroids.
- Dynamic programming: longest common subsequence, sequence alignment,
- Amortized analysis: multipop stack, union-find.
- Graph algorithms: breadth-first search, depth-first search, Eulerian path,
de Bruijn graph, topological sorting, strongly connected components,
- Network flow, matching, linear programming.
- Randomized algorithms: quicksort, minimum cut.
- Complexity theory: Turing machines, P, NP, reductions,
- Approximation algorithms, fixed-parameter tractability.
- Homework assignments (30%): written assignments handed out every one or two
- Midterm exam (30%).
- Final exam (40%).