**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)**

**Office
hours: ** Tuesday 11:45 am– 12:45 pm (Hill 426, Busch
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