Author: welcometotheoryland

A Beautiful Sum: Σ k · 2ᵏ

The other day I came across a post on Stack Overflow that asked for help working out a summation. As an intermediary step, I needed to evaluate the sum \sum_{k=0}^n k \cdot 2^k. This wasn’t a sum I’d seen before, and some quick Googling didn’t turn anything up. I managed to find this Wikipedia entry on arithmetico-geometric series, which gave me a closed-form, but I wasn’t very satisfied with having to look it up, especially given that the resulting formula was pretty messy.

When I was lying in bed that evening I realized that there was a beautiful connection between this sum and another one I’d seen, and that suggested a route for solving it. This morning I got up, put some animated slides together, and uploaded my very first YouTube video!

I think this is a beautiful derivation and love the multiple uses of sums of powers of two.

I’m thinking there’s almost certainly another route to solving this summation that routes through finite calculus. The sum is analogous to \int{x \cdot e^x dx}, given that the functions e^x and 2^x play similar roles in traditional and finite calculus as fixed points of the derivative operator. You can use integration by parts to show that \int{x \cdot e^x dx} = (x - 1)e^x + C, which works out pretty similarly to the resulting (n-2)\cdot 2^n + 2 that you get from the discrete sum. I think the extra “nudges” here are an artifact of the shift operator that shows up in finite calculus’ version of integration by parts, but I haven’t chased the details down yet.

In the meantime, I hope that if someone else in the future is looking for how to work out this sum, this saves you a lot of time and gives you a perspective on where the result comes from!

Design of an Assignment: The Labyrinth!

In Winter 2020, I designed a new assignment for CS106B entitled “The Labyrinth!,” which students generally reported positive experiences with and which seemed to do a good job teaching people how to use the debugger.

At a high level, the assignment asks students to explore randomly-generated mazes to find three items, after which they can escape from the labyrinth. What’s interesting about these mazes is how they’re represented. We provide students a struct type that looks like this:

struct MazeCell {
    string whatsHere; // Item present here, or empty if no items
    MazeCell* north;
    MazeCell* south;
    MazeCell* east;
    MazeCell* west;
};

The maze then consists of a collection of these cells all linked together in different ways. One of the cells is the starting location, and that’s what’s provided to students. They then need to explore the maze to find three items (a potion, a spellbook, and a wand). Specifically, students have to figure out where these items are by using the debugger. We ask them to grab a pen and paper and use the debugger to traverse the links, mapping out their route and seeing which nodes link to which other nodes, before they eventually find everything they need.

You can see the assignment spec here, and download the (Qt Creator) starter files here.

This post is about how I came up with the idea for the assignment and why it’s specifically designed the way that it is.

Part One: The Idea

One of the issues we’ve noticed over the years in CS106B is that our students aren’t always super comfortable using the debugger to understand what their code is doing. This can make debugging really tricky and frustrating, especially if they’re working on code with linked lists or walking through recursion. Starting in Winter 2017, I started adding a few smaller warm-ups to the assignments that asked students to work through some debugger exercises, just to make sure that they were comfortable with the basics. For example, the first assignment of the quarter asks them to step through a polynomial hash function to get an intermediate value, and the next one asks them to observe a stack overflow.

I had the idea in mind for a while that we should ask people to work through some sort of debugging exercise using linked structures so that they could better debug their code when they, say, miswired a linked list. It was tricky to figure out how to do this, though. Should we give people buggy code and ask them to find where an error is? Go through a guided tutorial to see how the debugger lets them inspect linked structures? Draw a picture of some state of memory?

For some reason my gut feeling was that the previous items might work, but would either (1) not be much fun for students to work through or (2) be hard to grade. There was also one auxiliary concern I had about each of these ideas – once one person had figured out how to solve the problem, they could easily share the answer with friends. (I was more worried about someone overhearing something else or being pestered by a friend for a hint, rather than someone posting the answer online for everyone to see.)

This reminded me of the Binary Bomb assignment developed by Bryant and O’Hallaron over at CMU. This classic assignment gives each student an executable that has been customized based on their student ID, then asks them to use the debugger to figure out how it works and “defuse the bomb” (enter correct passwords). I then started wondering – could we do something like this for linked structures?

That idea led me to think about using a hash of the student’s name as a random seed in an algorithm that would generate some sort of linked list or graph or something like that that students would then need to explore. But what would the “story” be here? How could we make this compelling? I had a few ideas of what might work here:

  • We could ask students to draw out a picture of some linked structure generated from a name hash. That’s not super exciting and it would be a pain to grade.
  • We could generate some sort of “linked structure art” based on the student’s name hash and have them draw that one out. I was thinking something along the lines of nonograms here. The problem is that this would require exploring a lot of linked space, which would be pretty tedious.
  • We could have the linked structure be a maze, with the goal to escape. “That’s a cool idea,” I thought, so I decided to pursue that one!

So now I have the basic idea in mind. We’re going to generate random mazes per student, then have them solve the maze.

Part Two: Workshopping

I’ve now got an idea – now, how do I turn this into an assignment?

The first question was how to encode the maze itself. I knew the general shape of the maze would be given by MazeCell objects that stored four pointers and some indicator of what item was present. I opted to name the pointers “north,” “south,” “east,” and “west” to make it easier to explore in the debugger. Although the “correct” way to indicate what item was present would be to use an enumerated type, we hadn’t actually covered enumerations at that point and so I opted to use std::string instead.

Then there was how to make the maze. In the past, I’ve used random maze generation as a motivation for various graph algorithms (Kruskal’s, DFS), so I’m not at all concerned about how to make this work. I can just create a 2D grid of cells, then add links between them to represent the maze. Having the cells fit into Euclidean space would also simplify the assignment, since the links between nodes would be somewhat “reasonable,” for some definition of “reasonable.”

But how do I ensure people actually use the debugger? The textbook we use, Eric Roberts’ “Programming Abstractions in C++,” includes a section on how to use recursive backtracking to solve mazes. Oops. If a student wanted to, they could just take this code and adjust it to solve the maze without learning to work the debugger. Honestly, I’d be pretty excited if a student did this, but I figured it wouldn’t be great if there was such an easy “trapdoor” for this. (As a note, we hadn’t covered general DFS or BFS at this point, so I wasn’t super worried about students finding out about those algorithms.)

This led me to make the first change to the basic idea: rather than finding a way out of a maze, let’s have them search the maze for three items. This is still solvable by backtracking or a graph search, but it’s a bit trickier because of the more involved state. Now, if someone wants to solve the maze without working the debugger, it’s a bit more involved. And that’s okay – the goal is to make the path of least resistance the actual intended path, not to make it impossible for folks to do anything else.

At this point, I had a clear statement for the problem that students would work through, and all that was left to do was to code up a prototype to see how it worked.

Part Three: Prototyping

I must admit that I had a lot of fun building out the prototype of this assignment. It was fun building a maze generator in C++. One step I was really proud of was in how I represented the edges in the grid graph. Since each cell had four named pointers representing the different directions of motion, to represent the idea of “connect this node with the node below it,” I needed some mechanism for saying “set the south field of this cell to the cell below it, and the north field of this cell to the cell above it.” That ended up leading me to use pointers-to-members to select out different fields from the MazeCell structs. In particular, I got to use the type MazeCell* MazeCell::* (a MazeCell* field inside of the type MazeCell), which was very fun to write.

Coding up Kruskal’s algorithm here wasn’t all that tricky, so I used that as my maze generator. I had considered using DFS, but liked how Kruskal’s algorithm tends to produce mazes with more, shorter branches rather than mazes with fewer, longer branches. That would make the “exploration” part more interesting.

I then ran into a question – how do I decide where to place items and the starting location? I could place them randomly, but then some students would have mazes where the items are all close to one another and other students would have mazes where the items were all far away. I initially decided on a compromise – we’d place the items sequentially, setting up “exclusion zones” around each item already placed. In particular, no item could be in the 3×3 box centered around any other item. After sketching out some math to convince myself that, indeed, any 4×4 maze could always have four items placed into it this way, I had a rough prototype that I sent out for review.

The initial version of the maze was a 5×4 grid. I thought this was an appropriate size, but the preliminary feedback from the course staff was that this was too much. I decided to scale this back to a 4×4 maze for the final version, which I think is still large enough to require some exploration but not so huge that it feels boring.

Part Four: Moving the Goalposts

I had set out to create an assignment where students would have to work the debugger to solve a maze, and at this point I had something that did just that. But then I started thinking more about what problems people actually have when working with linked structures. There are a lot of issues people have to learn to sort out when doing this:

  • Recognizing what a null pointer looks like.
  • Drawing pictures of what memory looks like.
  • Recognizing uninitialized pointers.
  • Recognizing deallocated pointers.

The assignment I’d put together accomplished only the first of these goals, and only kinda sorta ish hit the second. Specifically, students would get a feel for null pointers because those arise naturally in the maze (it means “you can’t move this way,”) and while they’d have to draw pictures to escape the maze, those pictures had a nice, well-defined shape because the maze generator always produces sensible mazes. Those last two, unfortunately, I wasn’t hitting at all.

I never did manage to find a way to get students to play around with uninitialized or deallocated pointers, since everyone’s best friend Undefined Behavior meant that I couldn’t predictably set things up on students’ machines so that they’d recognize this. That left only the “draw better pictures” goal, and I started wondering whether there was some way to get people to play around with that. I had in mind the goal of getting someone who had miswired a doubly-linked list to be able to say “oh, I see what I did wrong” and then fix their issue.

After some thought, I came up with a way of making the mazes a bit more interesting. What would happen if we linked the mazes in a way that formed an arbitrary graph where each node has degree at most four (north/south/east/west), but where the labels “north,” “south,” ‘east,” and “west” were totally arbitrary? That way, to draw the picture of the maze, you’d have to sketch out a more or less arbitrary diagram of linked nodes. I could even add cycles to the maze if I wanted to to ensure that students could recognize when they were going in circles.

This led me to come up with the “twisty labyrinth” problem as a follow-up to the basic labyrinth problem. We’d generate a random graph with the only restriction being that the graph was undirected – if there was an edge from one MazeCell to a second, the second MazeCell would have a link back to the first. Which links those were, though, would be more or less random. This would get people comfortable reading memory addresses and internalizing them as the idea of the “identity” of an object. I figured that if students could do this, they could certainly recognize that they miswired a linked list!

I decided to code up a maze generator for this version. That turned out to be a lot harder than I expected. I knew how to generate mazes using Kruskal’s algorithm or DFS, but now how to generate a random graph. How would we ensure each node didn’t have too many incoming edges? What if the graph wasn’t connected?

I did some reading on Erdos-Renyi random graphs and the probabilistic results about when they’re likely to have only one connected component. Based on that, I coded up a graph generator that builds an Erdos-Renyi random graph with each node having an 2 ln n / n probability of connecting to each other, then iterated this to generate graphs until we had one where each node had degree at most four and the graph was connected.

Then I ran into another issue – where to place items? Previously, I’d solved this using my notion of “exclusion zones,” but that wouldn’t easily generalize to this new version (it would be equivalent to finding an independent set of cardinality four, one for each item and one for the start position, and that wasn’t guaranteed to happen in small graphs). I decided to go for another approach instead. I coded up Floyd-Warshall and used that to compute the all-pairs distances between nodes. Then, I iterated over all 4-tuples of nodes, assigning each one a “score” consisting of a vector of the distances between those nodes, sorted from lowest to highest. I then picked the 4-tuple of nodes with the lexicographically highest “score” as the positions for the start point and the three items. This new system actually worked really well for the original maze – it always placed items in tree leaves and generally spaced things out so that you actually felt like you were exploring!

Solving these newer mazes is a lot trickier than solving the older ones, but the course staff had generally positive feedback about it and so I included it in the final version of the assignment.

Part Five: Last-Minute C++ Panic

The day before the assignment was slated to be released, I’d be doing some final checkups and polish – making sure the tests were good, that the instructions were clear, etc. I decided to do one final check. I had known that, in order for this assignment to work, the maze generator needed to be consistent from machine to machine. To address this, I’d used the new C++11 <random> library for maze generation. I seeded a std::mt19937 Mersenne Twister with a hash of the student’s name, and from that point forward always used the library random routines with that generator to produce the maze. This led to consistent maze generation from run to run.

So imagine my surprise when I found that the maze I got on my Mac was not the same as the maze I got on my Linux machine, even given the same seed. What a fun surprise with less than 24 hours to release!

I frantically started debugging to figure out what I’d done wrong. Was the hash function different on those machines? Nope – they go through the same code path, and I’d actually rewritten the hash code library the previous summer to clean things up a bit and knew it was deterministic. Was I accidentally using a function with a separate random source? Nope, that checked out as well. Was I using object addresses for something, and that was introducing nondeterminism? Turns out I was stashing object addresses in a set, but that wasn’t causing the issue.

With not much else to go on, I decided to just have the maze generator print out all the random decisions it was making. What edges was it processing? And in what order? Astonishingly, I found that despite using the same C++ standard library calls with the same random generator and the same seed, I wasn’t getting the same results across systems. Turns out, the C++ <random> library doesn’t actually specify which procedures are to be used in things like std::uniform_int_distribution or std::shuffle, though it does guarantee that std::mt19937 will be consistent across devices.

That turned out to be easy to fix – I just wrote some helper functions to do a Fischer-Yates shuffle and to generate a random integer in a given range given a std::mt19937. And with that, we were good to go!

Part Six: Release, and Moving Forward

We ended up rolling out the assignment and it went extremely smoothly – we got generally positive feedback and it seemed like students were comfortable working the debugger in precisely the ways we’d asked them to. Hurray!

I’m definitely planning on using this assignment in the future when talking about linked structures. It’s a simple and fun way to teach pointer debugging and gives the problem intrinsic “stakes.”

I suspect that this assignment is likely good to go “out of the box,” so to speak, for next time. The main changes I’d consider making are minor:

  • Although I didn’t discuss it here, there’s a warm-up coding component that asks students to validate that a particular path out of the maze works. This was both so that they can practice pointers in a simple setting and so that they can validate their solution once they find it. There are a couple of weird edge cases (what happens if you have a valid path as a prefix of a solution, then do something illegal? what happens if there are invalid characters?) that could be simplified to make things easier for students.
  • Maybe I was wrong about enumerated types and it would be best to replace that std::string field with an enumeration. That would make this a lot less error-prone when students are coding up that initial function.

Any other thoughts or suggestions? How can I make this better going forward?

How LR(2) Parsers Work

Many, many years back when I was a grad student, I picked up a phenomenal book on parsing: Parsing Techniques: A Practical Guide by Grune and Jacobs. That book was indispensable when I was teaching Stanford’s CS143 course on compiler design, and it taught me most of what I now know about parsing. Plus, it’s a great example of how to write a lucid introduction to difficult technical concepts.

One style of parsing that I didn’t learn a decade ago was LR(k) parsing with k > 1. This is a fairly uncommon style of parsing – I think it’s primarily of theoretical interest – but I was intrigued nonetheless. By following some leads from the book, asking some questions around on Stack Exchange, reading Knuth’s original paper On the Translation of Languages from Left to Right, and working through a few examples, I think I finally got a handle on how LR(2) parsing works, and the techniques that came up there are precisely what’s needed to handle more general LR(k) parsing.

I put together a writeup on LR(2) parsing on Stack Overflow, and I’m hoping that it’s a useful resource for other people interested in LR(k > 1) parsing in the future. It was fun to work through the details and examples, and I learned a bunch in the process!

From Skiplists to BSTs and Back

I’ve been teaching a course in advanced data structures (Stanford’s CS166) for many years now and in the course of doing so have learned some fascinating techniques. One of my favorites is the data structure isometry, where we use the shape of one data structure to guide the design of another. The most prominent example of this is how the red/black tree can be viewed as a representation of a 2-3-4 tree by pulling all the red nodes up into their parents. In this quarter’s offering of CS166, I explicitly taught how to derive red/black tree rotations by thinking about what the equivalent 2-3-4 tree would look like.

In one of the early offerings of CS166 (I think it may have been the inaugural 2014 edition?) one of the project teams presented on a method for making deterministic skiplists. The idea is similar to deriving the red/black tree:

  • Find a mechanism for encoding a general multiway tree as a skiplist.
  • Take the rules for a 2-3-4 tree and, one at a time, convert them into structural invariants on the skiplist.
  • Based on the encoding scheme, map the insertion and deletion algorithms of 2-3-4 trees onto the new skiplist.

This procedure gives you a deterministic skiplist where each operation has (amortized) costs of $O(\log n)$. The actual details aren’t particularly tricky, and I’ve been using this as a problem set exercise in CS166 for the past few years.

The other day, I came across a paper on a data structure called the zip tree that essentially runs this process the other direction – it begins with the randomized skiplist and uses it to build a randomized binary search tree. The idea is surprisingly similar to the one shown above:

  • Find a mechanism for encoding a skiplist as a binary search tree.
  • Take the rules for a randomized skiplist and, one at a time, convert them into structural invariants on the binary search tree.
  • Based on the encoding scheme, map the insertion and deletion algorithms of skiplists onto the new binary search tree.

The resulting tree, the “zip tree,” is closely related to a treap but using top-down rebalancing primitives rather than bottom-up rotation-based restructuring. This top-down restructuring is, I believe, equivalent to the treap’s use of insertions followed by rotations and “rotate downward” deletions, though probably slightly easier to code up. Unless I’m mistaken, the net effect is that you essentially get a treap, except that priorities are geometrically-distributed rather than uniformly-distributed and there’s a new tiebreaking rule to handle the (common) case when ties arise.

I wrote up a post on Stack Overflow explaining what the resulting zip tree looks like, as well as how to derive it. It was a fun exercise to work through, and I’m now wondering whether I can introduce this into CS166! Running this equivalence both ways – first to derive a deterministic skiplist and second to derive the zip tree – might make for a fun exploration of how ideas cross-pollinate one another.