#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.)

And another thing!

Shoutout: I effin' love Big Nerd Ranch. We had this assigned reading on debugging and logs, it was so helpful and well-written.  The course notes for this class are immensely helpful and awesome. That's all.

CS counting: 1 thumb up! Binary counting: 10 thumbs, way up!

Character Flaws

I have been thinking of some of my weaknesses when it comes to this course, and I am almost afraid to mention them in case the Powers That Be (that is, that be ...able to identify me on Markus) encourage me to switch it up for the second half of the semester, which I honestly don't want to do. My biggest issue that I believe is counter to the approach of this class is that I prefer to work alone for almost everything. Labs, assignments, whatever.

I tried doing the first lab with a partner, and found it frustrating--we ran out of time, I had a very clear idea of how to accomplish the lab tasks, but it was different than my partner's, and we weren't able to communicate our ideas to each other. So we both wanted to 'compromise' and not be bossy, but we ended up with a non-functioning committee-designed, time-crunched piece of code, and where I (thought) I could see how we could fix it and make it work, we just couldn't really understand each other enough in the time constraints to make it happen.  I was also navigating, not driving, so perhaps my suggestions amounted to a lot of backseat driving. 

Anyway, I am a friendly, open-minded person, but I am sure I can be fussy and I usually want to do things my own way.  I am also marks-oriented, and probably part of this fussiness is the desire to do well on projects and make sure everything is good. I loved working on assignment 2 alone because I could get a sense of the whole picture and do exactly that.  This is a total weakness, because in the 'real world,' I know projects are done in groups and it is impossible and undesirable to accomplish everything on your own. 

This also brings me to my second weakness, which is that I'm not the best at understanding other people's code.  I document the sh*t out of my code, perhaps to an annoying extent, because when I look at other people's code, I have such a hard time seeing intuitively what it does, and it makes me impatient.  To me, these conjoined weaknesses are very negative and are things that I have to overcome if I am to progress farther in this field (which I now actually really want to do).  But I am still a stubborn-ass gal (yep, gal--further identifying myself here) and I find it hard to do in this course, especially given my work schedule, unpredictable hours, and general dislike of spending time on campus.

My solution for self-improvement is to challenge myself to read through as much code as possible of other people's (thank God Python is part of an open-source/collaborative CS spirit) and understand, modify, and play around with it until other people's work is not so foreign to me.  I don't know if I will become patient enough to do this right away within the confines of this course, but who knows. At minimum I wanted to mention that I am not going to stay all curmudgeon-y, I recognize that this is a weakness and I plan to address it.

OOP

My understanding of object-oriented programming may be limited in that I have very little basis on which to make a comparison. I have a limited understanding of relational databases from a bit of experience with ArcGIS and some faithful listening to an online SQL tutorial lecture series. But I don't have a working knowledge of any non-object-oriented programming languages, and I can't exactly conceive clearly how they would work. (I know you can use object-oriented languages in a procedural manner, but...holy geez, that still serves to confuse things).

So anyway, my understanding of OOPs is constrained by my relative lack of comparison, but so far, I am intrigued by all the different abstract data types that we are learning.  I like Trees. I don't totally understand how to navigate within them, but I like them! I have been playing around with other python modules that use trees, such as NLTK, but more on that later. I even like Stacks (although at this point my understanding of them is just 'list that has been implemented funny,' which is probably grossly inaccurate). I have made efforts to learn more about Stacks, but even the Python documentation conjures up images of somewhat Sphynxlike lists that will only give you a little bit of information at a time.

Ask for more than LIFO and I will bite your bloody head off.

So yeah, Trees. I feel like the concept of recursion has clarified a bit for me, although boy did I struggle in the last tutorial.  Was slammed with work that week, didn't do more than read over the tutorial handout ahead of time, arrived and struggled with the first question for almost the whole time. It was brutal. I understood what to do, but couldn't make my code pass all the tests.  Spent the whole entire class struggling with it. Poor Rajeet tried his best to help me, but he may need some ice for that bruise after spending so much time banging his head against a wall. (Note: There was no actual violence or self-injury. This is humour. Nobody was physically harmed in tutorial, although it may have been touch-and-go at times cause I can be pretty dense.) Thanks also to mystery female classmate (don't know her name) who was kind enough to look at my code and ultimately point me in the right direction.
  
Anyway, take-home point is that it is a terrible idea to go to tutorial without having at least a bit of the handout worked through. Such a mistake. Don't do it. Hopefully next (next) week will be better, although I have been crazy busy and only get home at 8:30pm Tues and Thurs, (and the odd time, I have work Friday mornings before tutorial!) so my preparation is not always adequate.  At least I have reading week to do more on the labs and on Assignment 2, which I can already see will require a bit of brain-stretching to understand.