| CSE431/531A Lecture Time | Location |
|---|---|
| Mon & Wed & Fri, 2:00PM - 2:50PM | Knox 104 |
| CSE531B Lecture Time | Location |
|---|---|
| Mon & Wed & Fri, 4:00PM - 4:50PM | Clemen 120 |
| Role | Name | Office Hours |
|---|---|---|
| Instructor | Kelin Luo (kelinluo@buffalo.edu) | Mon & Wed 12PM-12:50PM |
| TA | Erfan Habibi Panah Fard (erfanhab@buffalo.edu) | Tue 12PM-12:50PM |
| TA | Gagan Chandan (gaganch2@buffalo.edu) | Thu 12PM-12:50PM |
Except for the office hours provided, you can also set up an appointment (by email) for additional office hours.
Please sign up for the course on Piazza.
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.
Course Credits: 3
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, Task, Exam |
| 2. Have a good overall picture of algorithm analysis and design techniques | Quiz, Homeworks, Projects, Task, 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 |
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.
There are no required textbooks, but most of the content we will discuss is covered in the following books:
Similar courses taught at other universities:
Your final grade will be computed as follows:
Quizzes: 15% = 1% × (15 quizzes).
Quizzes will be given during lectures or via UBlearns.
Automatic Proof Assistant Tasks: 10% = 5% × 2 (Lean tasks).
Homeworks and Programming Projects: 25% = 5% × 5
(4 homeworks + 2 projects).
Midterm Exams: 20% = 10% × 2 (Mid Exam I and Mid Exam II).
Final Exam: 30%.
Each component will receive a numerical score. The course grade will be based on the weighted total of all components.
Quizzes: We will select the best 15 scores out of 16-17 quizzes. Although the weight is relatively low, quizzes are essential for learning concepts and algorithms. Problems similar to quiz and homework problems may appear on exams. You must score 100% on the Academic Integrity Quiz 1, or you will receive an F in the course.
Automatic Proof Assistant Tasks: Students will complete two small tasks using the interactive theorem prover LEAN. The use of LLM tools is permitted.
Homeworks and Programming Projects: We will select the best 5 scores out of 6 assignments.
Exams: 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).
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. Grades will not be curved/adjusted during the semester.
| Percentage | Letter Grade |
|---|---|
| >= 90 | A |
| 85 ~ 89 | A- |
| 70 ~ 74, 75 ~ 79, 80 ~ 84 | B-, B, B+ |
| 55 ~ 59, 60 ~ 64, 65 ~ 69 | C-, C, C+ |
| 50 ~ 55 | D |
| < 50 | F |
Questions or requests for the instructor, TAs, or graders should be posted on Piazza; if the matter is private, please create a new post and select Instructors only. Email should be used only as a secondary option if posting on Piazza is not possible.
UB Learns should be used only for quizzes, assignment submission, and grade checking.
Your homework written solution should be typeset. You may use any word processor of your choice; Microsoft Word and LaTeX are recommended. For web-based LaTeX editing, you may use platforms such as Overleaf. You should view your submission after you upload it to make sure that it is not corrupted or malformed. Submissions that are rotated, upside down, or that do not load will not receive credit. Illegible submissions may also lose credit depending on what can be read. Ensure that your final submission contains all pages.
You are responsible for making sure your submission went through successfully.
Please start all assignments early! Excuses that you did not have enough time for an assignment will not be considered. Extraordinary circumstances will be considered at the discretion of the instructor (not the TAs), contact the instructor via e-mail if you think these apply to you.
All assignments are due at the date and time posted. Late assignments will be accepted for up to 2 days after the deadline (based on the UBlearns submission timestamp), with penalties applied as follows. Penalties are applied automatically, even if a submission is late by just 1 second.
If your latest submission is:
Exams/Assignments: Exams/assignment grades will be posted on UBLearns. You can look up graded exam/assignments from the UBLearns. Questions about exam/assignment grades should be sent on Piazza via private post within one week after the grade is posted on UBLearns. If you are not satisfied with the TA’s response, you should contact the instructor no later than 2 days after the TA’s response.
No regrade requests will be considered after the deadlines mentioned above.
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
Failure to follow university academic integrity policies will be treated as cheating and a violation of academic integrity. For details, see:
Individual Work: Homework and projects must be completed individually. You may use lecture notes, libraries, and books, but you must properly cite all sources.
Prohibited Sources: Copying or aggregating solutions from online sources (e.g., Stack Overflow, Google, YouTube) or previous semesters is considered cheating, even if cited.
Collaboration: You may discuss problems with classmates after attempting them independently. However:
Use of AI Tools: Generative AI tools (e.g., ChatGPT) may be used only when explicitly permitted. Failure to follow guidelines may constitute an academic integrity violation. If unsure, ask.
Responsibility: Statements such as “I did not know” or “I was not sure” are not acceptable. When in doubt, consult the instructor or TAs.
In accordance with university and departmental policy:
First violation:
At minimum, a letter grade reduction in the course and a zero on the assignment/exam. Severe cases may result in an F in the course.
Second violation:
Automatic F in the course.
Reporting:
All violations will be reported to the Office of Academic Integrity (OAI), the Department, and the School.
For departmental policies, see:
We recognize that students may make mistakes under pressure. If you believe you have violated academic integrity, you may withdraw your submission before it is discovered by emailing the instructor using 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
In this case:
All course materials are provided for students’ educational use only. Without prior written permission, students may not:
Course materials include lectures, notes, assignments, exams, slides, and other instructional content.
Unauthorized distribution may:
This course allows the use of generative AI tools (e.g., ChatGPT) on certain assignments (Automatic Proof Assistant Tasks) 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.
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 the Accessibility Resources
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.
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
Health Services
Health Promotion
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.
Here are some free university resources:
Writing Support:
UB Center for Excellence in Writing
Equipment Loans (Computers, Devices):
UB Libraries Equipment Loans
Counseling Services:
UB Counseling Services