Super Mario 64 and Binary Decision Diagrams
Another Sunday means it's time for me to sit down and talk about what happened between the last newsletter and now. I have to say: not much has happened.
The smoke that blanketed most of Vancouver for the past week-or-so has finally lifted as of yesterday. I'm honestly amazed at how much of a difference that made. I can see the North Shore mountains from my window in Ponderosa, and I can go outside for more than a few minutes at a time without having a chalky feeling in my mouth. It feels good to get some reprieve from the smoke, but I can't help but wonder if we're in for another bout next summer, or even sooner.
Last Tuesday, I gave my first lecture as a graduate student for CPSC 310 (Intro. Software Engineering). It was definitely an experience that made me nervous; I almost feel like giving the lecture remotely makes my anxiety worse. I've given presentations in person and for those, I could at least tell from the faces of the attendees whether I was making sense (not super likely), or if I was just making a fool of myself (more likely). For online learning, I was more or less speaking to my slides, since Zoom shows 5 participants at a time when you're presenting, and those 5 participants usually have their cameras off. Nonetheless, I felt like I gave a half-decent lecture of the dangers of JavaScript and the merits of TypeScript (with some of the merits of type-driven development sprinkled in).
I think I want to continue what I did in last week's newsletter and describe at least one thing that I learned the past week. Hopefully this is going to prove to me that I'm actually learning something in grad school. This week's concept is the Binary Decision Diagram (BDD) from CPSC 513: Introduction to Formal Verification. I thought that this was an incredibly friendly visualization of boolean expressions, such as a && b && c, where a, b, and c are some boolean terms. The BDD for that expression is shown below:
It's pretty cool how taking a path down the tree for a true (1) or false (0) value of a boolean term will eventually lead to the value of the entire expression once you arrive at a leaf node. But this is pretty wasteful, since we know that for the expression a && b && c, having even a single false value will lead to the entire expression being false. It turns out we can take advantage of this and reduce the tree above to a canonical form:
Extending this reduction for more complicated boolean expressions, we not only save memory, but also time, as we no longer need to traverse a deep tree.
I also made the decision a few weeks ago to pre-order a copy of Super Mario 3D All-Stars. Whether that was a wise decision remains to be discovered but I received my copy on release day (Friday). The game includes the following:
* Super Mario 64 * Super Mario Sunshine * Super Mario Galaxy
I'm embarrassed to admit that I bought the game mainly for Super Mario 64 (I actually haven't played Sunshine or Galaxy), but it seems like the other two are beloved classics as well. Booting up Mario 64 brought back some sepia-toned memories of my early childhood. I would remember going on road-trips with my family where there would be nothing to do but read, sleep, look out the window, or fight my brother for a turn at playing Mario 64 on a DS. After a couple hours, I can say that the controls are as infuriating as ever, the graphics clearly need some work, and opening the right sequence of treasure chests underwater is almost impossible. I love it.
It looks like rain is in the forecast for the week coming up. Hopefully I'll get a chance to go cycling a bit more now that the smoke is gone. I'm still (for the most part) keeping my head above water.