Design and Analysis of Data Structures and Algorithms

 

16:198:513

 

Fall 2016

 

Instructor: Shubhangi Saraf

Email:   shubhangi.saraf@gmail.com

Timing:  Wednesday 3:20 pm - 6:20 pm 

Location:  Lsh A143 (Livingston Campus)

 

TA: Amey Bhangale

Email Address: amey.bhangale@rutgers.edu

Office hours: Fridays 2 pm – 4 pm   Hill 268

 

 

Text:  Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein)

Additional References: Algorithms (Dasgupta, Papadimitriou, Vazirani), Randomized Algorithms (Motwani, Raghavan)

Prerequisite: Basic linear algebra, probability. Topics covered in a first algorithms course such as greedy algorithms, divide and conquer, sorting, dynamic programming, graph algorithms (such as graph search, shortest path, minimum spanning tree, max-flow min-cut), basic linear programming, notion of P, NP, NP completeness, reductions.

 

 

Description:  The following is a partial and tentative list of topics that might be covered

(This list may change based on interest of students and their background/preparation)

 

·      Randomized algorithms (Identity testing, string matching, fingerprinting, hashing)

·      Data structures

·      Number theoretic algorithms (Fast integer multiplication, primality testing)

·      Algebraic algorithms (Fast fourier transforms, matchings)

·      Cuts and flows, bipartite matching

·      Cryptography

·      Sublinear algorithms (polling, element distinctness)

·      Dimension reduction (Johnson Lindenstrauss)

·      Approximation algorithms (3SAT, set cover, SDP for maxcut)

·      Online algorithms

·      Parallel algorithms (perfect matchings, maximal independent set)

·      Multiplicative weights and applications

·      NP-completeness, space complexity

 

•Grade: There will be one midterm exam (on October 12), one final exam (on Dec 14) and biweekly problem sets and in-class quizzes. The problem sets and quizzes will be worth 30% of the grade, midterm will be worth 25% of the grade, the final exam will be worth 45% of the grade. Class participation will determine the grade for borderline cases.

Late homeworks will not be accepted. Also if you miss an in-class quiz, there will be no make up. However when we assign your final grade, we will drop the homework with the lowest grade and quiz with the lowest grade. Thus if you do poorly on (or miss) one homework and/or one quiz, then it wont affect your grade.

Homework: You are allowed to discuss the homework problem sets or work in small groups to solve the problems. In case you do work with others, clearly indicate in your homework writeup who you collaborated with. The writeup of the homework must be done independently and must be original.

 

Other interesting courses with overlapping material:

 

 

Homework

Problem Set 1    (Due on September 21 in class)

Problem Set 2    (Due on October 5 in class)

Problem Set 3    (Due on November 2 in class)

Problem Set 4    (Due on November 16 in class)

 

 

Schedule

Sept 7:  Overview, review of asymptotic notation, recurrences, divide and conquer, in class quiz

Sept 13: Fast Fourier transform, Selection in linear time (randomized and deterministic)

Sept 21: Start randomized algorithms (Probability basics, max-cut, algorithm for min-cut)

Sept 28: Short quiz, min-cut analysis, balls in bins, load balancing, hashing

Oct 5:  More hashing, polynomial identity testing

Oct 12: Midterm, parallel algorithm for maximal independent set

Oct 19: More polynomial identity testing, perfect matchings in graphs

Oct 26: Short quiz, string algorithms, number theory algorithms

Nov 2: number theory algorithms, Applications to cryptography

Nov 9: Short quiz, more cryptography

Nov 16: Multiplicative weights update method

Nov 23: No class (Wednesday became Friday schedule)

Nov 30: The stable matching problem

Dec 7: Error correcting codes