Algorithm Design and Analysis (Spring 2024)

Course Information

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

Logistics

Instructor's Office Hours: Wednesdays 10:00am-11:00am
Location: 计算机系楼605
TA: 白思睿 (srbai)
We will create a QQ group for the class.

News (check regularly!)

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:

Prerequisites of the course include

Textbook

The following book is required for the course:


The "CLRS" book is also a good reference book:

Grading

Your final grade will be computed as follows:

Both exams will be closed-book.

Policies for Homeworks and Programming Assignments

Homeworks and Programming Assignments

HWs/PAsReleasing DateDeadline
HW12024/03/052024/03/17
HW22024/03/242024/04/07
HW32024/04/072024/04/21
PA12024/04/072024/05/19
HW42024/04/182024/05/05
HW52024/05/052024/05/19
HW62024/05/192024/06/02
PA22024/05/192024/06/23
HW72024/05/312024/06/12
HW82024/06/072024/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.

  1. 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)
  2. 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)
  3. 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)
  4. 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)
  5. 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
  6. 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)
  7. 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)
  8. 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
  9. 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)
  10. 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)
  11. Final Review      Slides Final Review