About

Welcome to my notes dump!

I spend a lot of time thinking about how to teach algorithms, and I realize that I should probably spend some time writing my ideas down. This page is a rough and incomplete approximation of how I'd teach an algorithms class, updated whenever I decide to write down a new set of notes or rethink what belongs in the course. Given that I learned algorithms from UC Berkeley's CS170, these notes will likely be influenced by them.

Material is divided into three types: core, supporting, and peripheral.

  • Core: Knowledge that I consider essential to a basic understanding of algorithms. It may assume that you are familiar with the prior core material.
  • Supporting: Proofs, examples, questions, or anything else I consider to be helpful but not necessary to understand the concepts. It will almost certainly build upon the core material.
  • Peripheral: Tangents that are almost certainly unnecessary but I found personally interesting enough to think about (and type up). Likely to feel like when you ask your friend about a topic they're very invested in and you want them to stop talking but they're just so excited about it.

Material assumes a CS1-equivalent background (control flow, data structures), as well as familiarity with math up to calculus. More familiarity in CS and in mathematics is helpful but not necessary.

Please feel free to use these notes if you'd like (for non-commercial purposes, obviously)! If you have any questions, feel free to reach out at liujon23 (at) berkeley (dot) edu. I also happily welcome any civil discussion/suggestions/criticisms about these notes.

Part 1: Introduction

What are algorithms, why should we think about them, and how should we think about them?

Core Material

  • Why do we care about algorithms?
  • Algorithmic analysis

Supporting Material

  • How (not) to think about algorithms
  • A more formal definition of Big-O notation

Part 2: Algorithm Design

Some big ideas we'll encounter repeatedly when talking about algorithms.

Core Material

  • Greedy Algorithms
  • Dynamic Programming
  • Linear Programming
  • Divide and Conquer
  • Graph Algorithms

Supporting Material

  • A proof of Master Theorem
  • Mechanism Design
  • Cryptography

Peripheral Material

Part 3: Computational Complexity

How we classify the difficulty of computational questions.

Core Material

  • P and NP
  • Reductions and completeness
  • Randomized Algorithms

Supporting Material

  • Turing Machines
  • Interactive Proofs
  • Game Theory