Basics

Time & Location: Monday 12pm-3pm @ Hill 260

Instructor: Professor Jie Gao, jg1555@cs.rutgers.edu, skype: jiegao79. Office hour Monday 3-5pm at Hill 411.

Grader: Jeffrey Isaacs, jji23@scarletmail.rutgers.edu

For discussions/questions, please signup at piazza.com: https://piazza.com/rutgers/spring2020/cs513. I will check piazza daily and answer questions there.

Homework submission and announcements will be handled through canvas system.

This course expects students with undergraduate algorithm knowledge. If you plan to take this course, I expect that you know what the following words mean: big-O notion, running time, sorting, worst-case analysis.

This course will introduce algorithms used in practice as well as their performance analysis. The list of topics I plan to cover includes:

• Divide and conquer.
• Dynamic programming.
• NP and intractability.
• Approximation algorithms.
• Randomized algorithms.
• Online algorithms
• Geometric algorithms.

Everyone is welcome to sit in the lectures. Graduate students with interest in theory and algorithms are highly encouraged to take this course.

Schedule

1. 1/27 Quick review of basic knowledge. Sorting (MergeSort, QuickSort), Solving recurrences. First homework posted on canvas, due 2/9 9pm.
2. 2/3 Median (randomized and deterministic), Lower bound on sorting, closest pair. Fast Fourier Transform (FFT).
3. 2/10 FFT, Hash Table Second homework posted on canvas, due 2/23 9pm.
4. 2/17 Bloom Filter, Skip List
5. 2/24 Dynamic Programming (Weighted Interval Scheduling, Longest Increasing Subsequence, Longest Common Subsequence, Matrix Chain Multiplication)Third homework posted on canvas, due 3/8 9pm.
6. 3/2 Dynamic Programming
7. 3/9 All pairs shortest path, Flow Algorithm
8. 3/23 Flow algorithm and applications
9. 3/30 NP-hard problems and polynomial reduction, Fourth homework posted on canvas, due 4/14 9pm.
10. 4/6 NP-hard problems and polynomial reduction
11. 4/13 NP-hard problems and polynomial reduction. Fifth homework posted on canvas, due 4/26 9pm.
12. 4/20
13. 4/27
14. 5/4 Review, Q&A
15. Final exam TBD

Course Materials

The recommended textbooks are listed below.

• [KT] Algorithm design, by Jon Kleinberg, Eva Tardos, Addison-Wesley, 2005.
• [CLRS] Introduction to algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2nd edition, 2001.
• [Va] Approximation algorithms, Vijay V. Vazirani.
• [MR] Randomized algorithms, by Rajeev Motwani, Prabhakar Raghavan.

Good lecture notes:

• Jeff Erickson: http://jeffe.cs.illinois.edu/teaching/algorithms/
• David Mount: http://www.cs.umd.edu/~mount/451/Lects/451lects.pdf

Additional lecture notes or useful materials will be shared

Grading

Roughly 5-6 written homework (30%), midterm (35%) and final (35%).

• Homework problems are not trivial. Start early with the homework problems. It is unlikely you are able to finish last minute before the due date.
• No late homework accepted.
• Homework submission must be in the format of pdf, formatted by Latex, submitted through canvas. Handwritten homework will be returned. See below on how to use Latex.
• In both homework and exams, a question left empty received 20% of the total points, a wrong answer receives 0, and partially correct answers with minor flaws receive partial points.

Latex Resources

Install Latex on Windows: Miktex, WinEdt (a nice latex editor), how-to: https://guides.nyu.edu/c.php?g=601858&p=4168436.

Online Latex compilers: overleaf.com.

Draw figures:

• xfig in X-window (cygwin on a windows machine).
• Ipe (on both windows and Mac).