Design and Analysis of Data Structures and Algorithms

Spring 2012

(198:513)

 

Course Info

Instructor: Swastik Kopparty (swastik.kopparty@rutgers.edu)

Office Hours: Hill 432, Wednesday 1pm – 2pm

 

TA: David Menendez (davemm@cs.rutgers.edu)

Office Hours: Hill 414, Thursday 1pm – 3pm

 

Recommended books: Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein)

 

There will be a problem set every 2 weeks. There is a midterm and a final.

Grading: 60% problem sets, 15% midterm, 25% final, class participation

 

Homework

·         Homework 0 (due January 26)

·         Homework 1 (due February 13)

·         Homework 2 (due March 7)

·         Homework 3 (due April 16)

 

Lecture Schedule

·         January 23: Course Overview, Divide and Conquer, Sorting

·         January 30: Selection, Greedy Algorithms, Spanning Trees

·         February 6: Dynamic Programming

·         February 13: Mergeable Heaps, Union Find

·         February 20: Graph Algorithms: Shortest Paths, Minimum Spanning Trees

·         February 27: Matchings, Flows and Cuts

·         March 5: Linear Programming

·         March 12: NO CLASS (Spring Break)

·         March 19: Polynomials, Strings

·         March 26: Midterm (5:05pm – 6:05pm) Integers

·         April 2: Randomized Algorithms

·         April 9: Approximation Algorithms

·         April 16: Online Algorithms

·         April 23: Parallel Algorithms, Course Wrap-up

·         April 30: FINAL EXAM (in class)