CS 344: Design and Analysis of Computer Algorithms
Spring 2025, Rutgers University
Time and Location
Monday, Wednesday, 3:50pm – 5:10pm, Busch PHY-001
Instructor
Roie Levin, Core 306
Office Hours
TBD
Teaching Assistant
TBD
Course Description
The course covers a broad set of topics in algorithms design and analysis. The goal is to cover tools and algorithms that give students the ability to (a) recognize which tool or method to apply to problems, (b) become reasonably proficient at using these tools, (c) be able to reason about the correctness and performance of the resulting algorithms.
There will be a Homework 0: if you plan to take this course, please make sure you are comfortable with the material therein.
Topics I plan to cover include:
- Divide and conquer.
- Dynamic programming.
- Greedy Algorithms.
- Graph Algorithms
- NP-hardness and intractability.
- Linear Programming.
- Misc. Advanced Topics.
Homework
All homework is due at 11:59 pm on the specified day. The lowest homework grade will be dropped.
- Homework 0
- Homework 1
- Homework 2
- Homework 3
- Homework 4
- Homework 5
(Tentative) Schedule
| Date | Topic | Lecture Notes | Optional Reading |
|---|---|---|---|
| Jan 22 | Course Overview and Basics Review | ||
| Divide and Conquer | |||
| Jan 27 | Proof by Induction, Recursion, Tower of Hanoi, Divide and Conquer, Mergesort | ||
| Jan 29 | Karatsuba Multiplication, Strassen’s Algorithm | ||
| Feb 03 | Master Theorem, Median of Medians | ||
| Dynamic Programming | |||
| Feb 05 | Fibonacci, Longest Increasing Subsequence | ||
| Feb 10 | Edit Distance, 0/1 Knapsack | ||
| Greedy Algorithms | |||
| Feb 12 | Interval Scheduling, Coin Change, Fractional Knapsack | ||
| Feb 17 | Huffman Coding, Optimal BST | ||
| Graph Algorithms | |||
| Feb 19 | Graphs, BFS, DFS, Topological Sort | ||
| Feb 24 | Strongly Connected Components, Shortest Path, Dijkstra | ||
| Feb 26 | Bellman-Ford, Floyd-Warshall | ||
| Data Structures and Amortized Analysis | |||
| Mar 03 | Amortized Analysis Techniques | ||
| Mar 05 | Minimum Spanning Trees and Union Find | ||
| Mar 10 | Binomial Heaps, Fibonacci Heaps | ||
| Mar 12 | MIDTERM | ||
| Mar 17 | Spring Break, No Class | ||
| Mar 19 | Spring Break, No Class | ||
| Randomized Algorithms | |||
| Mar 24 | Probability Review, Quicksort | ||
| Mar 26 | Hashing, Balls and Bins | ||
| Mar 31 | Perfect Hashing, Bloom Filters | ||
| Linear Programming and Optimization | |||
| Apr 02 | Flows and Matchings | ||
| Apr 07 | Linear Programming, Modeling, Intuition behind algorithms | ||
| Apr 09 | Linear Programming Duality | ||
| Apr 14 | Game Theory, Von Newmann Minimax Theorem, Yao’s Lemma | ||
| Apr 16 | Polytopes and Integrality | ||
| Limits of Computation | |||
| Apr 21 | Limits of Computation and the Complexity Hierarchy | ||
| Apr 23 | NP-Completeness, Cook-Levin Theorem, Reductions | ||
| Apr 28 | More Reductions | ||
| Advanced Topics | |||
| Apr 30 | Combatting Intractability, Approximation Algorithms | ||
| May 05 | TBD |