YP-DSA

The way I teach it

Preface

I have been teaching CSS 342 and 343 at UW Bothell since 2017. Before that I ran the Games Studio at UTS in Sydney for almost twenty years. Before that I built knowledge representation systems for my PhD at Northwestern. The throughline across all of it: people learn by doing, not by reading. This book is here to keep the reading short so you can get back to doing.

Reader, I am here to say: if you are taking my class, you are in the right place. If you are not, you are also in the right place. The material is general, the examples are LeetCode-flavored, the code compiles.

0.1 What this book is

Two courses, twenty lectures each, forty chapters total.

• Part I (CSS 342): C++ mechanics, STL containers, pointers, classes, the Rule of Three, templates, recursion, complexity, sorting, induction, linked lists, binary trees.
• Part II (CSS 343): balanced trees, heaps, graphs, hash tables, divide-and-conquer, greedy, dynamic programming, OOP design patterns, regex, finite automata, Turing machines.

Each chapter is one 120-minute lecture. If you sit in the room, you get the live coding, the whiteboard arrows, and my accent. If you do not, you get this.

0.2 How I teach

A few things you should expect, because they are on every page.

Code first. I do not introduce a concept by defining it. I show you a problem, write the code, and we talk about what just happened. If you skim the prose, you can still pass an exam. If you skip the code, you cannot.

Warmups on the first slide. Every lecture opens with a LeetCode warmup. Sometimes it has nothing to do with that day’s topic, sometimes it has everything to do with it, and I will not always tell you which. Try the warmup before reading the chapter.

Debug lines stay in. When I write code in class I leave the cout statements that helped me debug it. Sometimes I comment them out, sometimes I do not, but they do not get cleaned up. The mess is the point.

int binarySearch(const vector<int>& v, int target) {
  int lo = 0;
  int hi = v.size() - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    // cout << "lo: " << lo << ", hi: " << hi << ", mid: " << mid << endl;
    if (v[mid] == target) return mid;
    if (target < v[mid]) hi = mid - 1;
    else lo = mid + 1;
  }
  return -1;
}

That commented-out cout was there for a reason. You will see this pattern in every binary search in this book. Run it. Then comment it back out.

Helper before caller. When I decompose a problem I write the helper function first, then the function that calls it. All bottom-up. If you see a function signature you do not recognize, scroll down a paragraph.

The same problem, multiple ways. isPalindrome shows up for int, vector<int>, string, and ListNode* across different chapters. Same logical question, different containers. Algorithms are separable from the structures they run over, and the only way to feel that is to see it.

A good programmer is one who can recognize patterns. That is the line I repeat most often in class. Patterns over recipes. Once you see the pattern, the implementation usually follows.

0.3 On AI

I will not pretend AI does not exist. I use Claude and Gemini daily. Some of this book was drafted with AI assistance. I edited every line. The persona files for YPai (my digital office hours) sit two directories over, and the rendering of voice you are reading was tuned against those files.

If you use AI to do your homework, you will fail my exams. If you use AI to learn faster, you will do well. As I keep telling my students: I use AI to draft. I do not use AI to think.

0.4 What is “interactive” about an interactive book?

Each chapter has:

• A warmup with a link to the LeetCode problem and, where available, my own submission for comparison.
• Live code blocks that you can copy directly into a .cpp file and compile. Every block here compiles with g++ -Wall -std=c++17.
• Common-mistake callouts (red), the things students consistently get wrong, with the bug visible.
• Pisan’s notes (green), short asides where I tell you what I would say in lecture. Usually fewer than three sentences.
• Try-it boxes, small problems where you should stop reading and write code.
• Self-check quizzes, multiple choice, designed to catch the misconception you are most likely to be holding.
• Challenges, three to five LeetCode problems per chapter, in difficulty order.

The book is built with Quarto. Spotted something I got wrong (there will be things)? Let me know in #book-feedback on the course Discord.

0.5 How to read this book

If you are taking the class, read the chapter corresponding to the upcoming lecture before class. Do the warmup. The 120 minutes of lecture will then be reinforcement and live coding, not first exposure.

If you are not taking the class, read in order. Each chapter assumes the previous ones. You can skip Lectures 11, 12, and 15 (the discrete math lectures) on a first pass if you only want the data structures and algorithms.

If you only have a weekend, read:

1. Chapter 4 (Pointers and Memory)
2. Chapter 7 (Copy Constructors and the Rule of Three)
3. Chapter 9 (Recursion)
4. Chapter 13 (Algorithm Analysis)
5. Chapter 17 (Binary Trees Intro)
6. Chapter 25 (Heaps)
7. Chapter 33 (DP I)

That sequence will give you 70% of the value in 20% of the pages.

0.6 A note on the textbook

CSS 342 has historically used Data Abstraction and Problem Solving with C++ (Walls and Mirrors) by Carrano and Henry. That book is a fine reference. This is not its replacement. This is the parallel track, the working notes, the thing my students kept asking me to write down. Read them together if you want both views.

0.7 Thanks

To every CSS 342 and CSS 343 student who pushed back when something was unclear, asked the question on Discord at 1 AM, or sent me a corrected solution that was better than mine. This book is mostly yours.

Yusuf Woodinville, WA

Pet Policy: if a pet enters your camera frame during a Zoom lecture, we pause for introductions and admiration by all. All pets are welcome. Sadly this does not extend to the in-person classroom.