Instructor: Swastik
Kopparty (swastik.kopparty@rutgers.edu)
Office Hours: Hill 432, Wednesday
3pm – 4pm
TA: Amey
Bhangale (amey@cs.rutgers.edu)
Office Hours: Hill 268, Monday
10am – 12 noon
Reference books: The Design and
Analysis of Algorithms (Kozen), Algorithms (Dasgupta, Papadimitriou, Vazirani)
Syllabus: This is a graduate
course in algorithms. Topics may include:
·
Basic
techniques: divide and conquer, greedy, dynamic programming
·
String
algorithms: string matching, approximate string matching
·
Graph
algorithms: spanning trees, shortest paths, matchings,
flows
·
Algebraic
algorithms: integers, rational numbers, polynomials, linear algebra
·
Linear
programming
·
NP
completeness
·
Randomized
algorithms
·
Parallel
algorithms
·
Online
algorithms
·
Approximation
algorithms
There will be a problem set every
2 weeks. There is a midterm and a final.
Grading: 50% problem sets, 20%
midterm, 30% final, bonus credit: class participation
Homework
·
Homework 0: prerequisite refresher + basic
techniques. Due Feb 4.
·
Homework 1: Due Feb 25.
·
Homework 2: Due April 1.
·
Homework 3: Due April 29.
Lecture Schedule
·
January 21: no class (snow)
·
January 28: course overview, basic
techniques
·
February 4: basic graph algorithms
·
February 11: matchings,
cuts and flows
·
February 18: flows, string algorithms
·
February 25: MIDTERM (in class), NP-completeness
·
March 4: NP-completeness continued
·
March 11: NP-completeness continued,
2SAT in P
·
March 18: NO CLASS (Spring Break)
·
March 25: algorithms for integers
·
April 1: algorithms for polynomials
·
April 8: hashing
·
April 15: randomized algorithms,
approximation algorithms
·
April 22: online algorithms, multiplicative
weights update
·
April 29: FINAL EXAM (in class)