Algorithm Design and Analysis (Spring 2024)
Course Information
| Time | : | Tuesdays and Thursdays, 10:10am - 12:00pm |
| Location | : | 仙 II-301 |
| Instructor | : | 栗师 |
| : | [first name][last name][at][nju][dot][edu][dot][cn] |
Logistics
| Instructor's Office Hours | : | Wednesdays 10:00am-11:00am |
| Location | : | 计算机系楼605 |
| TA | : | 白思睿 (srbai) |
News (check regularly!)
- The final exam is scheduled at 08:00-10:00am, Wednesday, June 26, 2024, at 仙I-202.
Overview
Algorithm design and analysis is fundamental to all areas of computer science and gives a rigorous framework for the study of problem solving. From the course you will learn:
- how to analyze the correctness and running time of an algorithm,
- classic algorithms for classic problems, such as sorting, minimum spanning tree and shortest paths,
- algorithm design paradigms such as greedy algorithms, divide and conquer, and dynamic programming,
- network flow and linear programming, and reductions of problems,
- NP-completeness, and
- advanced topics such as randomized algorithms, approximation algorithms, fixed-parametrized tractability and online algorithms.
Prerequisites of the course include
- basic skills in formulating mathematical proofs,
- courses on data structures covering
- linked lists, arrays,
- stacks, queues,
- priority queues,
- trees, graphs.
- some programming experiences using Python, C, C++ or Java.
Textbook
The following book is required for the course:
- Jon Kleinberg and Eva Tardos Algorithm Design 1st Edition, 2005, Pearson.
The "CLRS" book is also a good reference book:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein Introduction To Algorithms 3rd Edition, 2009, MIT Press.
Grading
Your final grade will be computed as follows:
- Theory Homeworks: 20% = 2.5% × 8 homeworks.
- Programming Assignments: 10% = 5% × 2 programming assignments.
- Midterm Exam: 20%.
- Final Exam: 50%.
Both exams will be closed-book.
Policies for Homeworks and Programming Assignments
- No late submissions will be accepted.
- You are not allowed to search online for solutions and codes.
- The following materials are allowed for solving the theory/programming problems: the text book, the reference book, the course slides and other materials that are distributed by the instructor.
- You may seek clarifications and/or hints from the instructor and the TAs, however, it is at their discretion to decide what information to provide.
- You are allowed to discuss with classmates. It is required that you dedicate sufficient time to solve the problems before the discussions. It is recommended that you collaborate with peers who have a similar level of understanding for the problems. You must write your solutions by yourself, in your own words. Furthermore, you must write down the names of the students you collaborated with. For the programming problems, you must implement the algorithms independently.
Homeworks and Programming Assignments
| HWs/PAs | Releasing Date | Deadline |
|---|---|---|
| HW1 | 2024/03/05 | 2024/03/17 |
| HW2 | 2024/03/24 | 2024/04/07 |
| HW3 | 2024/04/07 | 2024/04/21 |
| PA1 | 2024/04/07 | 2024/05/19 |
| HW4 | 2024/04/18 | 2024/05/05 |
| HW5 | 2024/05/05 | 2024/05/19 |
| HW6 | 2024/05/19 | 2024/06/02 |
| PA2 | 2024/05/19 | 2024/06/23 |
| HW7 | 2024/05/31 | 2024/06/12 |
| HW8 | 2024/06/07 | 2024/06/23 |
You need to submit your homeworks electronically, via a email to the TA. We strongly encourage the use of LaTeX. You can find some instructions on how to write in Latex here. You can choose to answer in Chinese or English; LaTeX supports Chinese well. If you choose to handwrite, you can scan or take a photo of your homework, ensuring that the handwriting in the electronic file is clear.
Syllabus and Tentative Schedule
It is highly recommended that you read the correspondent materials before each class, including the sections from the course textbook (the KT book), and the slides provided. The correspondent sections from the KT book are given below. The slides will be provided at least 2 weeks before the first class for the topic.
There are two versions of the slides available for each topic. The file without the suffix "handout" includes animations and is intended for viewing on a computer. Conversly, the one with the suffix does not include animations and is provided for ease of printing. The slides will be updated from time to time. The update times of the slides are provided to help you decide if you have the most current files.
- Introduction (3 hours) Slides: Introduction, Introduction-handout (last updated: 2024/02/28 03:27)
- Syllabus
- Asymptotic Notations (KT 2.2)
- Common Running Times (KT 2.4)
- Graph Basics (4 hours) Slides: GraphBasics, GraphBasics-handout (last updated: 2024/03/07 13:50)
- Basic Concepts on Graphs (KT 3.1)
- Connectivity and Traversal (KT 3.2, 3.4)
- Topological Sort (KT 3.6)
- Bridges and 2-Connected Components
- Connectivity in Directed Graphs (KT 3.5)
- Greedy Algorithms (5 hours) Slides: Greedy, Greedy-handout (last updated: 2024/03/11 11:01)
- Introduction, Interval Scheduling (KT 4.1)
- Scheduling to Minimize Maximum Lateness (KT 4.2), Weighted Completion Time
- Optimum Caching (KT 4.3)
- Huffman Code (KT 4.8)
- Divide and Conquer (6 hours) Slides: DivideAndConquer, DivideAndConquer-handout (last updated: 2024/03/27 23:43)
- Merge Sort (KT 5.1)
- Counting Inversions (KT 5.3)
- Solving Recurrences (KT 5.2)
- Quicksort, Median-Finder, Selection (KT 13.5)
- Polynomial and Matrix Multiplications (KT 5.5)
- Finding Closet Pair of Points (KT 5.4)
- Convolutions and Fast Fourier Transform (KT 5.6)
- Dynamic Programming (5 hours) Slides: DynamicProgramming, DynamicProgramming-handout (last updated: 2024/04/08 15:17)
- Weighted Interval Scheduling (KT 6.1)
- Segmented Least Squares (KT 6.2)
- Subset Sums and Knapsack (KT 6.4)
- Sequence Alignment (KT 6.6)
- Matrix Chain Multiplication
- Optimum Binary Search Tree
- Graph Algorithms (5 hours) Slides: GraphAlgorithms, GraphAlgorithms-handout (last updated: 2024/05/23 17:53)
- Kruskal's Algorithm for MST (KT 4.5)
- Prim's Algorithm for MST (KT 4.6)
- Dijkstra's Algorithm for Shortest Path (KT 4.4)
- Shortest Path with Negative Weights, Bellman-Ford, Floyd-Warshall (KT 6.8)
- Minimum Cost Arborescences (KT 4.9)
- Network Flow (8 hours) Slides: NetworkFlow, NetworkFlow-handout (last updated: 2024/04/28 12:01)
- Ford-Fulkerson Method (KT 7.1)
- Maximum Flow and Minimum Cuts (KT 7.2)
- Shortest Augmenting Path, Capacity Scaling (KT 7.3)
- Bipartite Graph Matching (KT 7.5)
- Disjoint Paths (KT 7.6)
- Other Applications of Network Flow (KT7.8-KT7.12)
- Linear Programming (4 hours) Slides: LinearProgramming, LinearProgramming-handout (last updated: 2024/05/09 17:49)
- Linear Programming, Simplex, Interior Point Method, Elipsoid Method
- Linear Programming and Duality
- Integral Polytopes
- NP-Completeness (6 hours) Slides: NPC, NPC-handout (last updated: 2024/05/23 09:41)
- P, NP, Co-NP (KT 8.1-8.3)
- P=NP?, NP-Completeness (KT 8.4)
- NP-Completeness of Circuit-SAT and 3-SAT (KT 8.5)
- NP-Completeness of Independent Set (KT 8.5)
- NP-Completeness of 3-Coloring (KT 8.7)
- NP-Completeness of Hamiltonion Cycle (KT 8.7)
- Advanced Topics (12 hours) Slides: AdvancedTopics, AdvancedTopics-handout (last updated: 2024/06/26 22:28)
- Randomized Algorithms: Global Min-Cut and Randomized Quicksort (KT 13.2, 13.5)
- Extending the Limits of Tractability (KT 10.1 - 10.4)
- Greedy Algorithms Via Approximation (KT 11.3, KT 11.4)
- Rounding Data to get Arbitrarily Good Approximations (KT 11.8)
- LP Rounding Algorithm for Approximation Algorithms (KT 11.6, 11.7)
- Primal-Dual Rounding Algorithm for Approximation Algorithms (KT 11.4)
- Final Review Slides Final Review