## CSE 6331 Algorithms

Spring, 2014.
Intructor: Anastasios Sidiropoulos.
TA: David Fuhry.
Time: Mon Wed Fri, 1:50-2:45pm.
Location: Smith Lab, Room 3094.
Office hours: Thu, 3:00-5:00pm, at Dreese Labs, Room 674.
Mon, 3:00-4:00pm, at Dreese Labs, Room 589.

### Information

• Grading policy: 33% homework, 33% midterm, 34% final. No late homework will be accepted.
• Book: Introduction to Algorithms (3rd edition), by Charles E. Leiserson, Ronald Rivest, Thomas H. Cormen, and Clifford Stein.
• Midterm study material (the numbering is according to CLRS, 3rd edition): Chapter 3, Chapter 6, Chapter 7, Chapter 11: 11.1, 11.2, 11.3, except for the proof of Theorem 11.5, Chapter 12: 12.1, 12.2, 12.3, Chapter 13: 13.1, 13.2, 13.3, Chapter 15: 15.1, 15.2, 15.3, 15.4, Chapter 16: 16.1, 16.2, 16.3, Chapter 17, Chapter 19.
• Final exam study material (the numbering is according to CLRS, 3rd edition): Chapter 22, Chapter 23, Chapter 24: 24.1, 24.2, 24.3, 24.5, Chapter 25, Chapter 26: 26.1, 26.2, 26.3, Chapter 29: 29.1, 29.2.

### Lectures

• Jan 8, 2014. Lecture 1: Introduction, complexity of algorithms, asymptotic growth of functions.
• Jan 10, 2014. Lecture 2: Heapsort.
• Jan 13, 2014. Lecture 3: Quicksort.
• Jan 15, 2014. Lecture 4: Binary search trees.
• Jan 17, 2014. Lecture 5: Red-black trees.
• Jan 22, 2014. Lecture 6: Dynamic programming I.
• Jan 24, 2014. Lecture 7: Greedy algorithms I.
• Jan 27, 2014. Lecture 8: Greedy algorithms II: Algorithms that are not optimal.
• Jan 29, 2014. Lecture 9: Dynamic programming II.
• Jan 31, 2014. Lecture 10: Hash functions I.
• Feb 3, 2014. Lecture 11: Hash functions II.
• Feb 5, 2014. Lecture 12: Hash functions III.
• Feb 7, 2014. Lecture 13: Amortized analysis I.
• Feb 10, 2014. Lecture 14: Amortized analysis II.
• Feb 12, 2014. Lecture 15: Amortized analysis III.
• Feb 14, 2014. Lecture 16: Fibonacci heaps I.
• Feb 17, 2014. Lecture 17: Fibonacci heaps II.
• Feb 19, 2014. Lecture 18: Fibonacci heaps III.
• Feb 21, 2014. Lecture 19: Review of midterm study material.
• Feb 24, 2014. Midterm exam
• Feb 26, 2014. Lecture 20: Elementary graph algorithms I.
• Feb 28, 2014. Lecture 21: Elementary graph algorithms II.
• Mar 3, 2014. Lecture 22: Elementary graph algorithms III.
• Mar 5, 2014. Lecture 23: Elementary graph algorithms IV.
• Mar 7, 2014. Lecture 24: Minimum spanning trees I.
• Mar 10-14, 2014. Spring break
• Mar 17, 2014. Lecture 25: Minimum spanning trees II.
• Mar 19, 2014. Lecture 26: Single source shortest paths I.
• Mar 21, 2014. Lecture 27: Single source shortest paths II.
• Mar 24, 2014. Lecture 28: All-pairs shortest paths I.
• Mar 26, 2014. Lecture 29: All-pairs shortest paths II.
• Mar 28, 2014. Lecture 30: All-pairs shortest paths III.
• Apr 2, 2014. Lecture 32: Maximum flow I.
• Apr 4, 2014. Lecture 33: Maximum flow II.
• Apr 7, 2014. Lecture 34: Maximum flow III.
• Apr 9, 2014. Lecture 35: Maximum bipartite matching.
• Apr 11, 2014. Lecture 36: Linear programming I.
• Apr 14, 2014. Lecture 37: Linear programming II.
• Apr 16, 2014. Lecture 38: Linear programming III.
• Apr 18, 2014. Lecture 39: Linear programming IV.
• Apr 21, 2014. Lecture 40: Review of final exam study material.