CSE 531C: Algorithm Analysis and Design (Fall 2023)

Course Description

This course introduces the design and analysis of algorithms, a fundamental aspect of computer science. Throughout the course, we will get to know fundamental algorithm concepts, exploring a range of topics including greedy algorithms, divide-and-conquer algorithms, dynamic programming, and graph algorithms. In addition, we will apply these techniques to both the development and analysis of algorithms for significant problems, such as scheduling, caching, sorting, the knapsack problem, matrix multiplication, shortest path algorithms, minimum spanning tree algorithms, and more. Moreover, the course will cover the limitations of algorithms, including concepts like NP-completeness theory and approximation algorithms. By the end of this course, you'll have a solid understanding of these essential algorithms and their applications, as well as an appreciation for the theoretical insights that guide algorithmic design and analysis.

Lecture Time: Mon-Wed-Fri 04:00PM - 04:50PM

Lecture Location: Nsc 201

Credits: 3

Please sign up for the course on Piazza.

Instructor and TAs Information

Instructor: Kelin Luo

Office Location: 306 Davis Hall

Office Hour: Mon-Wed-Fri 09:00AM - 09:50AM (Except for the office hours provided for Algorithm course Section B and Section C, you can also schedule an appointment with me via email for additional office hours.)

Email: [first name][last name][at][buffalo][dot][edu]

Teaching Assistants:

Davoud Moradi
Xiaoyu Zhang
Xuelu Feng
Ibrahim Bahadir Altun
Yuxin Liu

Office Hour:

Tue, Thu: 11:10AM - 12:00AM
Wed, Fri: 03:00PM - 03:50PM
Mon, Wed: 02:00PM - 02:50PM
Tue, Thu: 10:00AM - 10:50AM
Tue, Wed: 10:00AM - 10:50AM



Note: See the office location and Zoom link on Piazza.


You should have taken CSE250 (data structure) or similar courses before. We expect you to have certain levels of mathematical maturity: You should have basic understanding of calculus (e.g., limit, differentiation, integration) and linear algebra (e.g., matrix, vector space, linear transformation); You should be comfortable to read and write mathematical proofs, understanding common proof strategies (e.g., proof by induction, contradiction). We also expect you to have some programming experience: know what is a computer program, and be able to read and write code.


Your final grade will be computed as follows:
* Class Participation: 5% = 1% × (5 quizzes). Quizzes will be given randomly during the lectures.
* Homeworks: 40% = 8% × (5 homeworks). We choose the best 5 scores out of 6 homeworks.
* Programming Projects: 20% = 10% × (2 programming projects).
* Final Exam: 35%.
Note: (1) Each component will receive a numerical score. The course grade will be based on the weighted total of all components. (2) Class participation includes attendance, participation in class discussions, or quizzes. We will choose the best 5 scores out of a total of 8-10 quizzes for grading. (3) The final exams will be closed-book, and closed-notes.

Academic Integrity Policy:

* Collaboration and Discussions: You are permitted to engage in discussions with your classmates regarding homework problems. However, it is strongly recommended that you invest sufficient time thinking about each problem independently before engaging in discussions. All solutions must be written in your own words and produced by you individually. If you collaborate with fellow students, you must provide their names when submitting your work.
* Use of Artificial Intelligence Technologies: The use of generative artificial intelligence, large language models (LLMs), and other artificial intelligence-related technologies is generally prohibited. This encompasses tools like OpenAI's ChatGPT, Google Bard, and AI models within search interfaces like Google or Bing. Utilizing these tools for course content creation, debugging assistance, idea generation, or similar purposes constitutes a breach of academic integrity. All work submitted for evaluation in this course must be exclusively your own.
* Consequences for Violations: Failure to follow to the aforementioned rules will be treated as cheating and a violation of academic integrity. In addition to receiving an immediate grade of F for the course, further actions in alignment with theDepartment's Academic Integrity Policy and theUniversity's Academic Integrity Policy will be taken.


Course information and lecture notes from previous years

  • UB CSE431/531 Algorithm Analysis and Design (2022 Fall) by Shi Li
  • Recommended Textbooks

    There are no required textbooks, but most of the contents we will discuss are covered in the following books:

  • [KT] Algorithm Design, by Jon Kleinberg and Eva Tardos
  • [TCRC] Introduction To Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
  • Other Course References

    Similar courses taught in other universities:

  • UIUC CS473: Algorithms (2020)
  • Stanford CS161: Design and Analysis of Algorithms (2020)
  • News

    [Aug 28, Mon] Course website online.
    [Aug 28, Mon] Quiz 1: sign up on Piazza before 01 Sep 11:59PM EST.
    [Sep 01, Fri] Quiz 2: Complete the exercise on the final page of the Lecture slides from Sep 01. (The details regarding submission and deadlines will be announced on Wednesday, Sep 06.)
    [Sep 06, Wed] Quiz 2: Go to Ublearns (https://ublearns.buffalo.edu/d2l/login)-Log in to Brightspace-Course CSE 531C-Assessments-Quizzes. You have 2 attempts for Quiz 2, with each attempt having a time limit of 20 minutes. The deadline is 08 Sep 11:59PM EST.
    [Sep 08, Fri] Homework 1: The HW1 will be released on Monday, Sep 11. Highly recommendation: (1) use typing submission with LaTex, Word, or other document compilers; (2) use ``Ipe drawing editor'' to draw a figure.)
    [Sep 11, Mon] Homework 1: Go to Ublearns (https://ublearns.buffalo.edu/d2l/login)-Log in to Brightspace-Course CSE 431B/531B-Assessments-Assignments. The deadline is 25 Sep 11:59PM EST.
    [Sep 25, Mon] The deadline for HW 1 is 25 Sep 11:59PM EST. No late submission is allowed. The HW 2 will be released on 25 Sep 11:59PM EST and the deadline is 09 Oct 11:59PM EST.
    [Oct 02, Mon] The Programming project 1 will be released on 02 Oct and the deadline is 30 Oct 11:59PM EST.
    [Oct 04, Wed] During the Fall break, on Oct 9th and 10th, there will be no classes or office hours. If you have any questions, please don't hesitate to visit us during other office hours, or post your questions on Piazza, or schedule an appointment via Email.
    [Oct 9, Mon] The HW 3 will be released on 09 Oct and the deadline is 23 Oct 11:59PM EST.
    [Oct 11, Wed] The Quiz 4 will be held in the classroom on 13 Oct.
    [Oct 23, Mon] The Quiz 5 will be released on 23 Oct and the deadline for Quiz 5 is 25 Oct 11:59PM EST.
    [Oct 30, Mon] The Quiz 6 will be held in the classroom on 01 Nov.
    [Nov 01, Wed] The Quiz 6 group presentation will be held in the classroom on 03 Nov.
    [Nov 10, Fri] Quiz 7, which covers Kruskal and Prim algorithms, has been released. The deadline for Quiz 7 is 10th Nov at 11:59 PM EST.
    [Nov 15, Wed] The Quiz 8 (Dijkstra algorithm and DP algorithm for the shortest path problem with negative weights) will be released on 15 Nov and the deadline for Quiz 8 is 17 Nov 11:59PM EST.
    [Nov 29, Wed] Quiz 9, which covers P, NP, Co-NP, NP-Complete, will be released on 29 Nov. The deadline for Quiz 9 is 01 Dec at 11:59 PM EST.

    Slides and Assignments

    [Aug 28, Mon] [Slides] Introduction (1): Syllabus
    [Aug 30, Wed] [Slides] Introduction (2): Asymptotic notations
    [Sep 01, Fri] [Slides] Introduction (3): Common running times
    [Sep 06, Wed] [Slides] Graph basics (1): Graph basics and representation
    [Sep 08, Fri] [Slides] Graph basics (2): Connectivity and graph types
    [Sep 11, Mon] [Slides] Graph basics (3): Bipartiteness and topological order
    [Sep 13, Wed] [Slides] Graph basics (4): Topological order and Greedy algorithm (1): basics
    [Sep 15, Fri] [Slides] Greedy Algorithm (2): Box packing and interval scheduling
    [Sep 18, Mon] [Slides] Greedy Algorithm (3): Interval partitioning
    [Sep 20, Wed] [Slides] Greedy Algorithm (4): Offline caching
    [Sep 22, Fri] [Slides] Greedy Algorithm (5): Offline caching and heap
    [Sep 25, Mon] [Slides] Greedy Algorithm (6): Heap and Coding scheme
    [Sep 27, Wed] [Slides] Greedy Algorithm (7): Coding scheme and Exercise Problems
    [Sep 29, Fri] [Slides] Divide and Conquer (1): Basic merge sort
    [Oct 02, Mon] [Slides] Divide and Conquer (2): Counting inversions
    [Oct 04, Wed] [Slides] Divide and Conquer (3): Quick sort
    [Oct 06, Fri] [Slides] Divide and Conquer (4): LB, Selection and Polynomial Multiplication
    [Oct 11, Wed] [Slides] Divide and Conquer (5): Polynomial Multiplication and Master Theorem
    [Oct 13, Fri] [Slides] Divide and Conquer (6): More Divide-and-Conquer Algorithm Exercise Problems
    [Oct 16, Mon] [Slides] Divide and Conquer (7): Fibonacci number and Dynamic Programming (1): weighted interval scheduling
    [Oct 18, Wed] [Slides] Dynamic Programming (2): weighted interval scheduling and subset sum problem
    [Oct 20, Fri] [Slides] Dynamic Programming (3): Subset sum problem and Knapsack problem
    [Oct 23, Mon] [Slides] Dynamic Programming (4): Knapsack problem and Sequences
    [Oct 25, Wed] [Slides] Dynamic Programming (5): Longest common subsequence
    [Oct 27, Fri] [Slides] Dynamic Programming (6): Edit distances and shortest path in DAG
    [Oct 30, Mon] [Slides] Dynamic Programming (7): Matrix chain multiplication and Optimal binary search tree
    [Nov 01, Wed] [Slides] Dynamic Programming (8): Optimal binary search tree and Summary until 01 Nov
    [Nov 06, Mon] [Slides] Graph Algorithms (1): MST
    [Nov 08, Wed] [Slides] Graph Algorithms (2): Kruskal Algorithm
    [Nov 10, Fri] [Slides] Graph Algorithms (3): Reverse Kruskal and Prim'algorithm
    [Nov 13, Mon] [Slides] Graph Algorithms (4): Shortest path and Dijkstra's algorithm
    [Nov 15, Wed] [Slides] Graph Algorithms (5): Shortest paths with negative weights and Bellman-Ford algorithm
    [Nov 17, Fri] [Slides] Graph Algorithms (6): All pair shortest paths and Floyd-Warshall algorithm
    [Nov 20, Mon] [Slides] Graph Algorithms (7): Floyd-Warshall Alg, Summary and NP-Completeness (1): Introduction
    [Nov 27, Mon] [Slides] NP-Completeness (2): P, NP, Co-NP
    [Nov 29, Wed] [Slides] NP-Completeness (3): NP-complete, Polynomial reduction
    [Dec 01, Fri] [Slides] NP-Completeness (4): More Polynomial reductions and Solve NP-hard problems
    [Dec 04, Mon] [Slides] NP-Completeness (5): NPC summary, Introduction summary and Graph Basics summary

    Deadlines for Homeworks and Projects

    HWs/ProjectsReleasing DateDeadline
    HW1Sep 11Sep 25
    HW2Sep 25Oct 09
    HW3Oct 09Oct 23
    HW4Oct 23Nov 13
    HW5Nov 13Nov 27
    HW6Nov 27Dec 06
    Project 1Oct 02Oct 30
    Project 2Nov 06Dec 04

    Note: (1) Both homeworks and projects deadlines are at 11:59 PM EST. (2) Late submission for homework and project assignments will not be accepted under any circumstances. (3) Strongly suggest to submit the typed submission, e.g. latex.

    Syllabus and Tentative Schedule

    WeekDateTopicContentsOther Notes
    1 Aug 28 Introduction course syllabus
    Aug 30 asymptotic notations (KT 2.2)
    Sep 01 running times and exercise problems (KT 2.4)
    2 Sep 04 Labor Day Observed, no class
    Sep 06 Graph Basics graph basics (KT 3.1, 3.2)
    Sep 08 representation and types of graphs
    3Sep 11 connectivity and traversal (KT 3.4) HW1 Released
    Sep 13 topological order (KT 3.6)
    Sep 15Greedy Algorithms basics, interval scheduling (KT 4.1)
    4 Sep 18 interval scheduling (KT 4.1)
    Sep 20 optimum caching (KT 4.3)
    Sep 22 optimum caching and exercise problems
    5Sep 25 huffman code (KT 4.8) HW 1 Deadline
    HW 2 released
    Sep 27 More Greedy Algorithm Exercise Problems
    Oct 29 Divide and Conquer basic merge sort (KT 5.1, 5.3)
    6 Oct 02 merge sort and counting inversions (KT 5.1, 5.3) Project 1 released
    Oct 04 counting inversions and quick sort (KT 5.3, KT 13.5)
    Oct 06 selection problem and Exercise problems (KT 13.5)
    7 Oct 09 Fall Break, no class HW 2 deadline
    HW 3 released
    Oct 11 solving recurrences and fibonacci number (KT 5.2)
    Oct 13 More Divide-and-Conquer Algorithm Exercise Problems
    8 Oct 16 Dynamic Programming weighted interval scheduling (KT 6.1)
    Oct 18 subset sum problem (KT 6.4)
    Oct 20 knapsack problem (KT 6.4)
    9 Oct 23 sequence alignment (KT 6.6) HW 3 deadline
    HW 4 released
    Oct 25 shortest paths
    Oct 27 matrix chain multiplication
    10 Oct 30 Optimum binary search tree Project 1 deadline
    Nov 01 More Dynamic Programming Algorithm Exercise Problems
    Nov 03 Graph Algorithms minimum spanning tree and Kruskal's algorithm (KT 4.5)
    11 Nov 06 Reverse-Kruskal's algorithm and Prim's algorithm for MST (KT 4.6) Project 2 released
    Nov 08 shortest paths and Dijkstra's algorithm (KT 4.4)
    Nov 10 Dijkstra's algorithm and exercise problems (KT 4.4)
    12 Nov 13 shortest paths with negative weights and Bellman-Ford algorithm (KT 6.8) HW 4 deadline
    HW 5 released
    Nov 15 all-pair shortest paths and Floyd-Warshall algorithm
    Nov 17 More Graph Algorithm Exercise Problems
    13 Nov 20 NP-Completeness P, NP, Co-NP (KT 8.1-8.3)
    Nov 22 Thanksgiving Break, no class
    Nov 24 Thanksgiving Break, no class
    14 Nov 27 polynomial time reductions and NP (KT 8.4) HW 5 deadline
    HW 6 released
    Nov 29 circuit-SAT, 3-SAT (KT 8.5)
    Dec 01 independent set problem and more exercise problems (KT 8.5)
    15 Dec 04 HW solutions, Q & A Project 2 deadline
    Dec 06 HW 6 deadline
    Dec 08
    16 Dec 11 Last Day of Classes, Q & A
    Dec 19, Tuesday, 15:30-18:30: Final Exam, at Nsc 201