# 3

TL;DR: A Whiteboard Program Trace is where you write down a data structure on a whiteboard and step-by-step walk through how an algorithm A would manipulate this data, i.e. you execute A for one specific input in a visual way. Usually, I do this before I have understood all the details of A, in order to figure them out.

Imagine you are debugging some program and you step through every line of code and have a display of what are all the local and global variables in the given context.

What if instead of first writing the program and then debugging it, you start by debugging the program that you would like to have? All you need is a very high-level understanding of your program.

To do this write down on a whiteboard, write down some data structure, and then walk through, step by step, what modifications the algorithm performs on the data structure.

I do something like this in this video:

1. I write down the data structure and describe what properties the graph has.
2. I write down the result of an algorithm that embeds a graph into 2D Euclidean space (each vertex gets assigned a coordinate).
3. I describe the general problem of creating a plan from a to b where a and b are nodes. Then I create a specific instance of this problem by marking one node as the start node and one node as the target node in the graph.
4. I am running BFS on the graph. Note that I draw the squiggly edges in the order that BFS would unroll them.
5. I describe a procedure for calculating a displacement vector.
6. I describe how the displacement vector represents all possible plans.

I made this video to make sure that I understand the Vector planning algorithm, before writing the Vector Planning in a Lattice Graph post.

Note that I am somewhat confused at step 6. I go on and on about how this represents all possible paths, which I did not think about before recording the video. And I don't give an exact algorithm for unrolling the vector into the plan, in the video.

Mentioned in
New Comment