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.