As(sorted) Thoughts

Over the last few weeks of this course, we have been reviewing searching and sorting algorithms and comparing their runtime complexities in a number of different situations. I had learned about some of these algorithms in CSC108, so I came into this section with the following knowledge:

-Linear search is mostly bad
-Binary search is mostly good
-Insertion sort and selection sort are equally bad in the worst case scenario but one (I couldn't remember which) was better in the best case scenario
-Bubble sort is almost never the answer-- and there was a video with Obama attesting to that on a talk show somewhere

In 108, however, we focused mostly on the algorithms themselves--HOW, but not necessarily HOW FAST they processed code. Most of the problems we worked on revolved around determining which type of sorting algorithm had already been applied to a (short) list.

In 148, we've been working with the algorithms in a more practical way--applying them to very large data sets and comparing their efficiency on the scale on which they'll be used "in the real world", so to speak.

In order to compare their efficiencies, we've been using "big-Oh" notation, which relates the amount of work an algorithm must do to the size of the list it's being applied on, where the "amount of work" generally represents a number of calculations or comparisons the algorithm must execute in order to properly place an item in a sorted list. The the most common "big-Oh" relationships that we've worked with are:

O(1)--constant runtime, where the number of calculations does not vary with the size of the list
O(logn)--logarithmic runtime, where the number of calculations increases with the base-2 log of the
               list length
O(n)--linear runtime, where the number of calculations increases linearly with the list length
O(n^(2,3,4 etc))-- exponential runtime, for example, n^2 will quadruple the number of calculations if the list length is doubled
O(nlogn)--the number of calculations increases with the list length multiplied by its base-2 log

These relationships exist in an efficiency hierarchy that roughly runs from the top of the list above to the bottom--but it's not quite that simple. Depending on the state or length of the list, sometimes a simple algorithm will finish faster than a more complex one--one example of this is linear search (O(n)) outperforming binary search on a list where the item sought is the first item in the list. Consquently, it's important to consider the ASYMPTOTIC runtime complexity of a function--different algorithms may dominate above or below a certain threshold list length. (This tricked me on term test two--it's not necessarily ABSOLUTE order of magnitude that determines the best performance of an algorithm.

We've also learned about a new (and awful) sorting algorithm, merge sort, which performs at (nlogn) complexity, compared to the n2 complexity of insertion and selection sort. Along with the other algorithms, we assessed merge sort's performance in lab 10, both by graphing the runtime and using Cprofile to assess the number of function calls made. Cprofile is a useful tool for adapting code because you can see which step of your algorithm is taking up the most time--and hopefully find a way to reduce the number of calls on your problem function.

However, the most efficient way to sort a list remains Python's built-in search function, based on Timsort. It breaks a list down into much smaller pieces and uses the most efficient sorting algorithm for each piece--so, some combination of insertion, selection, bubble, and merge sort--before putting the pieces back together. It has an additional advantage in that it is coded in C, and thus can be applied by the machine more quickly, rather than having to convert from Python before being applied.

I found the ease and practicality of this section to be a HUGE relief after the exercise in frustration that was my experience with linked lists, and it was an INCREDIBLY satisfying feeling to walk out of a lab having completed the exercise. The thing I struggled with most in this section was remembering that log here applies to log base 2-- and not log base 10, as my math-brain repeatedly insisted--a trivial problem compared to the sense of despair that set in when I was confronted with recursive linked list/tree combination questions in my previous labs.

Can't see the forest for the (binary) trees

Over the course of the last two weeks, my experiences in CSC 148 have been completely dominated by trees -- binary trees, regex trees (some of which are unary trees), binary search trees, trees with linked lists-- and for much of that time, I felt at least a little like I was lost in the woods.

When we first saw trees in Week 6, the concept seemed fairly simple. Understanding the structure and terminology of trees-- roots, nodes, children, leaves, height, etc-- was easy with a picture of a tree in front of me. Things got a little harder when I had to applying the same concepts to TreeLists--which visually seemed much more complex than the trees they represented. Traversing trees by hand was almost fun (shout-out to whoever posted that traversal video featuring Paul Gries, who I singlehandedly credit with making me interested enough in computer science to be taking this course, which is currently kicking my ass)--and I was SO READY for a midterm question that asked me to reconstruct a tree given two traversals.

That question never did show up on the midterm--but lo and behold, there it was as part of e3. Figuring out the code to produce the tree was a little more complex, but still a fun logic problem. The strategy of working things out by hand and then asking, 'how did I know that?" really helped--for example, knowing that an inorder traversal traces left-root-right allows you to split the tree into left and right subtrees (with the root isolated by virtue of its place in the PREorder list)--and then realizing that if I'm applying the same process to each subtree, it must be a good time to apply RECURSION.

(About recursion: even if I'm still not a pro at knowing HOW to use it, I think I'm much better now at knowing WHEN to use it--baby steps, right?)

Having knocked e3a off my checklist in short order, I internalized the (very wrong) idea that e3b would have the same level of difficulty--initially challenging, but then I would just GET it. (I worked on that function for several hours. I never 'got it'.) I knew enough to use the 'height' function we had seen in class to get the depth of the tree, but I never did figure out a way to identify the individual elements in the longest path. Neither did any of the 5 other people I converse with in this class. I THINK this has to do with my insistence on evaluating trees from the root down, when really I should be working with recursive calls from the leaves on up, but I need even MORE time to work with this function to figure it out.

Disheartened by this experience with trees (and also by my time-crunched earlier experiences with A1 and A2.1), I was dreading sitting down to work on A2.2, certain that I would while aware every spare hour I had (and some that I didn't have) being frustrated with the functions.

Luckily, this was not the case. I sat down with A2.2 on Monday morning, and managed to knock off most of the work before my lab on Tuesday night. It was so nice to walk into that classroom feeling like I had a handle on things (by the end of the night, I'd lost the handle again, as my worst enemy, linked lists, joined forces with binary tree traversals to confuse me soundly). I even helped some other students debug their code! Mine wasn't perfect-- I couldn't get one of the examples from the handout to match a longer, more complex string--but at least I was ahead of the curve this time.

Thankfully, after much perusal of Piazza, I stumbled across this post, which COMPLETELY cleared up my misunderstanding of how regex matching worked and ALMOST caused me to shout 'YES' after I successfully completed my function in the back of another class whilst watching a movie.

Having submitted A2.2 several hours ahead of the deadline (what a nice change!), I'm breathing a little easier--for tonight. Tomorrow, though, and for several days after, I'll go back to the demanding task of climbing (and descending) trees in preparation for the midterm--which I expect is going to be MUCH more difficult for me than Test 1.  Hopefully by the time Wednesday rolls around, I'll be equipped with the skills I need to find my way out of the woods.

Losing The Race Against Time

This was a hairy week for me-- I had a major takehome midterm (40% of my final grade) due in another class, too many shifts at work (thanks, coworkers, for choosing this week to have babies and/or go to South Africa), and a heavy mileage training week--and it did not end well.

Over the past few weeks, I've realized I've bitten off more than I can chew by trying to go back to school full time, work (almost) full time and train for a marathon. I'm exhausted all the time, unenthusiastic about everything and too afraid to ask for help. With the cold weather over the past week, SAD hit me especially hard and I just couldn't deal.

Although I got some comfort in knowing that I scored very high (okay, let me enjoy my one triumph this week, perfectly) on the midterm for this class, and know that I am pulling in good marks in the labs and (hopefully) on this sLOG, I'm starting to feel pretty lost when it comes to CSC148.

I've just handed in a drastically incomplete file for A2 part 1, and although I feel like I understand the concept of the assignment, and think I could work things out given more time, I'm seriously doubting my prospects for success in this course. Over the course of the past two assignments, I have spend copious amounts of time trying to puzzle out the answers to questions the assignment didn't even pose. For example, in working on A2, I spent a valuable chunk of time trying to work out function that would convert a string representation of a regex to a nested list (I was unsuccessful in this venture). I think this might have been helpful, but less than necessary for part 1.

I've also come to the realization that maybe I can't do this alone-- perhaps I shouldn't try to be so self-sufficient, but instead actually work with a partner on these things. If only I wasn't so busy with work and training an commuting and a class schedule full of conflicts with office hours, I might have time to commit to meeting with other students or a TA.

My biggest realization this week is that something in my life has got to give--but I'm genuinely unsure what it will be. I need my job to pay for my classes,  I need my classes to get me into grad school, and I need to run because it (paradoxically) makes it easier for me to breathe most days. Marathon training seems like to obvious answer, but my training time is precious to me--it saves my sanity and might be the only thing standing between me and my next meltdown.

So really, my biggest lesson this coming week will be figuring out how to ask for help.

(And on a lighter note, of all this days to spring forward and lose an hour, there couldn't have been a worse one than today.)

A Recurring Theme

Back when I was a lit student (which was longer ago than I care to think it was),  I read far too many novels far too closely, looking for the most tenuous connections to what a professor or reviewer had identified for me as "the theme" of the book.

On one memorable occasion, my class read a novel that my professor presented as "a commentary on the struggle between art and science; between 'people of letter' and 'people of numbers'". Being a novel (and therefore presumably written by a 'person of letters'), the commentary was SLIGHTLY biased, and more or less decried scientists as immoral beings who are going to destroy the world as we know it.








I struggled with that book a lot, both because I hated that it seemed impossible to be both a 'person of letters' and a 'person of numbers'. I thought I was both, studying chemistry and English literature as I was, and if I had to choose, I wanted to be a 'person of numbers'. Unfortunately, working with letters has always been second nature to me, and working with numbers has always been much, much harder.

As much as I try not to believe in right brain/left brain and other dichotomies about learning styles that I (ashamedly admittedly) view as 'excuses' or 'not trying hard enough',  I've always thought that I just don't have a math brain. I love math, I work really hard at it, but I can rarely look at a problem and instinctively know how to begin solving it.

Frankly, if it weren't for years of teachers forcing me to complete math and chemistry and physics problems using the full problem solving method (which has a name or acronym that I've now forgotten), wherein you identify all the variables, and then go through the list of equations you know and see which ones use those variables, and then which of those equations provides the sort of variable you want as an answer, I would still have no idea how to solve most of the math problems in my everyday life.

So, I think it's pretty clear that a recurring theme in my life involves the struggle of dealing with numbers and conceptual programs involving calculations that comes with being a 'person of letters' in some sense trying to 'fake it' as a 'person of numbers'.

This struggle has reared its ugly head again in the process of learning about recursion for this class.  I feel like recursion itself has been a recurring theme of the lectures since day one, and my confusion with it has been a recurring theme for almost as long.

Looking through my notes, the first two sections on recursion don't really explain what it is or why it's important. They show how to construct at recursive function sum_list using list comprehensions, and although I can grasp that it's supposed to be more efficient than using a for or while loop, I don't really understand how that efficiency is accomplished. What confuses me even more, though, is how you seem to be able to call sum_list within its own body of code. How on earth do you use a function that you're still in the middle of defining?

Next section: "To understand recursion, trace from simple to complex", followed by some more example calls on sum_list. I traced them. Great, now I understand how to use this recursive function, but I still don't know how to write one (This is something I struggled with a lot in the labs---getting a handout that showed the recursive solution for a problem, then asking me to solve the same problem using a simpler loop. How was I ever going to learn to write recursive functions if I didn't get to try it in a supported learning environment? Wouldn't it make more sense to give us the loop solutions and ask us to condense them to recursive ones?)

One week later: Let's forget recursion and talk about exceptions for a while, mmmkay? (How about no.) However, in an aside with regard to assignment one, perhaps the most helpful definition of recursion I encountered in this class--"recursion is all about solving the problem of a given instance by reducing it to the solutions of smaller instances".

The following week, a traced example of the function remove3s blows my mind (and the mind of my fellow confused classmate, who had been puzzling over the same question as me for weeks--how do you call a function inside its own definition?) I feel like i get it now--the function call inside its own body is kind of like a reset button--it takes you back to the top of the code body, and you apply the same process to the smaller instance of the problem (e.g. the inner list in a nested list where the recursive function was first applied to the outer list). Still, I feel like I know how to use these functions now, but would be lost if I ever tried to write one.

The next week, a slide bearing the title "Getting that Recursive Insight for the Tower of Hanoi" strikes fear into my heart. "Insight" sounds a lot list "instinct", which is something I definitely don't have when it comes to recursion and by definition can't be taught. But then we go on to talk about identifying patterns--I can do that, albeit with some struggle--and I see that a function can be recursive and still have if/else statements and a function body longer than one line (at some point, I got in in my head that all recursive functions had to be in the form of list comprehensions, which where often paradoxically incomprehensible to me).

It wasn't until I started studying for the midterm and came across past tests containing problems that required recursive solutions that I realized two things:

1) I know more than I thought I did about recursion, and tracing function calls really does help you to understand how it works, even if it doesn't feel that way at the time.
2) "insight" !=  "instinct";  insight can be learned, and the best way to learn it is to keep doing the same sort of problems, over and over again. After A1 and two practice tests, I was able to pick out which problems in later tests sought recursive solutions, and (despite my earlier misgivings about lack of practice) WRITE THOSE SOLUTIONS.

Following the midterm, in hindsight (and in the course of writing this post), I have discovered a new recurring theme in my academic life--trust the process. Sometimes things you think aren't helping you or teaching you anything new are doing exactly that. Learning the pieces of things can be confusing, but the feeling you get when you're able to put those pieces together is incomparable and incredibly satisfying. (And obviously, gaining recursive insight into a problem is actually a lot like looking for a recurring theme in a novel. Just because I wasn't born a 'person of numbers' doesn't mean that I can't use the skills I do have as a 'person of letters' to solve numerical problems when they show up in front of me.)

Thank God for Training

      Having jumped head-first into a lot of new things over the course of the past month (a new position at work, training for another marathon, a full-time course load), and experiencing the ensuing balancing act, I've spent a lot of time doubting my abilities to do some or all of these things.
      However, I've been delighted to find that I'm actually not bad at any of these things. My fitness hasn't actually disappeared in my three months of sparse gym attendance--from the get-go, I've been training at a higher level than for my last race, and my body is handling it just fine. At work, I've discovered that I was already fulfilling many of my new responsibilities before my promotion--now I just have a fancy title and meager pay raise to establish my authority. At school, and particularly in this course, my (too many) years of (mostly) good study and work habits are starting to bear fruit.
     When I last wrote here, I was preparing to start A1 and conditioned by the fear of an overflowing inbox of Piazza questions to expect a hard row to hoe. I've started now, and while I can't say that it's easy by any means, it's much less daunting than I expected. Much of the assignment is focused on the initial steps, particularly programming the TOAHModel class--most of which I knocked out in one afternoon of work.  Sure, I have some cleaning up and style editing to do, but I have the bare bones of the methods worked out, and it was utterly satisfying to print some representations of TOAH models (empty models, models with the first stools filled, models after moves have been made) and see what I envisioned seeing. E2 was a great warm-up as far a learning how to catch and raise errors, and I'm enjoying my newfound ability to write more versatile code, rather than having to implement stringent input preconditions.
      I'm backed up against the wall with other commitments this week--condensing my class schedule to two days a week to facilitate work seemed like a great idea until I had 2 midterms, one major assignment deadline and a lab within a 36-hour period--so I know I'll be cutting it close on the deadline for this one, but I'm confident about my progress and excited to get to work on the ConsoleController after those two tests are out of the way.

(Lab)our Intensive

Phew, it's been a busy week. (That's why this post is a day late.)

I'm trying to get used to the grind of being a full-time student, part-time (sometimes closer to full-time) employee, and a full-time marathon-runner-in-training (it counts as full time if you're supposed to be running seven days a week, right?)

Individually, these quests are all going great. I turned my training up from 0 to 11 and logged 34 miles this week, worked 38 hours and aced a midterm in another class. Together, though, they're overwhelming my life. I made an executive decision this week (read: this afternoon), to scrap Monday's three miles every week at least until the end of March, because otherwise I'll have no hope of getting caught up with my homework (including this sLOG, and A1, which I haven't started yet (eep!)).

And there I go getting off track....(much like far to many runners at the UofT Athletic Centre, ugh.)

What I really wanted to talk about in my blog this week was the lab exercises for this class.

Overall, I'm not loving the structure of lab work in this course. I understand the value of pair programming and learning to work in teams, and I'll overcome my challenges with that. (I'm a control freak and will say no more), but coming off a second lab where my partner and I have been unable to finish the work because we got bogged down in details and concepts in the early stages of the assignment, I'm really starting to take issue with the policy of not working on the lab before class.

Specifically, I hate not being able to bring written notes to class. I get the concepts we're working on in class (finally understanding recursion--thanks for the great example in class last Wednesday, Dustin! I was really struggling with how you can call a function inside its own definition, but I get it now---it's kind of like a reset button that just takes you back to the top of the code for that function), but need some time to puzzle them out and apply them to an actual problem, and two hours just isn't sufficient for me to do that.

I'm sure it doesn't help that I'm a long way out of first-year calculus, second-year stats and higher order (i.e. above about the sixth grade level) math in general-- figuring out the formula for fuel efficiency in Lab 3 was much more complicated than it should have been--but mostly, I just feel that it would be more productive if I could bring written notes and/or diagrams to the lab to help explain myself to my partner, because I can't always communicate verbally. It's really important to me to able to finish the lab work during the lab because it's much harder to access the TAs outside of those designated hours (especially when you have a long commute and a dozen other things going on in your life) and can't justify taking the trip downtown.

I also struggle with the concept of "marks for participation". Since we don't have to actually finish the lab work in the allotted time, rather just needing to make our sincere best efforts to do so, there's not a lot of incentive to to go back and finish the work. I support the notion of some (even most) works for showing up to the lab on time and working things out with my partner, but it would ease my fears about upcoming tests if I could see how well I was doing in terms of actually understanding and writing good code on a more frequent basis than the assignments and exercises allow, even if it's just running the marks through an autotester or using the PCRS system like we did in CSC108 last term.

Finally--and I get that this is a tough one, because budget cuts, and also that it's a problem endemic to academia right now---I think we need another TA in the lab. I don't know if I'm just in a particularly challenged section, but if we're going to continue to be expected to finish all of the work in a two-hour period while having barely looked at it beforehand, we need to be able to have our questions answered in a more timely manner.

Annnnnnd that concludes my few (but not-so-brief) thoughts about CSC 148 for the week. Next week, look out for a recount of pulling my hair out over A1, which I'm going to start now, and about which questions posted on Piazza have been filling my inbox with e-mail (and my heart with dread) for the last week and a half. Wish me luck!

From OOT to OOP

         First, a bit of history: my very first foray into programming took place in 9^th grade tech, a course where we spent half a semester in the computer lab learning how to type and manipulate spreadsheets, and the other half in a workshop building pop bottle rockets and other fun toys. Near the end of the computer-focused portion of the course, my teacher introduced us to OOT. We used it exclusively to draw pictures, by inputting coordinates to serve as the endpoints, verticies or centres of lines, rectangles and circles of various colours. The final assignment was to draw a house with a tree, under the sun. Being a chronic overachiever, I made my picture terrifically complicated. My house had curtains and a chimney with smoke coming out of it; my tree had several branches and many leaves (as opposed to the ball-on-a-stick models of my classmates).
        In order to create thIs great work of art, I had to draw squares on top of squares and circles on top of circles and carefully plan the layering, so as not to create the impression the picture had been drawn by a small child. 

     If someone had wanted to recreate that picture, they would have had to draw the same endless series of circles and squares. However, with my new python knowledge, I could create a class house, with methods to create doors and windows or a class tree, with methods to create branches and leaves. But that's not all! With python you can create a class and methods for just about anything under the sun, because, to quote my instructor, "just about everything is an object in python". 

     Python, and other object oriented languages, allow you to create objects that correspond to real world objects and concepts. The objects can contain both data and functionality-- they are a compound data type. Objects can then interact with themselves or each other by way of  funtions-- in a previous exercise for this class, we created "dog" and "toy" objects, which were able to interact with each other via a "play" function.

     The multifunctionality of the objects (which are an example of abstract data types) allows users to create bigger, more complex software systems with ease. For this reason, object-oriented languages became to dominant programming paradigm in the 1980s.  Later in this class, we will be writing classes and functions for a more sophisticated toy-- a ."cheesy" version of the Towers of Hanoi logic puzzle-- check back soon for updates!