##
CSCE 411 Design and Analysis of Algorithms

Fall 15

**Instructor**: Sing-Hoi Sze

**Email**: shsze@cse.tamu.edu

**Meeting**: MWF 9:10-10 HRBB 113

**Office Hours**: MWF 8:40-9:10 HRBB 328B or by appointment

### 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, 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, minimum cut, bipartite matching,
matroids.
- Dynamic programming: longest common subsequence, sequence alignment,
matrix-chain multiplication.
- 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,
*NP*-completeness.
- Approximation algorithms, fixed-parameter tractability.
- Undecidability, Halting problem, Rice's theorem.

### Grading

- Homework assignments (30%): written assignments handed out every one or two
weeks.
- Two midterms (20% each).
- One final exam (30%).

### Prerequisites

- Junior or senior classification or approval of instructor.