CSE 531B: Algorithm Analysis and Design (Spring 2025)


• Course Syllabus: Detailed course content, including grading policy, academic integrity policy, accessibility resources, etc.

Course Logistics

Lecture Time: Tue, Thu 2:00PM-3:20PM (Section B)

Lecture Location: Hoch 114 (Section B)

Instructor: Kelin Luo

Office Hour: Tue, Thu 12:30PM-13:30PM

Except for the office hours provided, you can also set up an appointment (by email) for additional office hours.

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

Please sign up for the course on Piazza. You can post all questions related to lectures, quiz, and assignments on Piazza. Instructor posts announcement on piazza.

TAs and Graders Information (TBD)

Teaching Assistants:

Mohammad Jakir Hossain
Hao Ban
Erfan Habibi Panah Fard
Zhipeng Zhao
Yujie Zhu
Shijie Zhou

Email:

[mh267][at][buffalo][dot][edu]
[haoban][at][buffalo][dot][edu]
[erfanhab][at][buffalo][dot][edu]
[zzhao43][at][buffalo][dot][edu]
[yzhu68][at][buffalo][dot][edu]
[shijiezh][at][buffalo][dot][edu]

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


References

Course information and lecture notes from previous years

  • UB CSE431/531B Algorithm Analysis and Design (2024 Fall) by Kelin Luo

  • 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 (ISBN: 978-0321295354)

  • [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

    [Jan 20, Mon] Course website online.
    [Jan 23, Thu] Quiz 1 on UBlearns. Quiz 1 (Join Piazza, Academic Integrity Quiz, MUST GET 100%) due 11 Feb@ 11:59PM.
    See Piazza -> News

    Slides and Assignments

    See Piazza -> Resources -> Lecture Notes

    Deadlines for Homeworks and Projects

    HWs/ProjectsReleasing DateDeadline
    HW1Jan 28Feb 11
    HW2Feb 18Mar 04
    HW3Mar 11Apr 01
    HW4Apr 15Apr 29
    Project 1Feb 11Mar 11
    Project 2Mar 25Apr 15

    Note: (1) Both homeworks and projects deadlines are at 11:59 PM EST. Expectations will be clearly noted when the assignments come out as well as the duration of the assignment. Please pay attention to the amount of time that each assignment provides and begin early. (2) Submit the typed PDF submission for homeworks. You are free to format your submissions using any word processor of your choice. Both Microsoft Word and LaTeX are recommended options. Additionally, for web-based LaTeX editing, you can explore platforms such as Overleaf. (3) Both homeworks and projects will be submitted and returned via UBlearns.

    Tentative Schedule

    WeekDateTopicContentsOther Notes
    1 Jan 23 Introduction Course Syllabus and Introduction to Algorithms
    2Jan 28 Asymptotic Analysis, Big O, Omega and Theta, Running Times (KT 2.2, 2.4)
    Jan 30 Graph Basics Graph Notations (KT 3.1, 3.2), Graph Types and Traversal (KT 3.4)
    3Feb 04 Bipartiteness Test and Topological Order (KT 3.4, KT 3.6)
    Feb 06 Greedy Algorithms Box Packing (KT 4.1)
    4Feb 11 Interval Scheduling (KT 4.1) and Interval Partition HW1 Deadline
    Feb 13 Optimum Caching (KT 4.3)
    5Feb 18 Huffman Code (KT 4.8)
    Feb 20 More Greedy Algorithm Exercise and Midterm #1 Review
    6Feb 25 Midterm #1 Midterm #1 Exam (2:00PM-3:20PM at Hoch 114)
    Feb 27 Divide and Conquer Merge Sort and Counting Inversions (KT 5.1, KT 5.3)
    7Mar 04 Quick Sort and Selection Problem (KT 13.5) HW2 Deadline
    Mar 06 Polynomials Multiplication (KT 5.5), Solving Recurrences (KT 5.2)
    8Mar 11 More Divide and Conquer Algorithm Exercise P1 Deadline
    Mar 13 Dynamic Programming Weighted Interval Scheduling (KT 6.1)
    9Mar 18 Spring Break, no class
    Mar 20 Spring Break, no class
    10Mar 25 Subset Sum Problem and Knapsack Problem (KT 6.4)
    Mar 27 Sequence Alignment (KT 6.6) and Matrix Chain Multiplication
    11Apr 01 Optimum Binary Search Tree and Midterm #2 Review HW3 Deadline
    Apr 03 Midterm #2 Midterm #2 Exam (2:00PM-3:20PM at Hoch 114)
    12Apr 08 Graph Algorithms Minimum Spanning Tree and Kruskal's Algorithm (KT 4.5)
    Apr 10 Reverse-Kruskal's Algorithm and Prim's Algorithm for MST (KT 4.6)
    13Apr 15 Shortest Paths and Dijkstra's Algorithm (KT 4.4) P2 Deadline
    Apr 17 Bellman-Ford Algorithm and Floyd-Warshall Algorithm (KT 6.8)
    14Apr 22 NP-Completeness P, NP, Co-NP(KT 8.1-8.3)
    Apr 24 NP-hard, NP-complete, Polynomial Reduction (KT 8.4)
    15 Apr 29 Circuit-SAT, 3-SAT, Independent Set Problem (KT 8.5) HW4 Deadline
    May 01 Solve NP-hard Problems and Approximation Algorithm
    16 May 06 Last Day of Classes, Recap/Review/Questions
    Final Exam: May 13, Tuesday, 11:45 - 14:45 at Nsc 201