Jue Guo
← All courses

CSE 431/531 · Undergraduate and graduate

Algorithm Analysis and Design

An introduction to the design and analysis of algorithms: asymptotic analysis, divide and conquer, greedy algorithms, dynamic programming, fundamental graph algorithms, NP-completeness, and approximation algorithms.

Each topic is covered in depth and anchored in one or more representative problems and their algorithms. Beyond designing and analyzing algorithms, students build the discrete-mathematics problem-solving skills that every computer scientist and engineer relies on.

Every module has a full set of notes, linked from the outline below: the ideas and proofs in plain language, working Python for each algorithm with its real output, figures, and exercises.

What the course covers

  1. Foundations
  2. Week 1 Prologue: why algorithms, and big-O; algorithms with numbersFibonacci three ways, big-O notation; arithmetic on n-bit numbers and modular arithmetic.
  3. Week 2 Primality, cryptography, and hashing; divide and conquer beginsFermat's test, RSA, universal hashing, and randomized algorithms; fast multiplication and recurrences.
  4. Week 3 Divide and conquer continued; decompositions of graphsMergesort, medians, Strassen, and the FFT; depth-first search, DAGs, and strongly connected components.
  5. Graphs and greedy algorithms
  6. Week 4 Paths in graphs; greedy algorithmsBFS, Dijkstra, priority queues, Bellman–Ford; minimum spanning trees, Huffman codes, set cover.
  7. Week 5 Midterm exam; dynamic programmingThe midterm covers weeks 1–4. Then longest increasing subsequences, edit distance, and knapsack; the notes go on to chain matrix multiplication, shortest paths, and independent sets in trees.
  8. Hard problems
  9. Week 6 NP-complete problems; coping with NP-completenessP, NP, and reductions; backtracking, approximation algorithms, and local search.
  10. Week 7 Review and final examCourse review, including selected topics from chapters 7 and 10 (read in DPV; no course notes).

How the course runs

Two sessions a week; each covers about one chapter. The exercises at the end of each module are good practice for the quizzes, the assignments, and the exams: try to write each proof yourself before checking it against the notes.

  • Attendance (10%) — random attendance checks during the term.
  • Programming assignments (30%) — two assignments, implementing and analyzing algorithms from the course.
  • Weekly quizzes (5%) — a short online quiz each week.
  • Midterm exam (25%) — in week 5, covering weeks 1–4.
  • Final exam (30%) — in week 7.

The midterm date is announced a week ahead, and the schedule may change with the pace of the class. Grades use an absolute scale with no curve: 95–100 A, 90–94 A−, 85–89 B+, 80–84 B, 75–79 B−, 70–74 C+, 65–69 C, 60–64 C−, 55–59 D, below 55 F.

Getting set up

The code in the notes is plain Python 3 (version 3.9 or newer) with only the standard library, so any recent installation — or a free Google Colab notebook in the browser — runs every example. Type the examples yourself and change them: the fastest way to understand a running-time claim is to test it.

Course policies

Collaboration

Discussing the modules and the assignments with classmates at the level of ideas is encouraged, but your assignment code must be your own. Helping someone debug an error message is fine; sharing code or results is not.

AI and LLM use

  • Allowed without disclosure: autocomplete-style help (syntax lookups, translating code between libraries), debugging individual error messages, and reading recommendations.
  • Allowed with disclosure: explanations of concepts or proofs you are stuck on, and suggested approaches after you have thought the problem through. A one-line note in your submission is enough.
  • Not allowed: generating quiz answers, assignment solutions, or proofs with an LLM. Undisclosed LLM-generated work is an academic-integrity violation.

When in doubt, disclose. Disclosure costs you nothing; non-disclosure can cost you the course.