CSCE 411-502 Design and Analysis of Algorithms
Spring 23
Instructor: Sing-Hoi Sze
Email: shsze@cse.tamu.edu
Meeting: TR 8-9:15 HRBB 124
Office Hours: TR 9:30-10:30 PETR 427 or on zoom
Textbook
Cormen T.H., Leiserson C.E., Rivest R.L. and Stein C.
Introduction to Algorithms. 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, and will also investigate classes of problems that are intractable
or unsolvable.
Topics
- Sums, asymptotic notations, sorting lower bound.
- Divide-and-conquer: Master theorem, matrix multiplication, fast Fourier
transform.
- Greedy algorithms: minimum spanning tree.
- Dynamic programming: longest common subsequence,
matrix-chain multiplication.
- Amortized analysis: multipop stack.
- Graph algorithms: de Bruijn graph, Eulerian path, depth-first search,
breadth-first search, topological sorting, shortest paths.
- Network flow, linear programming.
- Randomized algorithms: quicksort, minimum cut.
- Complexity theory: P, NP, reductions,
NP-completeness.
- Approximation algorithms, fixed-parameter tractability.
- Undecidability, Halting problem.
Grading
- Homework assignments (30%): written assignments handed out every one or two
weeks.
- Two midterms (20% each).
- Final exam (30%).
Prerequisites
- Junior or senior classification or approval of instructor.