CS513 - Design and Analysis of Data Structures and Algorithms



Time: Tuesday & Thursday 1:40pm - 3:00pm
Place: Busch Sec-202
Instructors: Mina Ghashami & Matthäus Kleindessner & Jude Kong
Office Hours: by appointment (send an email to mina.ghashami[at]rutgers.edu or matthaeus.kleindessner[at]rutgers.edu or jk1567[at]dimacs.rutgers.edu)
Teaching assistant: Mohamed Abdellatif (latif.mohamed[at]rutgers.edu)
TA office hours: Wednesday 10:00am - 11:00am at Hill 403
Prerequisites: general background in undergraduate algorithms and basic mathematics


Tentative List of Topics (this list may vary according to the background of the students): Recommended Textbooks:
Grading Policy: There will be one midterm and a final exam. The midterm is worth 30% of the final grade. The final will weigh 40% of the final grade. Weekly homework assignments make up 30% of the final grade.

The homework assignments are mathematically oriented and involve derivations of mathematical equations, proofs of combinatorial theorems and running time analysis of combinatorial algorithms. Students can form groups of up to three for the purposes of homework. Homework is to be done independently within each group. Each group should turn in one assignment, clearly marked with group-member names. Once you form a group, it can not be changed.

For determining the final homework grades, we do not consider the two worst assignments of each group. This means each group can skip two homework assignments and still achieve the best homework grade. NO LATE HOMEWORK WILL BE ACCEPTED. 25% credit will be given for any question for clearly marking the question with "WE DO NOT KNOW". Wrong answers will get 0% credit, so it is better for you to admit that you do not know something rather than trying to fake it. Of course, you get partial credit for saying something better than "WE DO NOT KNOW".

Homeworks have to be uploaded in Sakai. If you upload a scan of your handwritten records, make sure it is properly readable.

Tentative Exam Schedule:

Covered topics, material, and assignments

  Date     Instructor     Content     Material     Assignment  
January 16 M. Ghashami growth of functions (asymptotic notation), recursive relations (recursion tree, master theorem), merge sort and selection sort algorithms   CLRS: Chapters 2, 3, 4 Assignment 1 (this assignment is only provided as an exercise and will not be collected)
January 18 M. Ghashami divide and conquer (lower bound on number of comparision on sorting, median of median, linear time select) DPV: Chapter 3    
January 23 M. Ghashami Dynamic programming CLRS: Chapter 15    
January 25 M. Ghashami Dynamic programming (Matrix chain multiplication), Greedy algorithms (Activity selection), Majority algorithm CLRS: Chapters 15, 16 Assignment 2 (due February 2, 11:59pm)
January 30 M. Ghashami Streaming (Majority, Misra-Gries, count-min sketch, bloom filter) http://www.cs.utah.edu/~jeffp/DMBook/L11-Heavy-Hitters.pdf http://www.cs.utah.edu/~jeffp/DMBook/L12-Count-Min+Apriori.pdf
February 1 M. Ghashami Probabilistic Analysis and Randomized Algorithms CLRS: Chapter 5 Assignment 3 (due February 9, 11:59pm)
February 6 M. Ghashami Probabilistic Analysis CLRS: Chapter 5 (coupon collector, balls and bins, longest streak of heads in coin flips)    
February 8 M. Ghashami Probabilistic Analysis: online hiring problem, Markov and Chebyshev's inequalities CLRS: Chapter 5 Assignment 4 (due February 16, 11:59pm)
February 13 M. Kleindessner Fast Fourier transform for multiplying polynomials CLRS: Chapter 30; DPV: Chapter 2.6    
February 15 M. Kleindessner Fast Fourier transform continued CLRS: Chapter 30; DPV: Chapter 2.6 Assignment 5 (due February 23, 11:59pm)
February 20 M. Kleindessner RSA DPV: Chapters 1.2 - 1.4; CLRS: Chapter 31    
February 22 M. Kleindessner RSA continued (primality testing) DPV: Chapters 1.2 - 1.4; CLRS: Chapter 31 Assignment 6 (due March 2, 11:59pm)
February 27 M. Kleindessner Midterm --- Questions will be about the content of the lectures from January 16 to February 20.

You are allowed to bring a handwritten "cheat sheet" (one piece of ordinary paper).
March 1 M. Kleindessner Hashing CLRS: Chapters 11.1 - 11.2 Assignment 7 (due March 9, 11:59pm)
March 6 M. Kleindessner Universal hashing; NP-Completeness CLRS: Chapter 11.3.3; CLRS: Chapter 34    
March 8 M. Kleindessner NP-Completeness continued CLRS: Chapter 34; DPV: p. 249/250 Assignment 8 (due March 23, 11:59pm)
March 20 M. Kleindessner Approximation Algorithms CLRS: Chapter 35 (35.1 and 35.3)    
March 22 M. Kleindessner Approximation Algorithms continued; Branch-and-bound CLRS: Chapter 34.5.4; DPV: Chapter 9.1.2 Assignment 9 (due March 30, 11:59pm), SetCoverInstance.txt
March 27 J. Kong Linear Algebra review CLRS: Appendix D, V: Chapter 21.3.2, 26.2    
March 29 J. Kong String Matching: Naive Algorithm and The Knuth-Morris-Pratt Algorithm CLRS: 32.1, 32.4 Assignment 10 (due April 06, 11:59pm)
April 3 J. Kong String Matching: The String Matching with finite automata CLRS: 32.3    
April 5 J. Kong String Matching: The Rabin-Karp algorithm; Van Emde Boas Trees: Preliminary approaches. CLRS: 32.2 and 20.1 Assignment 11 (due April 13, 11:59pm)
April 10 J. Kong Van Emde Boas Trees CLRS: 20.2 and 20.3    
April 12 J. Kong Matrix Operations CLRS: 28.1 Assignment 12 (due April 20, 11:59pm)
April 17 M. Kleindessner Markov Chains and PageRank https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf
(Sections 11.1, 11.3, 11.4)
   
April 19 M. Kleindessner Markov Chains and PageRank continued Assignment 13 (due April 27, 11:59pm)
April 24 M. Kleindessner Markov Chains and PageRank continued https://disco.ethz.ch/courses/fs16/ti2/lecture/chapter11.pdf (Section 11.3)    
April 26 M. Kleindessner Stable marriage problem and Gale-Shapley algorithm Lecture notes    
May 4 Final --- Questions will be about the content of the lectures from February 22 to April 26.

You are allowed to bring a handwritten "cheat sheet" (one piece of ordinary paper).