CSCE 411 Design and Analysis of Algorithms
Instructor: Sing-Hoi Sze
Meeting: MWF 9:10-10 HRBB 113
Office Hours: MWF 8:40-9:10 HRBB 328B or by appointment
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
algorithms, and will also investigate classes of problems that are intractable
- Sums, asymptotic notations, sorting lower bound.
- Divide-and-conquer: Master theorem, matrix multiplication, fast Fourier
- Greedy algorithms: minimum spanning tree, minimum cut, bipartite matching,
- Dynamic programming: longest common subsequence, sequence alignment,
- Amortized analysis: multipop stack, string matching.
- Graph algorithms: breadth-first search, depth-first search, topological
sorting, strongly connected components, shortest paths, Eulerian path,
de Bruijn graph.
- Network flow, linear programming.
- Randomized algorithms: quicksort, minimum cut.
- Complexity theory: P, NP, reductions,
- Approximation algorithms, fixed-parameter tractability.
- Undecidability, Halting problem, Rice's theorem.
- Homework assignments (30%): written assignments handed out every one or two
- Two midterms (20% each).
- One final exam (30%).
- Junior or senior classification or approval of instructor.