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!)

• The midterm exam is scheduled in the class on 2024/4/18.

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

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/04/16 15:48)
   • 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: 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/04/18 08:34)
   • 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/04/18 08:46)
   • 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)
    • TBD