Algorithm Design and Analysis (Spring 2026)

Course Information

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

Logistics

Instructor's Office Hours	:	Wednesdays 11:00am-12:00pm
Location	:	计算机系楼605
TA	:	To be announced

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, linear programming, and reductions of problems.
• NP-completeness and the boundaries of computation.
• Advanced topics: Randomized algorithms, approximation algorithms, fixed-parameter tractability, and online algorithms.

Prerequisites include:

• Basic skills in formulating mathematical proofs.
• Data structures: Linked lists, stacks, queues, priority queues, trees, and graphs.
• Programming experience in Python, C, C++, or Java.

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 and DeepSeek 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 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

Homework must be submitted electronically via email to the TA. We strongly encourage the use of LaTeX. You may answer in Chinese or English. Handwritten work must be scanned clearly.

Syllabus and Tentative Schedule

Slides are provided at least 2 weeks before the topic is covered. 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/02/15 00:43)
   • Asymptotic Notations (KT 2.2), Common Running Times (KT 2.4)
2. Basic Graph Algorithms (5 hours)     Slides: GraphBasics, GraphBasics-handout (last updated: 2026/02/15 00:43)
   • Connectivity, Traversal (KT 3.2, 3.4), and Topological Sort (KT 3.6)
3. Data Structures (5 hourrs)    
   • Priority Queue and Heap, Binary Search Tree, Union-Find
4. Divide and Conquer (7 hours)      Slides: DivideAndConquer, DivideAndConquer-handout (last updated: 2026/02/15 00:43)
   • Merge Sort (KT 5.1), Recurrences (KT 5.2), FFT (KT 5.6)
5. Greedy Algorithms (6 hours)     Slides: Greedy, Greedy-handout (last updated: 2026/02/15 00:43)
   • Interval Scheduling (KT 4.1), Optimum Caching (KT 4.3), Huffman Code (KT 4.8)
6. Dynamic Programming (6 hours)      Slides: DynamicProgramming, DynamicProgramming-handout (last updated: 2026/02/15 00:42)
   • Knapsack (KT 6.4), Sequence Alignment (KT 6.6), Matrix Chain Multiplication
7. Graph Algorithms (6 hours)      Slides: GraphAlgorithms, GraphAlgorithms-handout (last updated: 2026/02/15 00:43)
   • MST (Kruskal/Prim), Dijkstra's (KT 4.4), Bellman-Ford/Floyd-Warshall (KT 6.8)
8. Network Flow (6 hours)      Slides: NetworkFlow, NetworkFlow-handout (last updated: 2026/02/15 00:42)
   • Max Flow/Min Cut (KT 7.1-7.2), Bipartite Matching (KT 7.5)
9. NP-Completeness (6 hours)      Slides: NPC, NPC-handout (last updated: 2026/02/15 00:43)
   • P, NP, Co-NP (KT 8.1-8.3), NP-Completeness and Reductions (KT 8.4-8.7)
10. Advanced Topics (7 hours)      Slides: AdvancedTopics, AdvancedTopics-handout (last updated: 2026/02/15 00:43)
    • Randomized Algorithms, Exponential Time Algorithms, Fixed Parameterized Tractability, Approximation Algorithms