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