The Algorithm Machine

I've been teaching computer science at the college level for 15 years, and although my expertise is more on the programming side, I still spend quite a lot of time covering standard algorithms for searching and sorting. From a teaching standpoint the central issue is computational complexity: how much time does each algorithm require, given input of a particular size? But there are numerous nuances. For example, do the algorithms have different runtimes depending on the specific input values (as opposed to the size)? In which cases would you choose one sorting algorithm over another? Although we discuss these issues in the abstract, it always bugged me that there was no easy way to see how different algorithms work under various conditions.

Goals

My overarching goal for this project was to create a interactive display for students to visualize and explore algorithms. I limited myself to algorithms that work on arrays of values (integers), so I can use an addressable RGB LED strip to visualize the array contents. The array has 100 elements, and each integer is mapped to a color in rainbow order, so that it is immediately obvious when the array is sorted, partially sorted, or randomized. In addition to the values, however, I wanted a way to visualize control aspects of the algorithm -- for example, which elements of the array are currently being compared or swapped.

The specific goals are:

- Provide a variety of searching and sorting algorithms

- Visualize the values in the array in a way that highlights algorithm progress

- Visualize algorithm control; in particular, the elements being considered.

- Allow users to choose the input data patterns rather than always generating random values

- Allow users to control the speed and pause the algorithm

- Allow users to force best-case, worst-case, average-case behavior (algorithm-specific)

- Show the number of steps as the algorithm proceeds

Visualization

From a physical design standpoint the most interesting part of this project is the visualization of the array. I struggled with how to show the data and control, and how to build the display device itself. My goal was to show the data values as colored circles and the control points as colored arrows that point at the data values. After some experimentation I settled on a design with two parallel strips of 100 RGB LEDs (WS2812) with a circular mask over each data LED and a triangular mask over each control LED. I made a 3D model of the mask with 10 pairs of circles and triangles, and then 3D printed 10 of these modules for a total of 100 circles and 100 triangles. The size and spacing of my mask is designed for strips with 100 LEDs per meter. The 3D model files are provided later in this description.

Electronics and enclosure

The rest of the device is straightforward, from an electronics standpoint. In addition to the two LED strips, there are a bunch of momentary buttons, a rotary encoder (for the speed control), and a 7-segment display (to show steps). With so many buttons and controls I opted to use an ESP32 microcontroller because it exposes a lot of pins and because it is fairly powerful. I'll go over the wiring strategy, but it is pretty basic. You could probably do something smart with shift registers if you want to use fewer pins.

You can build the enclosure for this device in many different forms. I initially imagined it as a large rectangular board with the LED strip across the top, and a grid of buttons in the middle. The form I ended up with is inspired by a kind of 1960's view of space-age technology. You could also build it with the LED strips in a vertical orientation. Or make the LED part much bigger -- fill a whole wall -- with a separate control panel.

Software

The code for this device is freely available on GitHub, and I have done my best to document how it works and how to configure it. The only external library you need is FastLED to drive the WS2812 strips.

Electronics

1 ESP32 development board (e.g., https://a.aliexpress.com/_ssDfh3)

2 WS2812 or similar LED strips, density 100 LEDs per meter (e.g., https://amzn.com/B07BTTY4FL )

1 Triangle "start" button (e.g., https://amzn.com/B07R565HM6)

12 Momentary buttons (e.g., https://amzn.com/B01N4D4750) -- different shapes if you want

1 Pack (20) prewired button connectors (e.g., https://amzn.com/B07RRSG321)

1 Pack JST connectors (e.g., https://amzn.com/B0731NHS9R)

1 Rotary encoder (e.g., https://amzn.com/B07BN3DGBS)

1 Knob for rotary encoder (e.g., https://amzn.com/B07TSR4XM3)

1 Pack Dupont connectors (e.g., https://amzn.com/B014YTPFT8) -- it's worth getting the crimping tool as well.

1 Barrel jack (for power) (e.g., https://amzn.com/B074LK7G86)

1 TM1637 7-segment numeric display (e.g., https://amzn.com/B07MCGDST2)

Soldering and wiring gear

3D model files

You can find the 3D model for a pair of 10-light modules on Thingiverse:

https://www.thingiverse.com/thing:4178181

You will need to print this model five times for a total of 10 modules.

Software

https://github.com/samguyer/AlgorithmMachine

Enclosure

Wood, plexiglass, stainless steel bolts and screws

Diffusion material. My favorite is Lee Filters #216 full white diffusion, but there are other options. Even plain white paper does a good job.

A lot of people think that computer science is essentially the study of programming. But the real heart and soul of this field is algorithms: the study of systematic procedures for solving problems and their cost (typically, how long they take). Seminal figures in the field, like Alan Turing, Alonzo Church, and Edsger Dijkstra, were thinking about these ideas before computers as we know them even existed.

The key feature of an algorithm to solve a particular problem is that it is detailed and precise, so that someone could use it to get a solution without understanding how it works at all; just follow the steps in a mechanical fashion and you'll get the right answer. You can see how this helps with programming computers, since they need this level of detail. A computer cannot fill in missing details or make judgements, the way a person can.

How long will it take?

Once we have a detailed procedure a natural question is how long will it take to get the answer? We can't use ordinary units of time, since it depends on who is doing the work (compare how fast a person could compute something versus a supercomputer). In addition, it depends on how much data we have. Clearly, it takes longer to search a list of a million phone numbers than a list of a hundred.

To describe the cost of an algorithm we first pick some operation in the procedure that represents one "step" -- usually something simple, like comparing or adding two numbers, that takes a fixed amount of time to do. Then we come up with a formula that describes how many steps the algorithm will take given some number of data items. For historical reasons, we almost always denote the number of data items with a capital N.

For example, looking through a list of N phone numbers takes N steps. Looking through the list twice takes 2N steps. Both of these are called linear time algorithms -- the total number of steps is some multiple of the input size. Other algorithms are quadratic (N squared time) or cubic (N cubed) or logarithmic (log N) or some combination of these. Some of the most difficult computational problems require exponential time algorithms (2^N).

OK, so what?

When the number of data items N is small it doesn't matter much. For example, for N=10, 10N is that name as N squared. But what about N=1000? or N=1000000? A million squared is a pretty big number. Even on a very fast computer, a quadratic algorithm can take a long time if the input is big enough. Exponential algorithms are much more troublesome: for N=50 an exponential algorithm would take two weeks to finish even on a computer where each step is just one nanosecond (1 billionth of a second). Ouch!

At the other end of the scale we have logarithmic time algorithms, which are very fast. Log time is the opposite of exponential time: given input size N, the number of steps is the exponent T in the formula 2^T = N. For example, if our input size is one billion, then a log time algorithm only requires 30 steps, since 2^30 = 1,000,000,000. How sweet is that?!??!

You might be wondering, who cares about input sizes of millions or billions? Think about it: how many users are there on Facebook? How many web pages are indexed by Google? How many base pairs are there in the human genome? How many measurements go into a weather simulation?

The Algorithm Machine currently implements the following algorithms. Two of them are search algorithms (find a particular value in the list), the rest are sorting algorithms (put the values in order).

Linear search

Search through the list of values one by one starting from the beginning. Requires linear time.

Binary search

Search a list by repeatedly dividing it in half. Requires log time, but the list must be sorted for it to work.

Bubble sort

Sort a list a repeatedly exchanging neighboring elements that are not in order. Requires quadratic time.

Insertion sort

Sort a list by placing each element in its proper place in the list of already sorted values. Requires quadratic time.

Quicksort

Sort a list by repeatedly dividing the list in half and moving all the values less than the median to the first half, and all the values greater than the median to the second half. In practice, we cannot efficiently find the median, so we pick a value at random. As a result this algorithm can be quadratic in the worst case, but typically requires N * logN time.

Merge sort

Sort a list by dividing it in half, sorting the two halves separately (using merge sort), and then merging them together by interleaving the values. Always requires N * logN time.

Heap sort

Sort a list by building a data structure called a heap, which allows you to find the smallest value in log time. Always requires N * logN time.

Bitonic sort

Similar to merge sort and quicksort, divide a list in half, sort the halves, and recombine them. This algorithm requires N * logN * logN time, but has the advantage that it is easy to parallelize.

The first step in building the LED bar is to 3D print the mask that gives the lights their shape. Each module covers ten elements of the array, 10 values (circles) and 10 indicators (triangles), so you'll need 10 modules altogether. The STL file I am providing here contains two instances of the module, so you'll need to do five print cycles. I don't have the best 3D printer, so I had to do some manual cleanup on them using a file and sandpaper. The most important thing is that the circular and triangular holes are clean.

In the photos you'll see my test setup: I taped the two LED strips down and hooked them up to a breadboard with a microcontroller. This step isn't necessary, but I wanted to see how it would look before I started assembling the enclosure. I lined up the mask modules on the two LED strips and ran a simple sketch with random colors. With a strip of the diffusion material the shapes and colors really pop.

When I first started this project I experimented with other ways of making the LED mask. If you don't have a 3D printer you might consider one of these options. I'll be honest: it's a huge pain to make these parts.

For the circles, I bought a 13/32 brass tube, which is almost exactly 1cm in diameter. I cut it into one hundred 1cm segments and then spray painted them white.

For the triangles, I used heavy-weight aluminum foil cut from a disposable baking pan. I made a triangular form out of wood, then wrapped short strips of foil around the form and taped them. Again, you'll need a hundred of these things, so it take some time and patience.

My enclosure is fairly simple: two strips of wood for the sides and two strips of plexiglass for the top and bottom. All the parts are about 102cm long (1 meter for the LEDs, plus a little extra to accommodate the wiring). The sides should be a little taller than 1cm to make room for the LED strips. After cutting the strips I sandwiched the 3D printed mask pieces between them to measure the width for the plexiglass. Cut two pieces of plexiglass the width and length of the bar. Finally, cut a strip of the diffusion material to fit over the mask.

For diffusion I really like Lee Filters #216 (full white diffusion). It is a thin plastic sheet that gives even diffusion without losing a lot of light. But it is expensive stuff. Sometimes you can find smaller sheets for sale online, but a whole roll will set you back about $125. Some other options are white paper or any other kind of satin or frosted plastic. A popular choice is thin plastic cutting mats.

Before you assemble the LED bar make sure you have the appropriate connectors soldered to the LED strips. A lot of strips come with leads pre-soldered, so you can just use those.

I started the assembly by screwing the top piece of plexiglass onto the wooden sides (see photo). Then I flipped it over and placed the diffusion strip in, followed by the 10 mask pieces. Once I was happy with the spacing I pinned them in place with a few dots of hot glue.

Next, lay the two LED strips side by side on top of the masks. Make sure the LEDs face down and make sure each LED lines up with the corresponding hole in the mask. Add some hot glue or tape to hold the LED strips in place. Finally, screw on the back piece of plexiglass.

Run a test pattern. Nice job! You've done the hardest part!

The control panel is the part that affords the most creative freedom. It just needs to hold all of the controls and electronics, along with the LED bar. The simplest design is a rectangular boards: drill holes for the buttons and controls, and attach the LED bar. I like to combine wood, plexiglass, and other materials to give a kind of steampunk / retro-modern look. In this case, I cut a piece of heavy-duty plexiglass to hold the main algorithm choice buttons, and a wooden bar to hold the rest of the electronics. I drilled holes to match the size of the arcade buttons. The wiring shows on the back, but I like it!

I also drilled out space for the 7-segment display, the rotary encoder, and some of the wiring on the back. I cut a dado in the top to hold the LED bar.

Wiring a lot of buttons can be a real pain. Luckily, the people who make arcade machines have come up with some standard connectors that you can use. Each button connector cable has two wires, one for VCC and one for ground. One end has spade connectors that fit the leads on the back of the button -- attach the ground to the "normally open" lead, and VCC to the "common" lead. In this configuration, when the user pushes the button, the circuit is completed and the microcontroller will read HIGH on the corresponding input pin.

The other end of the cable has a JST connector (the little white thing). What's nice about these connectors is that they only go into the receptacle in one way, so there is no way to accidentally reverse VCC and ground.

What I did is build a little harness for these connectors. I solder a series of JST receptacles onto a piece of protoboard and then run wires back to Dupont connectors that I'll plug into the microcontroller. The red wire is the VCC line, and it connects to all of the JST receptacles. The blue wires are the ones that are separate for each button.

The rotary encoder lets the user control the speed of the algorithm. I use a module that comes as a breakout board that includes pull-up resistors for the two data lines (yellow wires). This one also happens to be a button, but I'm not using that feature. The other two wires are VCC and ground. I also got a nice fat knob.

What I like about a rotary encoder, as opposed to a potentiometer, is that it just signals rotation (clockwise vs counter-clockwise) to the microcontroller, so it's easy to change how the value is interpreted. For example, you can give it a sense of acceleration (like a mouse) when the user is spinning it fast.

Not a lot to say here. These things are everywhere. The LEDs are controlled by a chip called TM1637, which communicates with the microcontroller through a simple serial protocol. I use an existing library that lets me tell it what number I want to show, and it does the rest.

The back has four pins: VCC, ground, and two wires for the serial protocol. I soldered a 4-pin piece of header, which connects to a corresponding Dupont connector wired to the microcontroller.

The main controller board houses the microcontroller itself and all of the connectors to the controls (buttons, display, LEDs). The microcontroller is an ESP32, which provides a lot of computing power and memory, and exposes plenty of pins. The wiring is pretty standard, but I'll point out a few interesting bits.

NOTE: You might want to look at the code (https://github.com/samguyer/AlgorithmMachine) before you start wiring the main board, so that your pin configuration matches mine.

I soldered a barrel jack onto the board for power, and connected two beefy copper wires to the power and ground rails of the board. The reason is that the LED bar can draw a lot of power if the brightness is set high, and I don't want to pull all of that power through the USB connector on the microcontroller.

To simplify the button wiring I soldered a strip of male-to-female right angle header down the entire side of the microcontroller (upper side of the board as shown). The Dupont connectors from the button harness plug directly into this header.

IMPORTANT: the power for the buttons (the red wire) must be connected to the 3.3V power line on the microcontroller. The ESP32 is a 3.3V chip, so only 3.3V sources should ever be attached to the data pins.

The microcontroller draws power (or pushes power) to the rails (lower side of the board as shown) through the 5V USB pin and ground. All of the other red/black wires are VCC and ground.

The two blue wires are the data lines for the LED strips (the WS2812s). The yellow/green pair are the data lines for the rotary encoder, and the yellow pair are the serial connection to the 7-segment display.

This series of photographs shows the final assembly and wiring. I also attached the main controller board to the back at the top.

Before powering it up I did a few checks to avoid any nasty surprises. In particular, to make sure I didn't have any power/ground connectors backwards, and no short circuits. Set your multimeter to test for continuity -- it will beep when there is an electrical path between the two leads. Attach one lead to the common VCC line to the buttons. Then attach the other lead to each pin of the harness one by one. The multimeter should only beep when you press the button. If you get any other beeps it means you have a reversal or a short. Track it down and fix it before you turn on the power!

First, open up your Arduino IDE and make sure you have the FastLED library installed.

Download the Algorithm Machine code from GitHub:

https://github.com/samguyer/AlgorithmMachine.git

You can either clone it directly into your Arduino folder, or copy it in by hand.

Before uploading it, make sure the pin settings match your hardware configuration. I have placed all of the pin settings at the top of the file.

Upload and enjoy!

The Algorithm Machine is simple to use and almost any combination of buttons is ok!

First, use the data buttons to initialize the values in the array. There are three choices: (1) randomize, (2) add one random value, and (3) reverse the array. Note that the values are persistent, so you can do things like sort them first, then add some noise, then run a different sorting or searching algorithm.

Choose a searching or sorting algorithm from the other button choices. Currently, there is no feedback when you make this choice (something for future work). Then hit the "play" button.

The knob controls the speed. You can also hit "play" to pause and unpause the algorithm.

It will stop automatically when it's done. You can also hit another algorithm button at any time. The machine will stop the current algorithm and initialize the new one, but keep the data exactly as the previous algorithm left it.