CSE 431/531
Algorithm Analysis and Design
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, besides 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.
Pre-requisite: 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.
Instructor Information
Course Instructor: Jue Guo
- Research Area: Optimization for machine learning, Adversarial Learning, Continual Learning and Graph Learning
- Interested in participating in our research? Reach to me by email.
Course Outline and Logistics
Check out the course material under lecture notes.
Course Hours: Session [S]; MoWe 4:00PM - 6:20PM
Office Hours: 3:00pm - 4:00pm on Friday
Grader: Kristopher Kodweis (kkodweis@buffalo.edu)
| Week | Session | Date | Topics/Activities |
|---|---|---|---|
| 1 | Session 1 | May 28, 2025 | Introduction to algorithms; basic arithmetic and modular arithmetic (Chapter 1: Algorithms with Numbers). |
| 2 | Session 2 | June 2, 2025 | Primality testing, cryptography, and universal hashing; overview of randomized algorithms (Chapter 1). |
| 2 | Session 3 | June 4, 2025 | Divide-and-conquer algorithms: multiplication, recurrence relations, and an introduction to mergesort (Chapter 2: Divide‐and‐Conquer Algorithms). |
| 3 | Session 4 | June 9, 2025 | Continuation of divide-and-conquer: mergesort, medians, matrix multiplication, and the fast Fourier transform (Chapter 2). |
| 3 | Session 5 | June 11, 2025 | Graph decompositions: depth-first search in undirected and directed graphs, and strongly connected components (Chapter 3: Decompositions of Graphs). |
| 4 | Session 6 | June 16, 2025 | Graph paths: breadth-first search, Dijkstra's algorithm, and priority queue implementations (Chapter 4: Paths in Graphs). |
| 4 | Session 7 | June 18, 2025 | Greedy algorithms: minimum spanning trees, Huffman encoding, and set cover (Chapter 5: Greedy Algorithms). |
| 5 | Session 8 | June 23, 2025 | Midterm Exam (covers Weeks 1–4). |
| 5 | Session 9 | June 25, 2025 | Dynamic programming: longest increasing subsequences, edit distance, and knapsack (Chapter 6: Dynamic Programming). |
| 6 | Session 10 | June 30, 2025 | NP-complete problems: definitions, NP-completeness, and reductions (Chapter 8: NP-complete Problems). |
| 6 | Session 11 | July 2, 2025 | Coping with NP-completeness: exhaustive search, approximation algorithms, and local search heuristics (Chapter 9: Coping with NP-completeness). |
| 7 | Session 12 | July 7, 2025 | Final Exam and Course Review (includes selected topics from Chapters 7 and 10). |
Evaluation Components
| Component | Weight / Details |
|---|---|
| Attendance | 10% (Random Attendance Check) |
| Programming Assignments | 30% (2 PAs) |
| Midterm | 30% |
| Final | 30% |
Note on Logistics
- A week-ahead notice for mid-term, based on the pace of the course.
- The logistic is subject to change based on the overall pace and the performance of the class.
Grading
The following is the outline of the grading:
Grading Rubric
This course is absolute grading, meaning no curve, as there is a certain standard we need to uphold for students to have a good knowledge of algorithm.
| Percentage | Letter Grade | Percentage | Letter Grade |
|---|---|---|---|
| 95-100 | A | 70-74 | C+ |
| 90-94 | A- | 65-69 | C |
| 85-89 | B+ | 60-64 | C- |
| 80-84 | B | 55-59 | D |
| 75-79 | B- | 0-54 | F |
Lecture Notes
The lecture notes are primarily based on the textbook Algorithms, 1st Edition by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (ISBN-13: 978-0072190434). While this text provides an excellent foundation, students often face challenges with some derivations due to missing intermediate steps. To address these issues, I have expanded the derivations and included detailed explanations to enhance clarity and comprehension.
For additional insights and supplementary materials, please refer to the resource available on my shared overleaf.
The lecture notes are continually updated, so please check back regularly for the latest versions and improvements.