##
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

**TA**: Peiming Liu

**Email**: peiming@tamu.edu

**Office Hours**: MW 4-5:30 HRBB 419D

### Solutions

### Exams

- Midterm Exam (Mar. 8): up to amortized analysis

### Homeworks

### 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%).