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

TA: Jane Doe (jdoe@example.com)


Session Topics Covered
Session 1 Course Introduction, Algorithm Analysis
Session 2 Basic Data Structures
Session 3 Binary Search Trees and Balanced Binary Search Trees
Session 4 Priority Queues and Heaps
Session 5 Hash Tables, Union-Find Structures
Session 6 Sorting Algorithms (Merge-Sort, Quick-Sort, Selection)
Session 7 Midterm Exam (Covers Sessions 1–6)
Session 8 The Greedy Method
Session 9 Divide-and-Conquer
Session 10 Dynamic Programming
Session 11 Graph Algorithms (Traversals, Shortest Paths, MSTs)
Session 12 NP-Completeness, Approximation Algorithms, Final Exam Prep

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 deep learning.

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 Algorithm Design and Applications, 1st Edition by Michael T. Goodrich and Roberto Tamassia. While the book provides an excellent foundation, I have observed that students often face challenges understanding some derivations due to missing intermediate steps. To address this, I have expanded on these derivations and included detailed explanations to enhance clarity and comprehension.

The lecture notes are continually updated, so please check back regularly for the latest versions and improvements.

Topics Contents
Foundational Tools for Algorithms
  • Algorithm Analysis
  • Basic Data Structures
  • Useful Mathematical Facts
Trees and Hierarchical Data
  • Binary Search Trees
  • Balanced Binary Search Trees
  • B-Trees and External Memory
Hashing and Union-Find
  • Hash Tables
  • Union-Find Structures
Sorting and Selection
  • Merge-Sort
  • Quick-Sort
  • Fast Sorting and Selection
Algorithm Design Paradigms
  • The Greedy Method
  • Divide-and-Conquer
  • Dynamic Programming
Graph Algorithms
  • Graphs and Traversals
  • Shortest Paths
  • Minimum Spanning Trees
  • Network Flow and Matching
Computational Complexity
  • NP-Completeness
  • Approximation Algorithms
Randomized and Advanced Algorithms
  • Randomized Algorithms
  • The Fast Fourier Transform
  • Multidimensional Searching
  • Computational Geometry
  • String Algorithms
  • Cryptography
Optimization and Programming
  • Linear Programming