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!