Algorithm Design and Analysis (Spring 2026)

Course Information

Time	:	Tuesdays and Thursdays, 10:10am - 12:00pm
Location	:	仙II-319
Instructor	:	Shi Li (栗师)
Instructor's Office	:	计算机系楼605
Email	:	shili [at] nju [dot] edu [dot] cn
TA	:	王在烜

Overview

Algorithm design and analysis is fundamental to all areas of computer science and gives a rigorous framework for the study of problem solving. This course focuses on developing "algorithmic thinking"—the ability to identify the underlying structure of a problem and design efficient, provably correct solutions.

From the course you will learn:

• How to analyze the correctness and asymptotic running time of an algorithm.
• Classic algorithms for problems such as sorting, minimum spanning trees, and shortest paths.
• Algorithm design paradigms: Greedy algorithms, Divide and Conquer, and Dynamic Programming.
• Network flow, and reductions of problems.
• NP-completeness and the boundaries of computation.
• Advanced topics: randomized algorithms, approximation algorithms, fixed-parameter tractability.

Prerequisites include:

• Basic skills in formulating mathematical proofs.
• Data structures: Linked lists, stacks, queues, priority queues, trees, and graphs.
• Some programming experience.

Textbooks

The following book is required for the course:

• Jon Kleinberg and Eva Tardos, Algorithm Design, 1st Edition, 2005, Pearson.

The following books are excellent references for further study:

• Tim Roughgarden, Algorithms Illuminated, 2017-2020, Soundlikeyourself Publishing.
• Cormen, Leiserson, Rivest, and Stein, Introduction To Algorithms, 3rd Edition, 2009, MIT Press.

Grading

Your final grade will be determined by 5 homework assignments, a midterm exam, and a final exam. Your overall score will be calculated using the higher of the following two schemes:

• Scheme 1: 20% Homework + 20% Midterm + 60% Final
• Scheme 2: 20% Homework + 30% Midterm + 50% Final

Both exams will be closed-book.

Use of AI Tools

Powerful AI tools such as ChatGPT, DeepSeek and Gemini can help you understand course materials more efficiently. We do not prohibit their use as learning tools; however, AI-generated content may contain errors, and it is your responsibility to verify correctness.

Note: When solving homework problems, AI tools are strictly prohibited. Once you begin working on an assignment, you must complete it without searching for solutions online or using AI tools.

Policies for Homework Assignments

• No late submissions will be accepted.
• You are not allowed to search online for solutions or use AI tools for assignments.
• Allowed materials: The textbook, reference books, course slides, and instructor-provided materials.
• You are allowed to discuss with classmates, but you must dedicated sufficient time to solve problems individually first.
• You must write solutions by yourself, in your own words, and list the names of all collaborators.

Homework Assignments

Assignments	Releasing Date	Deadline

You can submit either an electronic version or a printed paper copy of your homework. You could also submit a handwritten work. For the electronic version, it is recommended that you use LaTeX to typeset your work. You may write your answers in either Chinese or English.

Syllabus and Tentative Schedule

The file without the suffix "handout" includes animations; the "handout" version is for ease of printing.

1. Introduction (4 hours)     Slides: Introduction, Introduction-handout (last updated: 2026/03/05 04:46)
   • Syllabus
   • Asymptotic Notations (KT 2.2)
   • Common Running Times (KT 2.4)
2. Basic Graph Algorithms (4 hours)     Slides: GraphBasics, GraphBasics-handout (last updated: 2026/03/02 03:24)
   • 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. Data Structures (4 hours)    
   • Priority Queue and Heap, Binary Search Tree, Union-Find
4. Divide and Conquer (8 hours)      Slides: DivideAndConquer, DivideAndConquer-handout (last updated: 2026/03/02 03:25)
   • 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. Greedy Algorithms (6 hours)     Slides: Greedy, Greedy-handout (last updated: 2026/03/02 03:25)
   • 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)
6. Midterm Exam (2 hours)
6. Dynamic Programming (6 hours)      Slides: DynamicProgramming, DynamicProgramming-handout (last updated: 2026/03/02 03:25)
   • 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
7. Graph Algorithms (6 hours)      Slides: GraphAlgorithms, GraphAlgorithms-handout (last updated: 2026/03/02 03:25)
   • 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)
8. Network Flow (8 hours)      Slides: NetworkFlow, NetworkFlow-handout (last updated: 2026/03/02 03:25)
   • 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)
9. NP-Completeness (8 hours)      Slides: NPC, NPC-handout (last updated: 2026/03/02 03:25)
   • 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)
10. Advanced Topics (6 hours)      Slides: AdvancedTopics, AdvancedTopics-handout (last updated: 2026/03/02 03:25)
    • 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)
11. Final Review (4 hours)
12. Final Exam in Exam Week (3 hours)