Graph Theory and other math topics in Intro to CS

If there’s one thing that Intro to CS is teaching me this year, it’s that there is so much more math in programming and computers than I even notice.

I’ve never taught a full-semester CS course before, and i’m taking it slow and easy. We have definitely not done as much as I could be doing, but it’s an elective, I want them to have fun and feel limited pressure and really dive into ideas at depth. It’s an elective, I can do that.

Here are some things we’ve done this year so far, and the math content that came (accidentally, usually) with the territory.

  1. We used Snap! (a rewrite of Scratch with more powerful features though also, sadly, some definite occasional bugs) to do some turtle art. Specifically, we made stars.
    • Math topics used exterior (turning) angles, modular arithmetic patterns, circumferences of circles, angles inside of regular polygons, formula-writing
  2. We made bugs dance, also in Snap. Simple animation tools used and explored to make a music video.
    • Math topics: calculating wait times between animation steps to match music, angles of turn for spinning steps
  3. We made our own versions of Pong, in Snap.
    • Math topics: in addition to timing and score keeping – simple things, really – the biggest math difficulty here was abstracting the idea of “bouncing off of something” in terms of angle directions. Basically, reflections in the horizontal and the vertical.
  4. We followed the Berkely Snap! curriculum to write a program that generates a “game board” – basically a grid of arbitrary size, using turtle graphics.
    • This used an AMAZING amount of analytical geometric reasoning. Figuring out how wide to make each square, how to move from one square to the next, when to go to the next row of the grid, how to get there without getting turned around, all in terms of an arbitrary variable on an x-y coordinate plane, required simply loads of serious mathematical thinking. I taught many of these girls geometry last year, and they learned more analytic geometry in the three days we worked on this project than they did in my class, for sure.
  5. We programmed our TI-84 calculators in TI Basic. I had mixed feelings about this task, but it was requested. So we wrote programs to simplify radicals, find missing sides in the Pythagorean theorem in simplest radical form, use the arithmetic and geometric sequence formulas to find terms (pretty pointless, it turns out, since these features are actually built in), factor quadratics, etc.
    • Math topics: obvious, yeah? Lots of good algorithmic thinking that goes beyond applying these skill in a non-computer environment though. It was interesting to think about some of these tasks in a way that is NOT instinctive, especially something like “find some numbers that add to one thing but multiply to another” for factoring.
  6.  We learned about binary numbers and hexadecimal (base 16) and how you can encode all kinds of information using strings of zeroes and ones.
    • base notation, powers of two, powers of 10, factors. The quick conversion between binary and base 16, relative to converting to base 10, was an interesting discussion. We also discussed base-12 and how it connects to the 60s in time, angles, etc.
  7. We used a Logic Gate Simulator to explore how very simple circuits can be combined to do more complicated math. We worked our way up to building logic gates that could add 4-bit numbers in binary using cascading addition (essentially, carrying!), as well as simple multipliers that could multiply 2-bit numbers (to create up to 4-bit numbers).
    • Obviously, formal logic comes into this a bit – Or, Not, And gates simulate those logical operations. But the biggest mathematical value here was really diving into the “standard” algorithms for addition and multiplication and thinking through how to adapt those to binary, then thinking how to adapt THAT to on/off values in gates.
  8. We created our own encoding scheme, in binary, to play a simplified game of battle ship with multiple people at once. This was part of’s AP Computer Science Principles curriculum, about how the internet works.
    • efficient packing of information, sufficient-and-necessary information
  9. We learned about the Minimum Spanning Tree and Shortest Path Problems in graph theory, discovering our own algorithms for MST and learning about Dijkstra’s algorithm for the SSP problem. This idea also came from
    • Graph theory is just straight up math, you guys. Also, modeling: we are solving SPP as part of our conversation about how the internet works, in that routers need to know the fastest path to the major internet hubs.
  10. And now, we are using p5.js (a version of the visual programming Processing written in Javascript) to implement Dijkstra’s algorithm on top of a program I built for representing graphs. You can play with that program below, if you’d like – I learned a lot about Javascript myself while writing it, a good excuse to finally learn about the language.
    • Despite the fact that this is technically all about implementing a full-fledged mathematical algorithm, the actual work we’re doing here is not particularly mathy. It’s very programmy – lots of iterating over arrays and checking for things – but there is less “math content” used that some of the earlier projects. Still, thinking about algorithms is mathy all itself.

Want to play with some graphs? Here you go. If you click the button, it will show you the shortest path for each node (though not in a very readable format as yet).

Leave a Reply