#Throwbackthursday; more shoutouts

Been looking at some of my old posts and, besides my unnecessarily chatty writing style and revealing psychological profile (hates complicated shopping lists; does not play well with others) I have come up with a few highlights to comment on.

First, and unsurprisingly, the theme of recursion. In some way or another, the whole second half of the course has involved using recursion in some way (perhaps the only exception was walking through linked lists with 'while' loops).  I did not talk about how hard Assignment 2 was for me; those wounds are still being licked.  It was Minimax hell. I wrote and rewrote that friggin' method, despite understanding perfectly what I wanted it to do, and crawled desperately to Prof Heap's office hours, where the wait time was longer than the Minor Injuries triage at Toronto General Hospital (source: broke my toe once).  But Prof Heap displayed an unrivaled kindness and patience and stayed late (very late) to assist those of us who were struggling, in part because we lacked TA assistance due to the strike.

Anyway, I never really made peace with Minimax, but I did make peace with recursion (see "my bugaboo" post for a direct comparison).  I am finding it easier to apply recursive techniques, which I think is a sentiment mirrored in several other students' SLOGs. I already wrote about Nadine, who struggled with recursion but has since come to terms with it and with Linked Lists. Gamerbornprogrammer wrote that they also struggled with Minimax, although they didn't go into detail on their issues with recursion, to me Minimax is a pretty solid litmus test of one's comfort in that area.

The only one who's been on top of it the whole time (that I came across) was Christian. He seems quite at ease with recursion, and even likes it--too bad I didn't come across his blog sooner, could have helped me out.  In fact, wafflemachine pointed me towards his blog. Wafflemachine seems to have a similar view to mine on this topic-- recursion is cool, elegant, can be a challenge to wrap your head around though.

Secondly, I'd like to address my post "Character Flaws." I have to admit that I was pretty worried about my inability to collaborate when I wrote that post.

But Assignments 2 and 3 (mostly Assignment 3) have really boosted my confidence in this regard. I took my time reading through the starter code, and since we had no alternative but to use it, I had no alternative but to understand it. I found that I actually could follow along with the style and eventually understand what the functions/methods were doing, despite not having created them myself.  I am still afraid of others' code --in particular, code that is not designed to be high-comprehension (I feel like the profs made it easy to understand).  Stuff like this freaks me out (scroll down) and this seems like a level of brevity that I will never attain. That might be because I don't understand map and lambda yet.  But the longer programs are what really scare me. How can I debug something if I barely know what it does? Makes me feel a bit foolish.  Anyway, baby steps. I do feel like the material in this course is well-structured in terms of pushing the boundaries of what we understand on multiple fronts, and helping us develop multiple programming skillsets (writing from scratch, writing from starter code, writing in general).

Really appreciating it so far.

Binary Trees; shoutouts

First of all, reading through the SLOGs (I find the punny usernames are like clickbait)...I found a fair number of people who disagreed with my view that linked lists were easy to understand. To be fair, the strike had struck (stricken?) and nobody, including myself, really had our A-game.  But Christian was on board, and even made one of those awesome ASCII-type pictorial representations (that's what they're called, right?) of a linked list that looked a lot like my train example.

But anyway, we're be on to different pastures now, and they are either greener, or not greener. (...It's a binary joke. Nevermind).  Binary trees are a type of linked data structure, but this time, a node can have a maximum of two child nodes, hence the 'binary' aspect.  An initial sticking point for me was knowing whether binary trees always had to be well-balanced by definition. After our first lecture on them, Prof Heap confirmed that they did not, and this knowledge served me well on Test 2.  (I think this point was not clarified for most people at that point). Binary trees do not, in fact, have to be well-balanced, and could in fact look like linked lists if they were poorly organized--with every node having exactly one child node (arity 1).  That would look like the conga line described by ES in their blog.

(Shoutout: I think I have found a kindred spirit in ES. Throwback photos, nerdy puns, tongue-in-cheek captions, reasonable honesty about course material...seriously, who are you and when can we hang out.)

But normally, binary trees that are well-balanced (**edit**: learned this is called complete) are a pretty efficient data structure, in particular when they are ordered for searching (binary search trees).

Shockingly well-balanced tree. courtesy reddit.com

---
Note: Nadine, whom I linked to above as an anti-linked-lister, posted that she understands Linked Lists now. (May have had more to do with recursion than linked lists--same issue as me). Right on, Nadine. You go girl.

Linked Lists

I am gratified (and a bit alarmed, in case it's a false impression) to find we are on a topic which I feel is intuitively easier to understand.  Linked lists seem bizarre when you think of them, in some ways, but pictorially they are very easy to understand.  I think the fact that there are real-world analogies that can describe this structure-- my favourite being a train with all the cars, with the caboose as the last element in the list--makes this an easier data structure to wrap your head around.  (cprogramto.com does a great job with examples)

Courtesy of shourtline.com, a 3-element linked list.  Caboose.nxt = None!

I guess it also helps that there are not too many operations you can do with a linked list, besides 'visiting' or altering nodes, walking along a list, adding/inserting nodes in various spots, or deleting nodes.  Of course the linked lists could be more complicated (I had inquired about double-linked lists in class and found out that they exist too) and could have more attributes, but there aren't too many things to remember to get started with them, which is great.

Linked lists remind me of relational databases, although that may not be a perfect comparison, but I guess some of the same principles seem to apply in terms of organizing data in separate modules and having them point/relate to each other, rather than in one giant supertable/superlist, etc.  Maybe the similarities (or differences) will become more apparent the more I learn.

Recursion, my bugaboo

I was sorely tempted to write about ADTs and compare them to people in my life (Trees: the people who go into a discussion with you armed with their version of everything you could possibly say and everything they could possibly say in response and everything you could then reply with and [...] in order to show you up; Stacks: that dude from my spin class who arrives 20min late and leaves 15min early, typifying "Last-In, First-Out" ...) but I think I owe it to myself to write about the toughest subject for me: recursion.

I have alluded jokingly to how confusing I find it, but sadly, this ain't no joke. I struggled endlessly with the MiniMax algorithm in Assignment 2, and I had no idea why I was struggling. I felt like I had the concept down, and more importantly, like I had used the type contracts of the various methods to figure out which method I needed to apply when.  (It was kind of a cool little puzzle; realizing "OK, this one yields an instance of State class, this one yields a list but needs a State as its argument... this one yields an instance of Move class...")  But somehow I was stumbling and kept getting errors, and actually struggled with the algorithm right up until it was due.  I had a hard time figuring out how to store and maximize (or minimize) the results of each recursive state without losing a reference to those results at the next iteration. My housemates must have thought I was solving P vs NP with all the scribbles and diagrams and alternate states I had drawn over our communal chalkboard in the kitchen, but sadly, the problem was incredibly elementary and my scribblings belied my actual lack of genius, rather than the presence of it.

J Musset, Droste, c. 1904. This is an early instance of recursion,

appearing in a cocoa ad in the early 1900s. The figure-of-a-figure

recursive image style is often called the Droste effect. 

As far as I can tell, the best clue to how to solve recursion problems if you are stuck is indeed to look at the type contracts.  Step away from the computer and on paper, or on a drawing surface or something, build a 'map' for yourself: what you want to use as input, what can happen to it, and then what it can spit out (in a few cases).  For example: if you know your output must be a list, or the sum (or max) element of a list, somewhere along the way you will probably be choosing between appending an element or item that you receive, and performing another recursive loop to find that element.  Sometimes it's even helpful to stop stressing about your function/method as being recursive, and just imagine you were writing the whole thing. It will immediately become obvious that you are wanting to repeat yourself and certain steps in the pseudocode. That gives a good clue as to where the recursion comes in. 

Another stumbling block lies in improper tracing of recursive function calls, which is why it is so important to practice tracing function calls, as we did for weeks leading up to the recursion exercises.  I was grateful for these exercises, because it can be daunting to try to figure out what the computer is doing 'behind the scenes,' and because I think it makes you a better programmer to have to write some things out manually and get a sense of them.  Often, when you're struggling with a recursive function/method (or really, with any function/method), it's because you don't actually understand what it is doing, and it is generally doing something that you don't expect.  A poor man's version of tracing (a.k.a my version) involved lots of breakpoints and lots of print() statements. However, prof. Heap introduced me to the world of assert: statements, which has drastically improved my debugging skills and also looks way less awkward.  (in particular, printing repr() of an object all the time is not an ideal debugging technique.)

These techniques were particularly useful for me in getting to know the starter code that was provided for us, which is great since reading other people's code (as I mentioned in a previous post) is not something I considered my strength.  Again, it was super fun, kind of like a puzzle, and very easy to follow after a certain point. I have tried to do the same with snippets on stackexchange etc., but I find them pretty tough to follow. So it was a bit of a boost to find out that I am, in fact, capable of it, I just need to practice. (It's amazing how easy it is to forget that.)