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


Course Description

Introduces basic elements of the design and analysis of algorithms. Topics include asymptotic notations and analysis, divide and conquer, greedy algorithms, dynamic programming, fundamental graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, we discuss one or more representative problems and their algorithms. In addition to the design and analysis of algorithms, students are expected to gain substantial discrete mathematics problem solving skills essential for computer scientists and engineers.

Lecture Time: Tue, Thu 11:00PM - 12:20PM

Lecture Location: Nsc 215

Credits: 3

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.

Instructor and TAs Information

Instructor: Kelin Luo

Office Location: 306 Davis Hall

Office Hour: Tue 09:30 - 10:30 and 12:30-13:30, Thu 12:30 - 13:30

Except for the office hours provided, you can also schedule an appointment with me via email for additional office hours at least two days in advance.

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

Teaching Assistants:

Ibrahim Bahadir Altun
Yuxin Liu
Chen Xu
Wen Zhang

Office Hour:

Fri 9:00 - 11:00
Thu 9:00 - 11:00
Mon 9:00 - 11:00
Wed 9:00 - 11:00

Email:

[ialtun][at][buffalo][dot][edu]
[yuxinliu][at][buffalo][dot][edu]
[chenxu][at][buffalo][dot][edu]
[wzhang59][at][buffalo][dot][edu]


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

Prerequisite

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.

Learning Outcomes:

Master the fundamental concepts in algorithm analysis and design.

Learning Outcomes Method of Assessment
1. Proficiently understand and apply asymptotic notations and analysis Quiz, Homeworks, Final Exam
2. Have a good overall picture of algorithm analysis and design techniques Quiz, Homeworks, Projects, Final Exam
3. Solve simple to moderately difficult algorithmic problems arising in applications Quiz, Homeworks, Projects, Final Exam
4. Understand the notions of NP-completeness and approximation algorithms Quiz, Homeworks, Final Exam
5. Be able to demonstrate the hardness of simple NP-complete problems Homeworks, Final Exam

Grading:

Your final grade will be computed as follows:
* Class Participation: 10% = 1% × (10 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: 30%.
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 10 scores out of a total of 12-15 quizzes for grading. (3) Although the weight of quiz is relatively low, it is a very important and essential part for learning concepts and algorithms. Problems similar to quiz and homework problems may appear in final exams. (4) The final exams will be closed-book, and closed-notes.

Grading Policy:

The following outlines the grade breakdown that will be utilized for assigning grades in the course. Please note that these ranges may be subject to adjustment at the end of the semester to address any inconsistencies or hardships that may arise. It is important to emphasize that grades will not be curved/adjusted during the semester.

Grade Percentage
A 90% - 100%
A- 85% - 89.99%
B+ 80% - 84.99%
B 75% - 79.99%
B- 70% - 74.99%
C+ 65% - 69.99%
C 60% - 64.99%
C- 55% - 59.99%
D 50% - 54.99%
F Below 50%

Re-grading

If you have a question about the grading of any piece of work, first consult with the teaching assistant who graded your work on Piazza. If you cannot resolve your questions with the teaching assistant, you should consult with the instructor. Any questions about the grading of a piece of work must be raised within one week of the date that the work was returned by the teaching assistant or the instructor.

Academic Integrity Policy:

Academic integrity is a fundamental university value. Through the honest completion of academic work, students sustain the integrity of the university and of themselves while facilitating the university's imperative for the transmission of knowledge and culture based upon the generation of new and innovative ideas. For more information, please refer to theGraduate Academic Integrity policy.
* Collaboration and Discussions: You are permitted to engage in discussions with your classmates regarding homework problems. Prior to discussing, please take the time to thoroughly consider each problem independently. 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 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.

General Resources:

Here are some of the University's available free resources:
* If you need help with writing, check UB Center for Excellence in Writing theWriting Support Services
* If you have issues with your device, the UB University Libraries provides access to computers, as well as equipment loans, see theEquipment Loans
* Your well-being is highly important, if you have any concerns, please check theCounseling Service

Accessibility Resources:

If you have any disability which requires reasonable accommodations to enable you to participate in this course, please contact the Office of Accessibility Resources in 60 Capen Hall, 716-645-2608 and also the instructor of this course during the first week of class. The office will provide you with information and review appropriate arrangements for reasonable accommodations, which can be found on the web at theAccessibility Resources.

References

Course information and lecture notes from previous years

  • UB CSE431/531 Algorithm Analysis and Design (2023 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 22, Mon] Course website online.
    [Jan 25, Thu] Quiz 1: sign up on Piazza before 02 Feb 11:59PM EST.
    [Jan 30, Tue] Quiz 2 covering the asymptotic analysis of lectures on January 30th and February 1st, will be made available on Ublearns on February 1st.
    [Feb 01, Thu] Quiz 2: Go to Ublearns (https://ublearns.buffalo.edu/d2l/login)-Log in to Brightspace-Course CSE 531B-Assessments-Quizzes. You have 2 attempts for Quiz 2, with each attempt having a time limit of 30 minutes for 6 problems (multiple choice, True/False). The deadline is 02 Feb 11:59PM EST.
    [Feb 06, Tue] Homework 1: Go to Ublearns (https://ublearns.buffalo.edu/d2l/login)-Log in to Brightspace-Course CSE 531B-Assessments-Assignments. The deadline is 20 Feb 11:59PM EST.
    [Feb 08, Thu] Quiz 3 covering the Graph Basics on Feb 06th and Feb 08th, will be made available on Ublearns on Feb 13th.
    [Feb 13, Tue] Quiz 3 is released on Ublearns. The deadline is 14 Feb 11:59PM EST.
    [Feb 15, Thu] Quiz 4 covering the Greedy Algorithm (Box Packing, Interval scheduling, interval partition and Offline caching problems) on Feb 13th and Feb 15th, will be made available on Ublearns on Feb 20th.
    [Feb 20, Tue] Quiz 4 is released on Ublearns. The deadline is 21 Feb 11:59PM EST. We will have an in-class quiz consisting of group discussions and presentations over the next two classes. Further details will be provided on Thursday, February 22nd.
    [Feb 22, Thu] Quiz 5 (presentation part) is scheduled for Tuesday, February 27.
    [Feb 29, Tue] Quiz 6 covering the Divide and Conquer Algorithm (Merge Sort and Quick Sort) on Feb 29th and Mar 5th, will be made available on Ublearns on Mar 5th.
    [Mar 05, Tue] Quiz 6 is released on Ublearns. The deadline is 06 Mar 11:59PM EST.
    [Mar 07, Thu] Quiz 7 (group discussion) about Divide and Conquer algorithm will be scheduled on Tuesday, March 12.
    [Mar 12, Tue] Quiz 7 (presentation part) is scheduled for Thursday, March 14.
    [Mar 26, Tue] Quiz 8 covering the Weighted interval scheduling problem and Subset Sum Problem on March 14th and Mar 26th, will be made available on Ublearns on Mar 28th.
    [Mar 28, Thu] Quiz 8 is released on Ublearns. The deadline is 29 Mar 11:59PM EST.
    [Apr 02, Tue] Quiz 9 class attendance on 02 Apr or 04 Apr.
    [Apr 04, Thu] Quiz 10 (group discussion) about Dynamic Programming algorithm will be scheduled on Tuesday, Apr 09.
    [Apr 09, Tue] Quiz 10 (presentation part) is scheduled for Thursday, April 11.
    [Apr 18, Thu] Quiz 11 covering the minimum spanning tree problem is scheduled for Thursday, April 18.
    [Apr 23, Tue] Quiz 12 covering the shortest path problem will be scheduled on Thursday, April 25.
    [Apr 25, Thu] Quiz 12 is released on Ublearns. The deadline is 26 Apr 11:59PM EST.
    [Apr 25, Thu] Quiz 13 is released in class (show a polynomial reduction from HC to HP). Please submit it before the start of the next class (Tuesday, 30 Apr).
    [Apr 30, Tue] Quiz 14 covering the NPC theorem, will be made available on Ublearns on May 2nd.
    [May 02, Thu] Quiz 14 is released on Ublearns. The deadline is 04 May 11:59PM EST. This is the last quiz.
    ......

    Slides and Assignments

    [Jan 25, Thu] [Slides] Introduction (1): Course Syllabus and Algorithms
    [Jan 30, Tue] [Slides] Introduction (2): Algorithms and Big O notations
    [Feb 01, Thu] [Slides] Introduction (3): Big Omega and Theta notations
    [Feb 06, Tue] [Slides] Graph Basics (1): Graph Notations, Types, Bipartiteness
    [Feb 08, Thu] [Slides] Graph Basics (2): Bipartiteness Test and Topological Order
    [Feb 13, Tue] [Slides] Greedy Algorithm (1): Box Packing and Interval Scheduling
    [Feb 15, Thu] [Slides] Greedy Algorithm (2): Interval Partition and Offline Caching
    [Feb 20, Tue] [Slides] Greedy Algorithm (3): Offline Caching and Heap
    [Feb 22, Thu] [Slides] Greedy Algorithm (4): Heap and Huffman Code
    [Feb 27, Tue] [Slides] Greedy Algorithm (5): Huffman Code
    [Feb 29, Thu] [Slides] Divide and Conquer Algorithm (1): Merge Sort and Quick Sort
    [Mar 05, Tue] [Slides] Divide and Conquer Algorithm (2): Lower Bounds, Selection problem, Polynomials
    [Mar 07, Thu] [Slides] Divide and Conquer Algorithm (3): Polynomials Multiplication and Fibonacci number
    [Mar 12, Tue] [Slides] Divide and Conquer (4) and Dynamic Programming Algorithm (1): Weighted Interval Scheduling
    [Mar 14, Thu] [Slides] Dynamic Programming Algorithm (2): Weighted Interval Scheduling
    [Mar 26, Tue] [Slides] Dynamic Programming Algorithm (3): Subset Sum Problem
    [Mar 28, Thu] [Slides] Dynamic Programming Algorithm (4): Knapsack and LCS Problem
    [Apr 02, Tue] [Slides] Dynamic Programming Algorithm (5): Edit distance and Shortest path in DAG
    [Apr 04, Thu] [Slides] Dynamic Programming Algorithm (6): Matrix Chain Multiplication and Binary Search Tree
    [Apr 09, Tue] [Slides] Graph Algorithm (1): Minimum Spanning Tree: Kruskal's algorithm
    [Apr 16, Tue] [Slides] Graph Algorithm (2): Minimum Spanning Tree: Prim's algorithm
    [Apr 18, Thu] [Slides] Graph Algorithm (3): Shortest path problem: Dijkstra algorithm and Bellman-Ford algorithm
    [Apr 23, Tue] [Slides] Graph Algorithm (4): Shortest path problem: Floyd-Warshall algorithm and NPC (1)
    [Apr 25, Thu] [Slides] NPC (2): P, NP, Co-NP
    [Apr 30, Tue] [Slides] NPC (3): NP-complete, NP-hard
    [May 02, Thu] [Slides] NPC (4): NPC theorem summary
    ......

    Deadlines for Homeworks and Projects

    HWs/ProjectsReleasing DateDeadline
    HW1Feb 06Feb 20
    HW2Feb 20Mar 05
    HW3Mar 05Mar 19
    HW4Mar 26Apr 09
    HW5Apr 09Apr 23
    HW6Apr 23May 07
    Project 1Feb 13Mar 12
    Project 2Mar 19Apr 30

    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) Submit the typed PDF submission. 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.

    Syllabus and Tentative Schedule

    WeekDateTopicContentsOther Notes
    1 Jan 25 Introduction course syllabus
    2Jan 30 asymptotic notations (KT 2.2)
    Feb 01 common running times (KT 2.4)
    3Feb 06 Graph Basics graph basics, connectivity and traversal (KT 3.1, 3.2, 3.4) HW 1 released
    Feb 08 topological order (KT 3.6)
    4Feb 13 Greedy Algorithm basics, interval scheduling (KT 4.1, 4.2) Project 1 released
    Feb 15 optimum caching (KT 4.3)
    5Feb 20 huffman code (KT 4.8) HW 1 deadline
    HW 2 released
    Feb 22 More Greedy Algorithm Exercise Problems
    6Feb 27 Divide and Conquer merge sort and counting inversions (KT 5.1, 5.3)
    Feb 29 quicksort, median-finder, selection (KT 13.5)
    7Mar 05 polynomial and matrix multiplications (KT 5.5) HW 2 deadline
    HW 3 released
    Mar 07 solving recurrences and fibonacci number (KT 5.2)
    8Mar 12 More Divide and Conquer Algorithm Exercise Problems Project 1 deadline
    Mar 14 Dynamic Programming weighted interval scheduling (KT 6.1)
    9Mar 19 Spring Break, no class HW 3 deadline
    Project 2 released
    Mar 21 Spring Break, no class
    10Mar 26 subset sums and knapsack (KT 6.4) HW 4 released
    Mar 28 shortest paths and Matrix-Chain-Multiplication
    11Apr 02 Optimum Binary Search Tree
    Apr 04 More Dynamic Programming Algorithm Exercise Problems
    12Apr 09 Graph Algorithms Kruskal's algorithm for MST (KT 4.5) HW 4 deadline
    HW 5 released
    Apr 11 Prim's algorithm for MST (KT 4.6)
    13Apr 16 Dijkstra's algorithm for shortest path (KT 4.4)
    Apr 18 Bellman-Ford, Floyd-Warshall (KT 6.8)
    14Apr 23 NP-Completeness P, NP, Co-NP (KT 8.1-8.3) HW 5 deadline
    HW 6 released
    Apr 25 polynomial time reductions and NP (KT 8.4)
    15Apr 30 circuit-SAT, 3-SAT (KT 8.5) Project 2 deadline
    May 02 independent set problem and more exercise problems (KT 8.5)
    16 May 07 Last Day of Classes, Q & A HW 6 deadline
    May 09, Thursday, 15:30-18:30: Final Exam, at Nsc 225