Algorithm Design and Analysis (Spring 2025)

Course Information

Time	:	Tuesdays and Thursdays, 10:10am - 12:00pm
Location	:	仙II-319
Instructor	:	Shi Li (栗师)
Email	:	[first name][last name][at][nju][dot][edu][dot][cn]

Logistics

Instructor's Office Hours	:	Wednesdays 11:00am-12:00pm
Location	:	计算机系楼605
TA	:	梁梓豪(zhliang[at]smail[dot]nju[dot]edu[dot]cn)

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 calculated as follows:

• 5 homework assignments.
• Midterm exam.
• Final exam.

Your overall score will be determined using the highest of the following weighting schemes:

• 20% Homework + 20% Midterm + 60% Final
• 20% Homework + 30% Midterm + 50% Final

Both exams will be closed-book.

Policies for Assignments

• No late submissions will be accepted.
• You are not allowed to search online for solutions, or use AI tools to generate solutions.
• The following materials are allowed: 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.

Use of AI Tools

Nowadays, we have powerful AI tools such as ChatGPT and DeepSeek that can solve complex algorithm design problems and generate codes. We do not prohibit its use as a learning tool for this course. In fact, AI tools can help you understand course materials more efficiently. But be aware that AI-generated content may contain errors, and it is your responsibility to verify the correctness of any information you use.

However, when it comes to solving homework problems, AI tools are strictly prohibited. The rule is that once you begin working on an assignment, you must complete them without searching for solutions online or using AI tools.

Assignments

Assignments	Releasing Date	Deadline

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.

1. Introduction (4 hours)     Slides: Introduction, Introduction-handout (last updated: 2025/02/20 08:44)
   • Syllabus
   • Asymptotic Notations (KT 2.2)
   • Common Running Times (KT 2.4)
2. Graph Basics (4 hours)     Slides: GraphBasics, GraphBasics-handout (last updated: 2025/02/18 08:41)
   • 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)
3. Greedy Algorithms (6 hours)     Slides: Greedy, Greedy-handout (last updated: 2025/02/10 09:54)
   • 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)
4. Divide and Conquer (6 hours)      Slides: DivideAndConquer, DivideAndConquer-handout (last updated: 2025/02/10 09:54)
   • 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)
5. Dynamic Programming (6 hours)      Slides: DynamicProgramming, DynamicProgramming-handout (last updated: 2025/02/10 09:55)
   • 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
6. Graph Algorithms (6 hours)      Slides: GraphAlgorithms, GraphAlgorithms-handout (last updated: 2025/02/10 09:55)
   • 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)
7. Network Flow (6 hours)      Slides: NetworkFlow, NetworkFlow-handout (last updated: 2025/02/10 09:55)
   • 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)
8. NP-Completeness (6 hours)      Slides: NPC, NPC-handout (last updated: 2025/02/10 09:56)
   • 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)
9. Linear Programming (4 hours)      Slides: LinearProgramming, LinearProgramming-handout (last updated: 2025/02/10 09:55)
   • Linear Programming, Simplex, Interior Point Method, Elipsoid Method
   • Linear Programming and Duality
   • Integral Polytopes
10. Advanced Topics (10 hours)      Slides: AdvancedTopics, AdvancedTopics-handout (last updated: 2025/02/10 09:59)
    • 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)