Slog Entry Week 12

Suggested Topics

Sorting Algorithms

Selection Sort:

Selection sort finds the minimum item in the list, and then swaps it with the first item. It then selection sorts the rest of the list, excluding the 0th element, which is already in order.

Selection sort is what I feel might be the approach of a first year Computer Science student if asked to write a sorting algorithm, provided they had never heard of a sorting algorithm. The naive idea of grabbing the min over and over again until you have a sorted list is very intuitive, although, it turns out, very inefficient. You have to do n passes through the list, and a swap each time. This makes a total of n + n-1 + ... + 1 comparisons, which equals n^2 - n and puts the algorithm in O(n^2). Although slow, it doesn't use a lot of memory, doesn't require you to subdivide the list into a billion pieces, and doesn't require a ton of recursive calls. It has a kind of beautiful, naive simplicity. I wrote my own sort that relies on the builtin min AND max to improve on selection sort slightly by reducing the number of passes through the list. If I knew of a function that could simultaneously find the min, return it, and remove it from the list (a sort of min_pop), it would be much faster indeed.

def min_and_max_sort(L):

    L1 = L[:]
    if len(L1) < 2:
        return L1
    else:
        K1, K2 = [], []
        if len(L1)%2 == 1:
            j = min(L1)
            K1.append(j)
            L1.remove(j)
        while L1 != []:
            j = min(L1)
            K1.append(j)
            L1.remove(j)
            k = max(L1)
            K2.append(k)
            L1.remove(k)
        K2.reverse()
        return K1 + K2

Quick Sort:

Quick sort selects a pivot element, and places it in the middle of two new created lists. The one on the left is the list of all elements less than the pivot element, the one on the right is the list of all elements greater than the pivot. The algorithm then quick sorts both of the new lists. On average, quick sort is in O(nlogn), since the pivot process divides the list roughly in half (the log2n component of the runtime), making 1 pass through the list that takes n comparisons with the pivot (the n). It does this until the list is sorted. The simplest quick sort uses the [0] element of the list as a pivot. A problem arises when this simple quick sort is called on an already sorted list. Then, the left list is empty, and the right list contains all the elements except the pivot. Quick sort ends up running n + n-1 + ... + 1 comparisons, putting it in O(n^2). This problem can be circumvented by choosing the pivot at (pseudo)random. Thus, the odds of picking the worst possible pivot (the min or max of the list) are low.

Intuitively, one would expect that quick sort is the fastest of all known sorting algorithms, because it has quick in the name. I was appalled to discover that this is not in fact the case. By far the best part of learning this algorithm was Prof. Heap's one line, recursive, list comprehension implementation of it. My sense of code aesthetic has pretty much only been shaped by Prof. Heap and this course. That said, in my mind, the best of all possible code is recursive, one line, and involves a list comprehension. It is practically self-documenting, and makes very clear that the nature of the solution to the problem involves solving smaller instances of the same problem.The random pivot implementation is especially clever, and I think makes use of all of what is good about my random sorting algorithm (Slog 11), the use (pseudo)randomness. Because I think life seems random to humans, because of our limited sensory and intellectual faculties. Thus, the idea of randomness is very intuitive to us. For example, when we roll a die, it seems that the result is random, but the roll is already completely determined by the physical factors going into the roll (up to randomness at the quantum level). If one had perfect knowledge of all the initial conditions, one could compute the roll. One might need a supercomputer for that, but that is what computer science is for.

Merge Sort:

Merge sort divides the list in half until it is broken up into lists of length 1. It then 'merges' adjacent lists, by adding them such that the resultant list is sorted. It merges by looking at the first element of each of the two sorted component lists being merged, and adding the lesser element to a new list. It does this until both of the old lists are empty, the new list is sorted. It runs in O(nlogn) since it divides the list in half several times so that it does not have to make n^2 comparisons, as it is only comparing the first element of 2 lists, rather than passing through one list over and over again.

Merge sort is the ultimate divide and conquer algorithm. Again there is a very neat and tidy recursive list comprehension implementation, because the solution is indeed to divide the problem up into smaller problems (indeed, list of length 1 sized problems). In the assigned reading, ALL of the algorithms were implemented iteratively, and they were hideous. Good god. Something that complicated is firstly completely unreadable except with a Herculean (Solomonian?) effort, and secondly is more vulnerable to human error, as complexity increases the likelihood of mistake. In this way, solving a recursive problem recursively is far more intuitive, even if the mind cannot follow make sense of stepping through the program as it makes 1000 recursive calls.

Efficiency:

I have reflected on the efficiency of the sorting algorithms under their entry. The general concept of efficiency is one that is useful to Computer Science. It is somewhat satisfying to write code that 'works' or 'gets the job done', but it is far more satisfying to know that you've written code that solves the problem well. This concept of 'well' is based partly on readability, but also largely on efficiency. It makes the difference between doing a job and doing a good job, and requires an intimate knowledge of how your program actually works. It also forces considerable visualization of what the machine is doing as it runs your code. These are educative things, and promotes a level of code-consciousness and revision for optimization that I think are useful in any task. It is the same as editing an essay, or a mathematical proof. Without destroying the ideas, you want to make them clearer, and to communicate them with less effort or words (more efficiently). This detail orientation and desire to improve the utilitarian and aesthetic value of your work are part of what makes the works of man so excellent. Does a chimpanzee care about the beauty of the stick it uses to get ants out of the anthill?

Funny efficiency story, I wrote my own Fibonacci(n) function about a year ago. I wanted to take CSC240, Enriched Introduction to the Theory of Computer Science, but I didn't have the 148 prerequisite or corequisite at the time. When I emailed the Prof about it, she said that the most important thing carried forward from 148 into 240 was recursion. She said as long as I could demonstrate that I understood recursion, I could take the course. So what I did, I talked to my computer programming father about it, and he explained the idea. I did some independent research, and the I wrote my own Fibonacci(n), much like the naive version we looked at first in class.

Looking back with hindsight, it's obvious that I had no concept of efficiency, or caching for speedy storage to prevent redundant function calls. And this must have been obvious to Professor Ellen as well. Much like Python, though, she decided to let me take the course, thus giving me enough rope with which to hang myself. I ended up dropping the course after it seemed too scary from the first couple of weeks. I decided to take 148 first, and here I am, signed up to take 240 next semester. Hopefully it goes better this time. Hopefully.

There was another issue at play too, besides my own lack of desire for an overdifficult challenge. There was a Russian Literature course in the same slot, and it seemed way too good to miss. So I took that instead, and I have no regrets. It was amazing course with an amazing Professor, and I learned a ton about literary analysis. And Russia! Maybe there's a course on Nabokov I can take next semester instead of 240...

So the memoized Fibonacci was interesting on a personal level as well as an intellectual one. Again, excellent techniques I learned from Prof. Heap that I can easily imagine using at some point in the future.

SLOG Entry Week 11

Back to the regular grind after a long 2 days of reading.

Regular classes resumed this week, and for this I was thankful. I missed Prof. Heap's excellent lectures. Besides teaching the theory, I feel like I learn more good coding techniques from watching him code examples than from reading. When I actually go to write code for the course, a large amount of the conventions that I use that I think are efficient, interesting, or clever at all, are copying things that I've seen Prof. Heap do (list comprehensions, ternary if, tuple packing, and generator comprehensions are all good examples). However, it felt somewhat hollow without the exercises to accompany it. This may not make me popular with my peers, or with myself on in a lackadaisical mood, but I think there should be more exercises. If there's time in a week to do a lab, surely there's time to do an exercise. They're great for learning, I like doing them, and they're one of the only productive things I can do on the bus. In their absence I've taken to books, audiobooks, and radio shows, and good heavens are Canadian radio shows boring. I listened to an entire half hour segment getting various opinions (including that of the head of the American society) on doorknobs. Yeah.

MapReduce was cool, as was property. I can see that MapReduce has a lot of power, and I love that it is recursive in nature. It inspires me to know that real world software companies are using the recursive techniques that 148 drills in to us repeatedly.

The lab was not my favourite. It didn't involve solving any problem, or building any program from the ground up. However, it did deepen my understanding of the various sorts, and I'm confident that I know how they work. Also, I did this lab on my laptop in PyCharm instead of Wing. PyCharm has a lot more static analysis, which helps me catch errors before running my code. I also like the autocomplete feature, because I'm super bad at typing under pressure. Especially when someone is watching me, like my partner or the TA. I swear I get ten times worse. And the shift key on the keyboard in the lab is not sensitive enough. So many of my brackets come out as 9s and 0s, it's ridonk.

I made my own sorting algorithm this week! Here's the code:

def rand_sort(L):
    '''
    Shuffle the list L until it is sorted.
    '''
    J = L[:]
    i = -1
    while True:
        i = i + 1
        if i == len(J) - 1:
            return J
        if J[i] > J[i+1]:
            shuffle(J)
            i = -1

Basically, it checks if the list is sorted, and if it's not, it shuffles the list, and repeats the process. Occasionally, it's very efficient. One time, it sorted an 11 item list in 60 seconds. Another time, it took 45 minutes. For very small inputs (3, 4, 5, 6 elements), it's pretty much just as good as the other sorting algorithms (at least BubbleSort), because there aren't very many permutations. But that decreases rapidly as input sizze increases. For a 5 element list, there's 120 elements. For an 11 element list, there's around 40 million. I put a print(J) command in one version, so I could watch the output as it goes. It's kind of funny, it's so obvious to a human observer when some parts are right, especially when the first element is right. I could perhaps make a more efficient version that only shuffles the portion of the list that isn't sorted. 'More efficient' is of course relative, rand_sort will never be as good as TimSort. Except sometimes it is. Randomly.

And no random number generator is truly random, so it could fall into a pattern of trying the same orders over and over again, without reaching a sort. In fact this is probably a good way to see how random.shuffle works, by reading the printed output.

The bloody print command! I learned on Python 2.7, and there, the print command worked in the following fashion (which is far more intuitive, I believe):

print 'hello world'

Even easier, one could simply:

print foo(bar)

might have worked, allowing Python credit for some fairly clever automatic interpretation of words that are not assigned as variables. Now, one must wrap round brackets around whatever it is that is to be printed, adding additional layers to what is already likely a phalanx of nested brackets, especially where multiple function calls:

pring(list(str(len(foo(bar)))))

something that would be nearly impossible without a good IDE. Thank goodness for PyCharm.

My first foray into the field of computer science was entirely self-directed, through an online tutorial called CodeCademy. The point is, I didn't spend a lot of time programming before 148, and certainly even less of that time was spent writing print commands. Yet still, without fail, EVERY TIME I go to print anything, usually for debugging purposes, I default to Python 2 syntax. Why!? I know they say that whatever you learn first seems more intuitive to you, simply by virtue of precedence. But I didn't even do that much Python 2! Surely that is testimony to the greater intuitive clarity of the former. ISN'T IT!?

Other than that, not a big week. Somewhere around this time I started coming early to the Wednesday lectures. I really like coming early and sitting in the front row, I feel like it's a better lecture experience. It's more exciting and I pay more attention. If only I could wake up earlier. #commuterproblems

SLOG Entry Week 10

I'm not an organized person. But Computer Science has given me a fresh excuse for why that isn't a personality flaw! My disheveledness derives itself not from a lack of interest in sorting, for the processes by which one can sort are fascinating to me, but from genuine laziness. And laziness is one of the cardinal virtues of a computer scientist. Like mathematical computations, sorting is not interesting to do, but is interesting to program a computer to do it for you. That way, all of your intellectual capacity goes to the much more interesting and engaging task of theory and implementation, and the computer handles the grunt (or Mathematics Undergraduate Student) work. This is not true just for sorting, but for all things, and is why I think programming is so appealing and enjoyable.

 This week was dominated by the test, which did not include sorting algorithms as part of the tested material (although my belief in this fact was shaken by inadvertent eavesdropping on some of my classmates in the 7 minutes before the start of the exam. This caused me much immediate pre-test anxiety, until I came to peace with my lack of preparation on this issue, realizing that part of the assumption of education is that repeated exposure to intellectual labour increases your ability to solve problems under stress. It was an eventful 7 minutes). To be perfectly honest, studying for my Analysis test this same week occupied the vast majority of my 'Reading Two Days' (which I am trying to get off the ground as a superior name for the 'Fall Break', as 2 days is not much of a break, and it's practically winter). That is not to say that I did not study for CS. I did. But some of my preparation was rushed. I spent the night before the test copying all of my code from each exercise and the assignment onto my 'aid sheet'. I think that the actual act of reviewing the material was itself more useful than having the code with me during the exam, but I suspect that's the intention of the 'aid sheet' mechanic, to trick the student into learning while assuaging her fears that might otherwise inhibit her ability to demonstrate her learning in a high-pressure environment. Pretty sneaky.

It was also not until the tuesday of this week that I successfully completed Lab 8. That was by far my worst lab. I had not had enough sleep or enough breakfast, and this fell in the time period between when I stopped drinking coffee (it causes me terrible migraines) and when I started drinking tea. That whole period is one gray blur, where all of my 'spare time' (if such a thing exists) was eaten up by naps. Anyhow, with an unclouded and amply caffeinated mind I was able to mount a successful assault on the lab, an excellent piece of educational assignment. It was difficult, but impossible to come through without a thorough understanding of binary trees, linked lists, and traversals. Superb. Once I had more or less wrapped my head around how my partner's functioning code was linking the 3 intermediate lists together into the end product, part b) was a snap. In fact, I must revisit that code now, as it would be instrumental in solving the most difficult portion of lab 10. It's almost as if these labs are working together to give us a unified understanding of some kind of material. Hmmmmmm.

I was pleased as I read through the exam before committing graphite to paper to note that it was fairly easy, and was all material that I understood thoroughly (mostly binary trees), with a taste of recursion. I finished my first drafts of all three programs in the first 20 minutes. The next 20 minutes went to bug fixes, most of which were removing incorrect 'self's that I had written in non-class-level functions (a few weeks of object-oriented programming can apparently form strong habits). By the last 10 minutes, I was efficiency-optimizing my code. My code that would never actually run. I got it down to 2 recursive calls instead of 4, utilizing a technique Aida had shown me in the previous lab. I wanted to make sure it didn't use up too much stack space on the paper, and that it wouldn't take the marker too long to run my code on pencilled test cases. Wasn't that considerate of me? I included my more efficient version alongside the first, which I felt was more explanatory, as I suspected that I was not being marked on efficiency, and did not want to jeopardize the correctness of my algorithm for the sake of showing off.

I was glad that my understanding of the data structures that we learned in class had culminated in my performance on this test, and I was perhaps equally glad that the test was easy enough for me to get an A. That's rare for a person in so many Math courses. Linked Lists in particular were a weakness until I reviewed them, as I had skipped that Lab to study for an Algebra midterm, which I failed. And then I dropped the course. Excellent prioritization. I should have stuck with computer science! Computer science treats me right, like the strong independent woman I know I am.

I took some time this week to read through the –well, readings, I guess they're called-- on sorting algorithms, and found them especially interesting. The visual representations were cool, although they were in no way, shape, or form as instructive as Danny's sorting of Second Cups in real time. It was a rare opportunity to watch a man push cups around a table without the lingering fear that he's trying to swindle you out of your money. If any money is being swindled out of me by the University, it's likely the University's own, or the provincial governments, and it's probably by Rosi service charges moreso than by honest fees asked and paid for intruction. Curse you, service charges. It's strange, I pay so much in service charges, and yet I don't feel that I get very good service. I pay you $20,000 a year for 4 of the best years of my life and you can't cut me some slack!? Come on!

SLOG Entry Week 9

For the first part of the week, most of my time went to finishing up the assignment.

We had already finished the string_to_tree method in the initializer of regextree. What was left was writing the match function. Some of the rules were quite easy to convert to code, but dot and star were quite difficult. For star, I couldn't quite figure out how to slice up the string into equally sized pieces to see if the given string matched both, so I did what was somewhat of a brute force solution, and wrote the program to iterate over all possible slices of the string. This was a later source of lost marks on the assignment, much to my chagrin, but it worked.

Dot was a different case. For dot, you actually are supposed to iterate over all possible ways of breaking up a string s into s1 and s2, so my code did that, and I received full marks. I thought that my code for star was the perfect synthesis of recursion and iteration, but it turns out that dot is a better example of that. The difference is that in dot, iteration was necessary in order to make recursive calls on multiple possible cases. In the code for star, I just used iteration to try different recursive calls until one worked. Kind of like shooting at a pop can with a shotgun loaded with buckshot. Did I hit the target? Yes. Did I also hit a large part of my neighbour's fence that was behind the target? Indeed I did. And it turns out that I later had to pay property damage later.

I had some code that I thought was great, and I thought it worked on all possible test cases. But there was one that I couldn't get it to work on. It was regex_match(RegexTree('(((1.0)|(0****.1*)*).(0|0))'), '0010'). This expression was too ludicrously complicated to be able to identify what the problem was, so i gradually narrowed it down to matching '(0***.1)') and '001'. What went wrong, was that if there were 3 or more stars attached to the left argument of a Dot, the code didn't work. 2 stars? Fine. 3 stars on the right argument? Totally fine. 2 on the left and 3 on the right? No problemo, compadre.

I puzzled over this for a while before I actually stepped through it, only to discover, much to my surprise, that the node that match was working on was not DotNode(StarNode(StarNode(StarNode(RegexTreeNode('0', []))), RegexTreeNode('1', [])) as it should have been, but something completely wrong and stupid.

string_to_tree wasn't working! This whole time I programmed under the assumption that that code would be the last thing to survive world war 3! It was the only support beam of my CN Tower, my life-raft in a choppy ocean of regexes, and suddenly it was gone. I was devastated. I wasted a whole bunch of time trying to fix the problem in regex match, when the problem was in string to tree the whole time.

I guess this shows the importance of rigorous unit testing. I could have saved myself hours if I had known where the problem was where it arose, or if I had solved it before even starting the match function. I will make sure to include unit testing of more difficult and varied test cases in the future. If only there were a program that could perfectly find any possible bug in a program that could arise on any possible input. Alas, reality intrudes, in the form of the Halting Program. Nothing seems to be perfect or absolute in this all-too-human universe of ours, but I take comfort in that nothing seems broken entirely beyond recognition either.

I located the problem, stared at it, and gave up. I sent it off to my partner (outsourced it to far Asia, I like to say), and she took her turn staring at it. She almost had a solution, although she described it as quite roundabout (I never took the trouble to understand it, I was too busy trying to come up with my own). Eventually, I solved the problem with a while loop! A bit of iteration that I learned more so from the labs and readings than from the lecture, or from Assignment 1, the tour of Anne Hoy (I still think that's hilarious, especially after I learned that Hanoi is in fact in my partner's ancestral country. That was a semi-embarassing conversational, in which I revealed my hereditary geographical ineptitude. My father likes to say that I get it from my mother).

Definitely this course has been focused on recursion over iteration as the master technique to solve all (or at least a broad class of) problems. I don't know what 108 was like, I didn't take it. But I tend to think that I will be able to teach myself iteration, as it is a lot easier for the human mind to understand, particularly in terms of what the computer is doing. Human brains aren't 'programmed' to think recursively, as Prof. Heap emphasizes. I'll certainly have to pick up some of it if I can expect the demands of CSC207 and 209 not to pull a lever to open the trap door beneath my feet, only to reveal that I was in an airplane 36, 000 feet in the air, leaving me to a parachuteless free fall into a lifetime of working as a cashier at McDonalds. I have a lot of academic performance stress.

Anyways, the rest of this week was spent on sorting algorithms, and I'll get into those next post. Toodles!

Slog Entry Week 8

Well, I didn't start the assignment over the weekend as I had hoped I would have learned to do from my experience with Assignment 1. What can you do? I had a lot of math homework.

Anyway, thanks to the completely appropriate pushiness of my partner (the text read "When do you want to meet TOMORROW to work on the assignment", emphasis added), I settled in for ~3 hours of work on Wednesday (read: 2 hours of work on Wednesday). It was productive, we got a lot done. The first thing we did, after reading and understanding everything in the handout and given code that we needed for step 1, was write a function that converts trees into strings. Shortly after finishing it, we were slightly upset to realize that it wasn't actually necessary. Hmph. Oh well, it was a good learning experience, parsing trees into strings is not that different from parsing strings into trees, and it gave us a valuable unit testing method, wherein we could create a tree, turn it into a string, and then call our string_to_tree helper function on that string to see if it output the tree with which we started off. Would that we were working in abstract mathematics, where we could simply define our parser as f(x), and then the desired string_to_tree would be simply f^-1(x), the not-explicitly-defined inverse function that we then wouldn't have to compute (as long as we could prove its existence and uniqueness). For the practical solution, we have to get our hands a bit dirty.

We very quickly whipped up some code that worked on the easy cases, and then we had rules for what to do individually with each of *, ., and |. They even involved some nifty applications of find and rfind to look for a left bracket starting from the beginning of the string and for a right bracket from the end of the string respectively. However, we couldn't get those rules to execute in the right order. It got to the point where we could change which test cases pass and which fail by manipulating the order of the relevant lines in the function. Not very helpful. At that point, we had to grab some fried chicken before CSC165 in order to be able to absorb any of the material, so we bailed.

Next morning, I decided to get the exercise done. It passed all of the tests on the first pre-mark this time, possibly because I wrote better test cases. But, more importantly, as I was doing the assigned readings (gotta love 'Code Like a Pythonista'), I came across some code that did something similar to what we wanted string_to_tree to do (string_to_tree_to_do ). In the sample code for binary trees, there was a group of functions designed to work together to parse arithmetic expressions containing sums and products into tree representations. I read this carefully, and then using these ideas, wrote some code that worked for strings with bars and dots. After all, bars and dots work very similar to arithmetic's 'plus' and 'times', at least from a purely syntactic perspective, looking at regex strings. Even down to inclusion of brackets.

Making the code work around stars was a more daunting task. I added a star clause (if, else) closer and closer to the fundamental level, with better and better results each time, until eventually all the cases worked! I then realized that you ONLY need the star clause at the fundamental level, the rest are extraneous, which greatly simplified my code. I think we'll go forward with this approach, because it works, but I still would like to get our original code working, if only as a purely theoretical exercise. Maybe we could even compare runtime.

In any event, things are looking good, and we should have a match function done soon.

In the lab I was finally able to reduce the 4 binary tree cases I mentioned in my Week 7 cases down to one line of code. It's especially easy when doing a sum. You simply add the result of a recursive call on self.left IF self.left, else 0. So too for self.right. I'm confident that this way of thinking about trees can be applied to other problems as well. Just when I think I'm the master of recursion, it throws another piece of knowledge at me, and I become that much more appreciative of its beauty. I think the wide range of applications of recursions is indicative of the recursive nature of being. I'm glad to see the way in which computer science adds to our appreciation of the beauty of the universe, through understanding the ways in which it operates. I find that most subjects have this, otherwise they wouldn't be very interesting at all.

Slog Entry Week 7

When Prof. Heap was coding in lecture this week, he used the tuple packing notation that we learned in last week's lab. I thought that was pretty slick. Both because of the advantages of tuple packing (it reduces confusion by assigning multiple variables in the same step) and because it was excellent integration of tutorial and lecture. The labs are a really great learning opportunity, and a lot of the coding that I do in a week is done in lab. Once I got a high-functioning partner relationship going, I really started enjoying the labs. I know Week 6 especially we finished all of the code in no time, with very few instances of the dreaded "getting stuck". It occurred to me that not only are labs enjoyable (and marked independently), but they're being utilized effectively to increase the amount that we can learn from lecture and tutorial combined. They make it possible to fit more content in the course without simply swamping the student with material, as I am experiencing in some other courses at the moment. *cough* Every math course *cough*.

My only other experience with labs was with first year physics last year, and I really strongly disliked them. Firstly, my TA barely spoke English at all, so his explanations and 'help' were completely useless. Secondly, the groups were too large to be high-functioning. I mean, you've got 4 people doing a lab report that ultimately has to be written by one person. Inevitably, someone ends up useless, and just through lack of assertiveness (not lack of intelligence), I end up that person. 

Beyond that there's increased risk of having a personality clash. In a group of 2 people, there's one possible personality conflict, and if that happens, you just change groups. In physics, the groups were immutable. In a 4 person group, applying some basic combinatorial methods, we obtain that there are

(4 * 3) / 2! = 6 

personal relationships, sextupling the risk of clash. And this happened, with at least 2 of the connections.

Also, in a 2 person group, generally both people have laptops anyway. But if there are no laptops, it doesn't take that long for one person to just grab the keyboard and try out the idea that they think will work but whose validity they can't convince their partner of.

The pair-programming thing is genius too. As much as my egotistical side hates to admit it, I do code better and faster when there's someone looking over my shoulder. There's a bunch of little stupid mistakes that I still make, that I think I'll always make (not putting the thing that you want to print in brackets; did anyone else learn to code on Python 2?). More importantly, if there's some fundamental flaw in the theory backing my approach to a problem, either simply by explaining my method aloud I'll realize it, or my partner will be able to (eventually) convince me of it, and we save valuable time. From the ansatz (German for approach, educated guess in Mathematics), I'll often be able to glean valuable insight into what a more effective solution might be, and if not, my partner has cooked one up in between bouts of fuming as I write my misguided code. In the end, we get a better finished product with less precious time wasted.

The exercise was not too challenging. Or so I thought. I wrote out my code, commenting as I went and running doctests like a good little CSC148 student. By the end, it passed all of the tests, and I was confident in its codified virility. The next day, when I checked the premark, I viewed the strangest result since my code for Exercise 1 failed the 'easy' tests and passed the 'hard' ones. 

My e5a code failed three tests and passed five, e5b passed three and failed 5. In both cases, one of the passes was the PEP8 style checker, so it's actually much worse than it sounds. I was baffled. I had no idead what could have gone wrong, until I actually went and took a look at my code. It turns out I had unwittingly (or witlessly, if you prefer) written my function so that it only worked on symmetrical trees. Duh. That's, like, the most obvious of the potential problems. I clearly should have checked it. In the future, I will be more careful to write an exhaustive set of tests.

This is an interesting psychological phenomenon that I've noticed when I'm programming. Often, I'll rush through the process of actually writing the code so that I can start testing less mediately (not quite immediately, but better than completely mediate). Almost without exception, my code with fail (often raising an exception of its own in the process(or)). Looking back at my script, I'll often notice some problem completely unrelated to the specific failure that got me looking at the code, and fix that, only to encounter the same failure. Eventually I fix the right problem, but the moral is that even just by thinking the code failed, you gain a piercing critical lens through which to give your code a second look, producing results leagues ahead of the initial ansatz. Perhaps when coding by hand on a test or exam, I should mentally simulate a run of the program that ends in a failure, so that I can trick my self into a more detail orientated state with which to take that all too important second look. 

Perhaps I should just code slower and more thoughtfully, and not run the test before I've taken the second look.

I went back, tried a few things, and settled on code that broke the problem down into 4 cases that correspond to the truth table for existence of a left node and existence of a right node. I had one case for two children trees, one for trees with only a left node, one for trees with only a right node, and one for trees with no children and a lot of disposable income (leaves). Although this made the code work in every test case, I was vaguely dissatisfied. I felt there was a more efficient solution somewhere. It wasn't until Week 8's lab that I would find out what this was...

Slog Entry Week 6

This week was pretty much all about the midterm. I didn't know exactly what to expect, but I thought to myself, "what are the things that the professor mentions every week?". So I figured that there would probably be a question on the midterm involving a list comprehension, and one involving recursion.

As it turned out, question 1 was computing some instances of a recursive function.
Question 2 involved writing a recursive function that uses a list comprehension.
Question 3 was implement a class with two methods that use list comprehensions.
Luckily my guess was spot on.

I hope it turns out alright, I feel pretty confident about my performance, although I'm not sure if I was supposed to write an initializer for the subclass FunctionalList. Hopefully in the absence of a subclass initializer it just calls the superclass constructor. Hopefully.

I went in to question 1 with a bit of an edge, because during the assignment I had computed a bunch of those M(n,i) least number of moves calculations by hand. I was trying to figure out which n's it was working optimally for (where n is the number of cheeses to move). Before I wrote a function to calculate the optimal split, I tried n // 2, which is optimal for some cases but not others. In the darkest hour I hard coded a bunch of control flow that used n // 2 for n = 5, 6, 9 and (n + 1) // 2 for n = 3, 11, 15 ... etc. It was hideous and confusing, but it worked up to n = 14, with no discernible pattern for the optimal i. In hindsight, if there was a discernible pattern, it wouldn't be an open problem in mathematics. But it was early in the morning, and I was pretty heavily caffeinated.