CSE 6332 Advanced algorithms
Spring, 2015.
Intructor:
Anastasios Sidiropoulos.
Office hours:
Tue, 2:003:00pm, in DL589.
TA:
Erdem Sariyuce
Time:
Wed Fri, 2:203:40pm.
Location:
CL0133
Information

The course is an introduction to advanced concepts in algorithm design that are not typically covered in CSE 6331. The topics that will be covered include:

String algorithms:
algorithms and data structures for processing strings.

Randomized algorithms:
how to obtain simpler and more efficient solutions using randomization.

Graph algorithms:
advanced algorithms for processing graphs and networks.

Linear programming

Approximation algorithms:
methods for approximately solving optimization problems that do not admit efficient exact solutions.

Fixedparameter tractability:
a framework for solving hard optimization problems when the optimum cost is small.

Streaming algorithms:
a framework for computing statistics of big data sets using limited space.

Reading material:

[1]
Introduction to algorithms (3rd edition), by Charles E. Leiserson, Ronald Rivest, Thomas H. Cormen, and Clifford Stein.

[2]
Algorithms on strings, trees, and sequences, by Dan Gusfield.

[3]
Randomized algorithms, by Rajeev Motwani and Prabhakar Raghavan.

[4]
Fundamentals of parameterized complexity, by Rodney Downey and Michael Fellows.

Grading policy: 33% homework, 33% midterm, 34% final project. No late homework will be accepted.
Homework
Lectures
1. String algorithms

Jan 14, 2015. Lecture 1: Introduction. Suffix trees 1 (Chapter 6 from [2]).

Jan 16, 2015. Lecture 2: Suffix trees 2.

Jan 21, 2015. Lecture 3: Suffix trees 3.

Jan 23, 2015. Lecture 4: Applications of suffix trees (Chapter 7 from [2]).

Jan 28, 2015. Lecture 5: The KarpRabin algorithm (Chapter 32 from [1], see also these lecture notes due to Piotr Indyk).
2. Randomized algorithms

Jan 30, 2015. Lecture 6: Karger's algorithm for MinCut (Chapter 1 from [3]).

Feb 4, 2015. Lecture 7: Applications of the Chernoff bound 1 (Sections 4.1 and 4.2 from [3]).

Feb 6, 2015. Lecture 8: Applications of the Chernoff bound 2.

Feb 11, 2015. Lecture 9: 2SAT.

Feb 13, 2015. Lecture 10: Random walks. Reachability.
3. Approximation algorithms

Feb 18, 2015. Lecture 11: Bin Packing. MaxCut.

Feb 20, 2015. Lecture 12: Approximation schemes. Knapsack.

Feb 25, 2015. Lecture 13: Fully polynomial time approximation schemes.

Feb 27, 2015. Lecture 14: Linear programming relaxations 1. Vertex Cover.

Mar 4, 2015. Lecture 15: Linear programming relaxations 2. Maximum Satisfiability. Set Cover.
4. Exact algorithms

Mar 25, 2015. Lecture 16: Fixed parameter tractability 1. Bounded search trees, kernelization, Vertex Cover (Chapters 3 and 4 from [4]).

Mar 27, 2015. Lecture 17: Fixed parameter tractability 2. Planar Independent Set, MaxSAT, color coding, kPath (Chapters 3, 4, and 8 from [4]).

Apr 3, 2015. Lecture 18: Treewidth 1 (Chapter 10 from [4], see also this expository article by Hans L. Bodlaender).

Apr 8, 2015. Lecture 19: Treewidth 2.

Apr 10, 2015. Lecture 20: Bidimensionality.
5. Streaming algorithms

Apr 15, 2015. Lecture 21: Distinct elements (see this monograph by M. Muthukrishnan).

Apr 17, 2015. Lecture 22: Norm estimation.