CSE 431B/531B: Algorithm Analysis and Design (Fall 2024)


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

Course Logistics

Lecture Time: Mon, Wed, Fri 02:00PM - 02:50PM (Section B)

Lecture Location: Knox 110 (Section B)

Instructor: Kelin Luo

Office Hour: Mon and Wed 03:00PM - 03:50PM

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

Teaching Assistants:

Xiaoyu Zhang
Ibrahim Bahadir Altun
Wen Zhang
Pratik Pokharel
Jason Niu
Mohammad Jakir Hossain
Sumaiya Islam Mouno

Email:

[zhang376][at][buffalo][dot][edu]
[ialtun][at][buffalo][dot][edu]
[wzhang59][at][buffalo][dot][edu]
[pratikpo][at][buffalo][dot][edu]
[jasonniu][at][buffalo][dot][edu]
[mh267][at][buffalo][dot][edu]
[smouno][at][buffalo][dot][edu]

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

Graders:

Kavitha Elizebeth Varughese
Xiaofeng Chen
Keshav Kumar Prabhakharan
Parag Shah

Email:

kavithae@buffalo.edu
xchen326@buffalo.edu
keshavku@buffalo.edu
paragsha@buffalo.edu

References

Course information and lecture notes from previous years

  • UB CSE431/531 Algorithm Analysis and Design (2024 Spring) 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

    [Aug 26, Mon] Course website online.
    [Aug 26, Mon] Quiz 1 on UBlearns. Quiz 1 (Join Piazza, Academic Integrity Quiz, MUST GET 100%) due 09 Sep@ 11:59PM.
    See Piazza -> News

    Slides and Assignments

    See Piazza -> Resources -> Lecture Notes

    Deadlines for Homeworks and Projects

    HWs/ProjectsReleasing DateDeadline
    HW1Sep 02Sep 16
    HW2Sep 23Oct 07
    HW3Oct 28Nov 11
    HW4Nov 18Dec 02
    Project 1Oct 07Oct 21
    Project 2Nov 04Nov 18

    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 dor 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 Aug 26 Introduction Course Syllabus
    Aug 28 Algorithm Pseudo Code and Asymptotic Analysis (KT 2.2)
    Aug 30 Big O, Big Omega and Theta Notations, Running Times (KT 2.4)
    2 Sep 02 Labor Day Observed, no class
    Sep 04 Graph Basics Graph Notations (KT 3.1, 3.2)
    Sep 06 Graph Types and Traversal (KT 3.4)
    3Sep 09 Bipartiteness Test and Topological Order (KT 3.4, KT 3.6)
    Sep 11 Greedy Algorithms Box Packing (KT 4.1)
    Sep 13 Interval Scheduling (KT 4.1)
    4 Sep 16 Interval Partition HW1 Deadline
    Sep 18 Optimum Caching (KT 4.3)
    Sep 20 Optimum Caching amd Huffman Code (KT 4.8)
    5Sep 23 Huffman Code (KT 4.8)
    Sep 25 More Greedy Algorithm Exercise and Midterm #1 Review
    Sep 27 Midterm #1 Midterm #1 Exam (2:00PM-2:50PM at Knox 110)
    6 Sep 30 Divide and Conquer Sorting Problem and Merge Sort (KT 5.1, 5.3)
    Oct 02 Counting Inversions (KT 5.3)
    Oct 04 Quick Sort and Selection Problem (KT 13.5)
    7 Oct 07 Polynomials Multiplication (KT 5.5) HW2 Deadline
    Oct 09 Solving Recurrences and Fibonacci Number (KT 5.2)
    Oct 11 More Divide-and-Conquer Algorithm Exercise Problems
    8 Oct 14 Dynamic Programming Fall Break, no class
    Oct 16 Weighted Interval Scheduling (KT 6.1)
    Oct 18 Subset Sum Problem (KT 6.4)
    9 Oct 21 Knapsack Problem (KT 6.4) P1 Deadline
    Oct 23 Sequence Alignment (KT 6.6)
    Oct 25 Matrix Chain Multiplication
    10 Oct 28 Optimum Binary Search Tree
    Oct 30 More Dynamic Programming Exercise and Midterm #2 Review
    Nov 01 Midterm #2 Midterm #2 Exam (2:00PM-2:50PM at Knox 110)
    11 Nov 04 Graph Algorithms Minimum Spanning Tree and Kruskal's Algorithm (KT 4.5)
    Nov 06 Reverse-Kruskal's Algorithm and Prim's Algorithm for MST (KT 4.6)
    Nov 08 Shortest Paths and Dijkstra's Algorithm (KT 4.4)
    12 Nov 11 Dijkstra's Algorithm (KT 4.4) HW3 deadline
    Nov 13 Shortest Paths with Negative Weights
    Nov 15 Bellman-Ford Algorithm (KT 6.8)
    13 Nov 18 Floyd-Warshall Algorithm P2 deadline
    Nov 20 More Graph Algorithm Exercise Problems
    Nov 22 NP-Completeness P, NP, Co-NP (KT 8.1-8.3)
    14 Nov 25 Polynomial Time Reductions and NP (KT 8.4)
    Nov 27 Thanksgiving Break, no class
    Nov 29 Thanksgiving Break, no class
    15 Dec 02 Circuit-SAT, 3-SAT (KT 8.5) HW4 Deadline
    Dec 04 Independent Set Problem (KT 8.5)
    Dec 06 Solve NP-hard Problems and Approximation Algorithm
    16 Dec 09 Last Day of Classes, Recap/Review/Questions
    Final Exam: Dec 11, Wednesday, 19:15-22:15 at NSC 215/225