Tideman. Tideman! (pounds desk) TIDEMAN! (Cs50x 2021 weeks 2 and 3)

If Week 1 was the learning equivalent of jumping into an ice-cold pool and trying not to drown, Weeks 2 and 3 were doing the same thing from a ground level diving board and from the high dive, respectively. Once you’re finished it’s not too bad, but the process of getting there instils a vague sense of dread followed by a terrifying ice-cold shock.

Content

Week 2 spent some time on the concept of arrays; integer arrays, string arrays, multi-dimensional arrays and what you could do with them, and assessed this through some basic cryptography. Specifically, a fun little program for scrabble scoring, followed by a couple of encryption puzzles. All this took a few hours start to finish and while the harder of the encryption exercises involved a bit of head scratching and a couple of frustrating re-writes of code, it didn’t require any particular mental gymnastics, and I was done with it by Tuesday.  

Week 3 though, oh boy. I started watching the Week 3 lecture on Wednesday fresh-faced, callow and full of enthusiasm. By the time I had finished the final exercise, called ‘Tideman’ (pronounced Teederman), it was about 2am the following Monday morning and I was haggard and hollow-eyed, like a WWI vet limping back from the Front. More on Tideman later. The main thing, though, is that week 3 was about 30 hours of work, of which the lecture and shorts made up maybe three and a bit hours, the lab and first problem set another one and a half, and the rest of it was all spent working slowly and patiently through the steps of scoring a ranked-preference election.

The topic of Week 3’s lecture was algorithms; different types of search and sort, Big O notation and recursion. For me at least, this was the first week where the challenge wasn’t merely to absorb the volume of material or peculiarities of syntax, but to understand abstract concepts.  The algorithms themselves were quite straightforward, but keeping track of the interplay of variables, arrays and recursive operations was surprisingly challenging. Which is how I ended up with the picture at the top of this post; I haven’t had to draw charts to visualise concepts on paper like that since before law school.

Which takes me to another question-to-self about how I’m approaching this. Thus far, I have been looking at each step in code design as a self-contained exercise: increment this number and perform an operation on it; set that algorithm to run through a 2D array and do something to each element. With the Tideman exercise, this was I think actively holding back my progress, because I needed to track variables through several different functions and transformations. Starting with week 4, I’m going to try diagramming out the entire process from the beginning to see if I can get better at planning around that and really understanding what I’m asking the computer to do.

Scheduling

Huge sigh of relief here! With two more weeks finished I’m back on track. If I can get through the week 4 and week 5 content by this Sunday, I’ll be well toward my goal of finishing the entire course content before the end of April. From discussions online it seems like most people found week 3 to be the biggest leap in difficulty, so I am hopeful that it will be a little easier going from here on out.

Resources

Nothing special this week outside of the course materials themselves and K&R.

Tideman

So what took all that time? Implementing the ranked pair electoral method algorithm, aka the Tideman method. The individual steps seem simple, but the complexity is I think geometric; each step adds another layer of abstraction which means that by the time you’ve traced through:

Voter A rankings [1D array]…

…cross-referenced against Voter B, C, … preferences [2D array]…

…sorted by margin of victory into pairs, each containing a winner and a loser candidate and discarding ties [2D array -> different set of data structures with two elements each]…

…then creating a completely separate 2D array to determine whether or not a given pairing results in an infinite loop of winners when taking into account all previous pairings via a recursive method [2D array + recursive voodoo]…

…then looking through all this to figure out which was the winner [actually just checking a 2D array again],

you have followed the same piece of data through six transformations plus one per recursion (that is, one per element in the array), trying to keep in mind its position relative to all the other bits of data. THAT is what made Tideman hard, and that is why I was back drawing truth tables with actual pen and paper for the first time in years.

Incidentally, recursion is a simple concept in principle but adds substantial complexity when you really trace out what’s happening to the data with every step. I had to skip ahead to week 4’s shorts to stay sane, and one of them helpfully explained what’s going on with stack memory that made it a lot easier to understand the mechanics of a recursive algorithm in a program.

Et Cetera

·         Variable names and iterations tripped me up a lot in the Tideman exercise. It’s second nature now to write nested for loops with [i][j][k] and so on, but when you’re using the exact same variable name multiple times in different functions all of which do the same iteration, it’s easy to lose track of which piece of data exactly you’re referencing. But it feels a bit silly to give them longer more descriptive names too. It made me wonder whether there’s a smarter way of managing these iterative loops (new function?)

·         One thing I forgot to do in the exam sim was to TELL the player when they pass/fail a check **and why**. This is important to me when I play games, I’ve no idea why it didn’t occur to me earlier, but I’m writing it now so I don’t forget it.