The Algorithm Machine

18,914

92

19

Introduction: 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.

    Supplies:

    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

    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.

    Teacher Notes

    Teachers! Did you use this instructable in your classroom?
    Add a Teacher Note to share how you incorporated it into your lesson.

    Step 1: Algorithms 101

    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?

    Step 2: The Algorithms

    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.

    Step 3: LED Bar: 3D Print the Mask

    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.

    Step 4: LED Bar Alternatives

    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.

    Step 5: LED Bar Enclosure

    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!

    Step 6: Control Panel

    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.

    Step 7: Button Harness

    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.

    Step 8: Rotary Encoder

    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.

    Step 9: 7-segment Display

    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.

    Step 10: Main Controller Board

    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.

    Step 11: Assembly

    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!

    Step 12: Code

    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!

    Step 13: How to Use

    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.

    STEM Contest

    Grand Prize in the
    STEM Contest

    Be the First to Share

      Recommendations

      • Raspberry Pi Contest 2020

        Raspberry Pi Contest 2020
      • Wearables Contest

        Wearables Contest
      • Fix It Contest

        Fix It Contest

      19 Discussions

      0
      atulyarchi20
      atulyarchi20

      2 days ago

      I did it ..........

      0
      thatguyer
      thatguyer

      Reply 1 day ago

      Great! Tell me more about it -- did you build the whole thing? You should be able to set NUM_LEDS to however many you actually have. The sketch will adapt as necessary.

      0
      atulyarchi20
      atulyarchi20

      Reply 1 day ago

      I built the whole thing within 3 days. I will be sharing it once I am done with my exams . Thanks a lot .

      0
      thatguyer
      thatguyer

      Reply 8 hours ago

      Nice job. It took me a lot longer than that! I'm still making improvements to the software, so keep an eye on the GitHub repo.

      0
      atulyarchi20
      atulyarchi20

      Question 5 days ago on Step 1

      Hello Sir, I'm not getting Start button here , Can I use simple push button as an alternative ?
      Can you guide me about the power supply ,please ?

      1
      thatguyer
      thatguyer

      Answer 4 days ago

      Hi! All of the buttons are just simple momentary pushbuttons. I used a big button for start/stop, but there is nothing else special about it. Just make sure all of the buttons have pull-down resistors from the input pin to ground.

      This device uses very little power, especially since most of the indicator LEDs are off at any given time. I just use a 2A or 3A 5V DC adapter (the kind of thing you would use to charge a phone or tablet).

      0
      atulyarchi20
      atulyarchi20

      Reply 4 days ago

      I got WS2812 , not WS2812b you mentioned as a product link and I don't have the program to check that. I got 60 led in 1m . what to do ?

      0
      Ruud48
      Ruud48

      15 days ago

      Great project, very informative and well done! Did you ever think about showing this on a computer by creating a Windows program? Then one does not have to build the hardware and every school can use it.

      1
      thatguyer
      thatguyer

      Reply 14 days ago

      That's a great idea. I should put together a web app. In some ways it can do a lot more than a physical device (like change the number of elements in the array)

      0
      Mattpenner
      Mattpenner

      15 days ago

      This is great! I had my original algorithm classes 20 years ago and there was not much of a visual component other than your typical static images with tables, blocks and arrows. For those in the class that didn't understand the algorithm or the code it wasn't much help. I'd say this hurdle caused a large delay while the teacher and students were attempting to help others understand what was happening.

      This really would have helped. A great visual way to understand how the various routines work. Nice job!

      0
      thatguyer
      thatguyer

      Reply 14 days ago

      Thanks! I felt the same way. Even when I did finally really understand it, I still couldn't picture exactly what was going on!

      0
      xiandavis
      xiandavis

      15 days ago

      Thank you for sharing this. I’ve coded before but haven’t been comfortable with sort algorithms. Your creation appeals to my visual learning style, and it is a beautiful piece of work!

      0
      thatguyer
      thatguyer

      Reply 14 days ago

      Thank you!

      0
      dresch
      dresch

      15 days ago

      Brilliant and beautiful. Thank you sir. That is a really gorgeous representation.

      Now I am going to do the old guy thing: when I was in undergrad when dinosaurs ruled the earth (along with PDP-8s) we had a sorting contest (8 bit integers) in my first algorithm class. One individual had a sort time orders of magnitude less than everyone else and I will never forget the way he did it. He created an array of 256 words. He then took the data set and counted thru it once adding one to whatever array bin the data value equaled. So if the data value was 125 he added one to bin 125: mycount[125]++. Then he simply wrote out the number of non-zero bin values the number of times that bin address held. Instant sorting by counting. If bin 7 (mycount[7]) had was equal to 3 he wrote to the sorted array: 7, 7, 7. Then if the next non-zero bin was 11 and it contained 5, the list became: 7,7,7,11,11,11,11,11... and so on.
      I must say I have used this a number of times in my computing life... if your data falls within certain well defined limits, it is a fantastic algorithm.

      0
      thatguyer
      thatguyer

      Reply 15 days ago

      Thank you! Some of my first programming experiences were on a VAX 11/780, so I'm familiar.

      What you're describing is a variant of radix sort (https://en.wikipedia.org/wiki/Radix_sort). In the form you are describing it is asymptotically faster than any other sorting algorithm ( order N versus order N*logN), but it comes at the cost of space (memory use): the size of the counting array is exponential in the number of bits in the values you're sorting. So, sorting 8 bit values requires 256 counters, sorting 16 bit values requires 65536 counter, and sorting 32 bit values requires around 4 billion counters. Forget about 64 bit values!

      One strategy to make it feasible is break each value into groups of bits and perform radix sort at each level. You could think of it like sorting numbers by placing them into bins according to each digit, starting with the highest place value. For example, to sort values in the range 0-999, you start by putting each value into one of ten bins according to the digit in the 100s place. Then consider each of those bins, and further divide them into ten bins for each digit in the 10s place. Then continue down to the 1s place. At any given time you only need some multiple of 100 bins (much much less than the exponential-sized algorithm).

      In this form, radix sort runs in time N * d, where d is the number of digits in the largest number. Since d is always some log factor of the size of the values, however, it ends up being N * logN in practice.

      0
      JeremySCook
      JeremySCook

      Question 20 days ago

      I don't suppose you have any video of this in action?

      1
      thatguyer
      thatguyer

      Answer 19 days ago

      Just added a video showing bubble sort, insertion sort, quicksort, and merge sort.

      0
      JeremySCook
      JeremySCook

      Reply 19 days ago

      Awesome, thanks!

      1
      thatguyer
      thatguyer

      Answer 20 days ago

      Yes! I am making a bunch of videos today, so I'll post them as soon as I'm done. I was racing to get it done yesterday, so I didn't have time.