CSE 531A: Algorithm Analysis and Design (Fall 2025)

Syllabus


Please note: It is your responsibility to make sure you read and understand the contents of this syllabus. If you have any questions, please contact the instructor.

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: Mon, Wed, Fri 4:00PM-4:50PM (Section A)

Lecture Location: Cooke 121 (Section A)

Credits: 3

Instructor and TAs Information (TBD)

Instructor: Kelin Luo

Office Location: 306 Davis Hall

Office Hour: Mon, Wed 12:30PM-01: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]

Teaching Assistants and Graders:

Yujie Zhu
Qiang Hu
Tianyang Zhang
Yi Du
Atharva Bhalchandra Wadekar

Email:

[yzhu68][at][buffalo][dot][edu]
[qhu5][at][buffalo][dot][edu]
[tzhang52][at][buffalo][dot][edu]
[yidu][at][buffalo][dot][edu]
[wadekar][at][buffalo][dot][edu]

Note: See the office hours, 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, Exam
2. Have a good overall picture of algorithm analysis and design techniques Quiz, Homeworks, Projects, Exam
3. Solve simple to moderately difficult algorithmic problems arising in applications Quiz, Homeworks, Projects, Exam
4. Understand the notions of NP-completeness and approximation algorithms Quiz, Homeworks, Exam
5. Be able to demonstrate the hardness of simple NP-complete problems Homeworks, Exam

TextBooks

There is no textbook for the course. All needed materials will be provided via the course's website and Piazza.

Computing Resources:

You will be using various free on-line tools for this course -- links will be posted on the course website.

* All assignments such as quiz, homework, and project assignments will be both submitted and returned via Ublearns.
* Any email communications must come from your UB email account and include [CSE 531A] in the subject line. All communications with course staff are expected to be professional.
* Any course-related communications should be via the Piazza forum linked from the course website. Piazza posts can be either public to the class or private to instructors.

Grading:

Your final grade will be computed as follows:

* Quizzes: 20% = 2% * (10 quizzes). Quizzes will be given during the lectures or UBlearns.
* Automatic Proof Assistant Tasks: 5% = 2.5% * 2.
* 4 Homeworks and 2 Programming Projects: 25% = 5% * 5 (highest 5 out of 6 assignments).
* Mid-term Exam: 20% = 10% * (2 in-class Mid-term exam).
* 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) Quizzes: We will choose the best 10 scores out of a total of 12-13 quizzes for grading. 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 exams. (3) Automatic Proof Assistant Tasks: Students will be assigned two small tasks involving the use of an interactive theorem prover LEAN. The use of LLM tools is permitted for these tasks. Students may earn bonus points by successfully completing an additional algorithmic task. (4) The mid-term and final exams will be closed-book, and closed-notes. However, you can bring in a single 8.5x11 inch paper in a mid-term exam and bring in two 8.5x11 inch paper in final exam (you can use both sides; The sheet must be typed or scanned and must include your name and UBID. Please do not write on the cheatsheet). (5) You must score a 100% on the Academic Integrity quiz or you will be given an F in the course.

Deadlines for Homeworks and Projects

HWs/ProjectsReleasing DateDeadline
HW1Aug 27Sep 08
HW2Sep 08Sep 22
HW3Oct 13Oct 27
HW4Nov 17Dec 01
Project 1Sep 29Oct 20
Project 2Oct 20Nov 17
Task 1Sep 22Oct 06
Task 2Oct 27Nov 10

Note: (1) All assignments deadlines are on Monday 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) All assignments will be submitted and returned via UBlearns.

Late Policy for Homeworks and Projects Assignments

Late assignments will be accepted up to 2 days late (based on the UBlearns submission timestamp) for a penalty of 50% of the total points (lower your earned points by 50% of the possible points for the entire assignment). Please keep track of the time if you are working up until the deadline. Submissions become late after the set deadline, even by 1 minute. Keep in mind that submissions will close 48 hours after the original deadline and you will no longer be able to submit your assignment after that time. If your latest submission was submitted:

* On or before the deadline: 100% of what you earn.
* Late penalty to 1 day (< 24 hours): 25% point penalty.
* Late penalty to 2 days (< 48 hours): 50% point penalty .
* > 2 days late: 0 points.

Attendance and Participation

Attendance in lecture is not mandatory, but highly encouraged. Lectures will typically be recorded, but recordings have been known to get corrupted; do not count on lecture recordings. No makeup in-class quiz will be given except in provably extreme circumstances.

Exams

There will be two in-class 50-minute midterm exams and one 3-hour final exam. Each midterm is worth 10% of your grade each. The final exam is worth 30% of your grade. We reserve the right to change the scaling of the exams. No makeup exams will be given except in provably extreme circumstances.

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, please consult on Piazza. Any questions about the grading of a piece of work must be raised within one week (and the regrade deadline posted on Piazza) of the date that the work was returned by the teaching assistant or the instructor.

Incomplete (I) grades

Please see the University rules on an Incomplete. Assignment of an ''I'' grade is at the discretion of the instructor.
The last day to resign the course is Wednesday, Nov 12, 2025.

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 the Undergraduate Academic Integrity policy and Graduate Academic Integrity policy.

Procedures for Academic Integrity Violations

Failure to follow to the university academic integrity policy will be treated as cheating and a violation of academic integrity. For more information, please refer to theUndergraduate Academic Integrity Procedures and Graduate Academic Integrity Procedures.

What is Allowed and What is Not Allowed

* Homework and project assignments must be completed individually. Using reference materials from lecture notes, libraries, or books is allowed, provided that you explicitly cite these sources in your submission. However, copying or aggregating solutions from online sources (e.g., Stack Overflow, Google, YouTube, or other platforms) or from previous semesters is still considered cheating, even if you cite the sources.

* 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.

* This course allows the use of generative AI tools (e.g., ChatGPT) on certain assignments within given guidelines. Failure to follow these guidelines may be considered a violation of UB's academic integrity policy. If you are unsure how and when generative AI can be used, be sure to ask.

* Excuses such as "I was not sure" or "I did not know" will not be accepted. If you are not sure, ask the TAs and/or the instructor.

Academic Integrity Violation Sanctions

In accordance with the current university and departmental policy on academic integrity violations, we will follow this sanctions:

* If the violation is the first ever academic violation, then it will result in a minimum of a letter grade reduction in the course and zero in the relevant assignment/exam. If the violation is serious enough, then it can result in an F in the course.
* If the violation is the student's second academic violation, then it will result in an automatic F letter grade in the course.
* All the violation (whether it's the first or second instance) will be reported to the Office of Academic Integrity (OAI), the Department, and the School, as required by the University policy Academic Integrity.

For more details, please see The Computer Science and Engineering department's policy on academic integrity can be found here:Department's undergraduate Graduate Academic Integrity Policy andDepartment's Graduate Academic Integrity Policy.

Amnesty Policy

We understand that students are under a lot of pressure and people make mistakes. If you have concerns that you may have violated academic integrity on a particular assignment, and would like to withdraw the assignment, you may do so by sending me an email BEFORE we discover it. The email should take the following format:

Dear Dr. Luo,
I wish to inform you that on assignment X, the work I submitted was not entirely my own. I would like to withdraw my submission from consideration to preserve academic integrity.
J.Q. Student
Person #12345678
UBIT: jqstuden

When we receive this email, student J would receive a 0 on assignment X, but would not receive an F for the course, and would not be reported to the office of academic integrity.

Policy on improper distribution of course materials

All materials prepared and/or assigned by me for this course are for the students' educational benefit. Other than for permitted collaborative work, students may not photograph, record, reproduce, transmit, distribute, upload, sell or exchange course materials, without my prior written permission. "Course materials" include, but are not limited to, all instructor-prepared and assigned materials, such as lectures; lecture notes; discussion prompts; study aids; tests and assignments; and presentation materials such as PowerPoint slides, Prezi slides, or transparencies; and course packets or handouts. Public distribution of such materials may also constitute copyright infringement in violation of federal or state law. Violation of this policy may additionally subject a student to a finding of "academic dishonesty" under the Academic Integrity policy and/or disciplinary charges under the Student Code of Conduct.

Critical Campus Resources:

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.

Sexual Violence

UB is committed to providing a safe learning environment free of all forms of discrimination and sexual harassment, including sexual assault, domestic and dating violence and stalking. If you have experienced gender-based violence (intimate partner violence, attempted or completed sexual assault, harassment, coercion, stalking, etc.), UB has resources to help. This includes academic accommodations, health and counseling services, housing accommodations, helping with legal protective orders, and assistance with reporting the incident to police or other UB officials if you so choose. Please contact UB’s Title IX Coordinator at 716-645-2266 for more information. For confidential assistance, you may also contact a Crisis Services Campus Advocate at 716-796-4399

Mental Health

As a student you may experience a range of issues that can cause barriers to learning or reduce your ability to participate in daily activities. These might include strained relationships, anxiety, high levels of stress, alcohol/drug problems, feeling down, health concerns, or unwanted sexual experiences. Counseling, Health Services, and Health Promotion are here to help with these or other issues you may experience. You can learn more about these programs and services by contacting:
Counseling Services:
● 120 Richmond Quad (North Campus), 716-645-2720
● 202 Michael Hall (South Campus), 716-829-5800
Health Services:
● 4350 Maple Rd, Amherst, NY 14226, 716-829-3316
Health Promotion:
● 114 Student Union (North Campus), 716-645-2837

Diversity

The UB School of Engineering and Applied Sciences considers the diversity of its students, faculty, and staff to be a strength, critical to our success. We are committed to providing a safe space and a culture of mutual respect and inclusiveness for all. We believe a community of faculty, students, and staff who bring diverse life experiences and perspectives leads to a superior working environment, and we welcome differences in race, ethnicity, gender, age, religion, language, intellectual and physical ability, sexual orientation, gender identity, socioeconomic status, and veteran status.

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

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