Time: Tuesdays and Thursdays, 14:00–15:20
Location: Hill 114
Instructor: Kangning Wang (Please only email me for confidential matters. For other purposes, please post a message on Piazza.)
Teaching Assistants:
Qing Chen (Ph.D. TA)
Yinglong Miao (Ph.D. TA)
Yash Sharma (Ph.D. TA)
Rohit Amarnath (Part-Time Leader)
Nadya Belova (Part-Time Leader)
Kavan Patel (Grader)
Primary Textbook: Algorithm Design by Jon Kleinberg and Éva Tardos (referred to as [KT] below)
Office Hours: (All office hours are open to students in all sections. These start from the second week.)
Kangning Wang: (1) Tuesdays, 15:30–16:30, Hill 482; (2) Wednesdays, 16:00–17:00, Hill 482
Qing Chen: Tuesdays, 16:30–17:30, Hill 482
Yinglong Miao: Thursdays, 11:00–12:00, CoRE 244
Yash Sharma: Mondays, 16:00–17:00, CoRE 626
Rohit Amarnath: Wednesdays, 12:30–13:30, CoRE 244
Nadya Belova: Fridays, 12:00–13:00, CoRE 244
Recitation Sections: (These start from the second week.)
Section 05: Tuesdays, 19:45–20:40, ARC 107, led by Rohit Amarnath
Section 06: Thursdays, 16:05–17:00, ARC 105, led by Yinglong Miao
Section 07: Thursdays, 17:55–18:50, SEC 205, led by Nadya Belova
Section 08: Tuesdays, 17:55–18:50, SEC 207, led by Yash Sharma
Exam Dates:
March 6th (Thursday), in-class midterm exam [up to Lecture 11: self-balancing binary search trees]
April 10th (Thursday), in-class midterm exam [cumulative, up to Lecture 19: applications of network flow]
May 13th (Tuesday), 12:00–15:00, final exam [cumulative]
This is a standard undergraduate-level algorithms course that covers some of the most important concepts in the field of algorithm design, including
the standard framework to evaluate the computational efficiency of algorithms;
powerful algorithm design techniques and abstractions, such as greedy, dynamic programming, divide and conquer, data structures, and graphs;
the insight that some problems are inherently "difficult," such as NP-hard problems.
The goal of this course to develop the ability to design algorithms for new problems, and to provide rigorous and clear analysis of their correctness and efficiency. Achieving this goal will take serious effort, and my personal suggestion is to solve as many problems as you can. The textbook [KT] provides lots of exercises at the end of each chapter, and if you are (or wish to become) comfortable with coding, you can solve problems on online judges such as Codeforces. Rutgers also has a very active competitive programming club that regularly holds beginner and advanced lectures.
Overview: The maximum score is 1000 plus bonuses. It is divided into: (1) 300 for homework assignments, (2) 200 plus bonuses for each of two midterm exams, and (3) 300 plus bonuses for the final exam. Expect the median grade to be a "B", and expect the fraction receiving an "A" to be about 25%.
Homework Assignments: Each Homework assignment can be done in groups of at most three students, and solutions must be prepared with LaTeX. (Short and longer guides.) Some of the homework problems are designed to be challenging, and you are expected to put in reasonable effort attempting every problem. If a problem remains unsolved, please write down the amount of time your group spent on it (which should not be too short), so that the submission will be considered "complete." For the purpose of calculating homework grades, completion is sufficient for full score. In other words, you will receive full score as long as you have made a reasonable attempt for each homework problem. The teaching assistants will provide critical feedback on the correctness of your homework solutions, but our grading policy does not take their correctness into account.
Exams: There will be two midterm exams and one final exam. In each of these exams, there will be challenging bonus questions, and the maximum possible score will be about 130% of the target. (The target is 200 for a midterm and 300 for the final.) We will grade exam solutions based on their correctness, and a fundamentally incorrect solution will receive zero score. However, you can write down "I don't know" for any problem for a 25% partial credit.
Homework Collaboration: Each homework assignment can be done in groups of at most three students. Please only submit one copy per group and mention the names and NetIDs of all members in the group. Acknowledge any external help from, for example, students in other groups, search engines, and large language models. Keep in mind that large language models sometimes give nonsensical answers.
Late Homework Submission: Homework submissions are expected to be timely unless there are legitimate justifications otherwise. (Note that we wish to distribute sample solutions immediately after the due date.) With legitimate justifications (please do not submit them unless asked), a late submission will be considered "complete" for the purpose of calculating grades, but may not receive critical feedback.
Regrading Requests: Please do not submit regrading requests for homework assignments (as their correctness does not count towards your grades). For exams, the course staff will only consider a regrading request if the initial grading contains a factual error. In that case, please post a message on Piazza clearly describing what factual error has been made in the initial grading. The course staff might also regrade your entire exam after receiving a regrading request.
Introduction and Brief Review (3 Lectures) [KT, Chapters 1, 2, 3]
Why studying algorithms?
big O notation
basics of graphs
algorithm design example: Gale–Shapley stable matching algorithm
Divide and Conquer (3 Lectures) [KT, Chapter 5]
exponentiation
sorting: merge sort, stooge sort, quicksort (median of medians)
the master theorem
closest pair of points on a plane
Karatsuba algorithm for polynomial multiplication
fast Fourier transform
Dynamic Programming (4 Lectures) [KT, Chapter 6]
introductory examples
longest increasing subsequence
intervals: merging adjacent piles of stones
knapsacks: subset sum, 0/1 knapsacks, and unbounded knapsacks
two strings: longest common substring
subsets: the traveling salesman problem
other dynamic programming examples
dynamic programming optimization techniques
Data Structures (2 Lectures)
self-balancing binary search trees: the splay tree
range minimum query
Greedy Algorithms (3 Lectures) [KT, Chapter 4]
the exchange argument
scheduling
caching
Huffman codes
minimum spanning trees: Prim (Fibonacci heaps), Kruskal (union–find), Borůvka
Graph Algorithms (4 Lectures) [KT, Chapters 4, 6, 7]
shortest paths: Dijkstra, Bellman–Ford, Floyd–Warshall
bipartite matching
network flow, cuts, and with costs
applications of network flow
Computational Complexity (3 Lectures) [KT, Chapter 8]
computability, the Church–Turing thesis
the classes P and NP
reductions, and the notions of "hardness" and "completeness"
NP-complete problems
Other Topics (2 Lectures)
randomized algorithms
approximation algorithms
game theory