Week 11: Sorting and Efficiency

For the past couple of weeks we've been talking about sorting and algorithm analysis.  A couple of the sorting algorithms (insertion, selection) were already brought up last semester in 108; I found the Wikipedia pages on insertion/selection particularly helpful because they featured animations to help visualize how both work (http://en.wikipedia.org/wiki/Selection_sort).  New sorting algorithms discussed recently include quicksort and mergesort, which are generally more efficient than previous algorithms.  Quicksort works by recursively choosing a pivot and comparing the rest of the elements' values to the pivot, while mergesort works by recursively dividing the list into smaller and smaller elements (eventually reaching one) and then "merging" the individual sorted lists into one.

Runtime analysis is, in the simplest terms, a way of looking at how fast a certain algorithm executes.  For this, we can use Big O notation, expressed as O(f(n)), where f(n) is a function that describes how fast (or slow) the program runs in the worst case scenario.  f(n) may be one of several different functions including c (constant), n (linear), n^2 (quadratic), logn, 2^n, and many more.

Having a runtime of O(c) is the best possible outcome, since it means that the time the algorithm takes to execute remains the same no matter what arguments are passed to the algorithm.  One example may include:

    def constant(s):

        if s is not None:

            print(s)

where the execution of function is independent of s.

Runtimes with n raised to some number are usually determined by the number of for loops that are nested within each other.  In these cases, the speed can be directly proportional/linear (O(n)), double (O(n^2)), triple (O(n^3)), or even greater depending on what f(n) is.  Of course, the higher the power, the slower and more inefficient the algorithm is.  An interesting runtime is that of O(log n).  In class, we discussed a search function for a binary search tree of runtime O(log2 n) that continuously halves the size of the argument with each iteration, thus reducing the impact of large inputs on execution time.  In contrast to O(c) being the best outcome, O(n^n) is the worst.

As a final note, I found it weird (but understandable) that only the slowest component of f(n) mattered in determining the overall efficiency of the algorithm.  For example, an algorithm with runtime 3n^4 + 7n^3 + 1 would be O(n^4); the constants and "lower" factors get dropped off.  My only question is would there be some situation in which the other factors actually made a difference when comparing functions?  I guess in the end only the fastest-growing factor would have a dramatic impact in execution speed, but I would like to know more about this topic in the future.

Week 10: Assignment 2

Assignment 2, which dealt with regex functions, was finally finished yesterday.  Initially, I had quite a bit of trouble thinking about how to approach regular expressions, especially the is_regex and regex_match functions.  My first plan for is_regex was to parse the string at every single operator, but I realized that it would only slow down the function and that I had no idea how to go on from there; I had no idea of how to find the outermost regex operator.  Later, I thought of counting the number of opening and closing parentheses to keep track of each "layer" and actually found this to be very helpful and intuitive, so I stuck with that method and managed to make is_regex work.  As for regex_match, it was more of sitting down and outlining the function first rather than diving straight into writing.  The function basically consisted of if-else statements for every possible operator; the already-verified parts of the string argument was cut off and the remaining unverified parts was fed through each recursive call.

For the most part, Assignment 2 went by pretty smoothly after I took the time to understand the basics of each function's purpose and made a pseudocode outline.  After this project, I really do hope to read more on regular expressions and exactly their uses are.  In other news, we have started to cover runtime analysis and big-O problems in class; I've done a bit with this in 165, although there is still much I need to work on with regards to runtime analysis.  By the end of this course, I want to be at a level where I'm most proficient or can at least determine the big-O of a piece of code.

Week 9: Binary trees, more recursion

This week we talked a bit more about binary trees, including a new type called the binary search tree.  A BST is very useful in sorting numbers since every single node follows the same pattern: values smaller than the parent go to the left subtree and values greater than go to the right subtree.  Since this pattern is preserved throughout the entire search tree, recursion is almost a must when thinking about these structures. Of course, this layout makes searching for values much easier since half of the tree can be ignored each time (in an average, well-balanced tree); I find the structure very intuitive and I'd like to know if binary search trees have important applications in software design or other topics in computer science.

In exercise 3, we dealt with writing methods to construct a binary tree from its preorder and inorder traversals, as well as finding the sum of the deepest path of a tree.  In particular, I enjoyed coding the first problem, since it was something new I'd never seen before and provided a good challenge.  Unlike some of the lab problems about linked lists/binary trees, this exercise went by faster and I found myself solving the problem much faster and with a greater understanding than before.  My basic approach to question 1 was to first find the root, partition the inorder list into left and right subtrees, and repeat the process all over again.  For question 2, which was the sum_to_deepest function, I had a bit more trouble since I first had no idea how to keep track of each path along with its sum.  In the end, I settled for keeping a list of unique paths along with their sums instead of replacing the values for sum each time a greater value popped up.

Assignment 2, part 2 was posted a week back and I should probably work on it soon considering I've only looked at the instructions.  Right now, I'm still trying to understand how to approach each method, but I hope that my finished code will be clear and correct.

Week 8

We've started learning about linked lists in class and some of the methods that they use to add, remove, or change elements.  A linked list at first glance looks fairly similar to a normal list, but its structure and how it's set up means that recursion plays a much larger role (and perhaps the central role) in traversing its elements. Unlike a regular list, linked lists can be thought of as containing only two elements: one item/value, followed by a reference to another linked list or None if it is the last in the chain.

At first, I had quite a bit of trouble thinking of how to go through its elements and struggled with writing new methods in labs, although I understood conceptually what linked lists were.  I think it was my association with regular lists (and using for loops to traverse them) that gave me difficulties, or maybe it was plain inexperience; either way, I plan to learn more about linked lists and recursive methods so that I can better understand this topic.

I also finished part 1 of Assignment 2, which was a basic design project for regex classes.  Since it was my first time working with (or hearing about) regexes, I was very confused as to what each operator (*, |, .) did and what exactly constituted a regular expression.  As for the actual project, I had little difficulty coming up with parent/child classes and was able to finish with relative ease; however, I would like to further work on my design skills as several aspects of the code could have been more detailed (for example, how many parent classes and which methods would be inherited).  I do want to know more about what regular expressions are used for and what their real-life applications are in the future.

Week 7: Recursion

For most of the course, we've been covering the concept of recursion, which in a nutshell is the process of calling a method within its own definition.  There's a saying that "in order to understand recursion, you have to first understand recursion," which definitely sounds confusing and maybe even impossible at first.  A recursive method consists of two basic parts: the recursive call and a base case to prevent methods from executing indefinitely; a structure to handle recursion usually takes the form of a simple if-else statement.

For example, a recursive function might look something like this:

    def count(n):

        "Return the depth of n."

        return 1+ max([count(i) for i in n] + [0]) if isinstance(n, list) else 0

In this case, count calls on itself every time the argument is a list and returns 0 otherwise (base case), so for the end result count will return how many lists are in n.

Recursion is an extremely useful technique for programmers to use if they're looking to break the problem up into smaller, similar pieces.  Since programming is naturally supposed to be "lazy," this helps programmers save time and space by reusing a method to get a result.  A recent example I found that demonstrated the importance of recursion the most was A1.  Thinking back to the tour_move method, I realized that with recursion, the method contained around only 10 lines of code and could handle almost any number of cheeses.  It's fascinating to think how the problem presented in A1 could be broken up into smaller parts and as a result be solved quickly in just 10 lines.

We've learned about linked lists in class, which also ties in quite nicely with recursion.  Although I had trouble with writing methods for linked lists using recursion in Lab 6, I grasped the concept and hope to improve on my understanding of recursion in the future.

Week 6: Finishing A1

I've finally managed to finish A1 over the course of the last week.  Everything seems to be working smoothly and there don't appear to be any bugs (fingers crossed!), so I'm happy with the end result of my program.  It's pretty amazing how three weeks ago I had very little idea of where to even begin--this huge pile of code was just basically sitting there, waiting to be sorted out.  Even now, I still don't quite understand the details of GUIController (what exactly does lambda do, and how does Python create a graphical version of the game?), which I hope to solve by learning about graphic interfaces and more of Python's built-in functions and keywords.

Perhaps the greatest challenge I encountered during the course of A1 was writing the Tour.py module.  We had previously been shown a function for solving (impressively, in three lines) the Tower of Hanoi problem, and I initially planned to base my tour_of_four_stools method on that solution with minor adjustments.  My first draft was almost identical to the original solution (i.e. three recursive calls to tour_of_four_stools with a base case of move(source, dest), the only difference being the addition of an extra stool in the parameter and setting a value i as equal to the ceiling of n/2), but I found out to my surprise that it would only work properly with four or fewer cheeses.  I went back to the assignment sheet and realized that if I replaced the second line of my method with that of the code for three stools, the entire method would work.  I ended up with two separate methods (one for three stools and one for four stools, which called the former method) just to come up with a solution for Tour, but it worked perfectly and returned the optimal number of moves.  As it turns out, my first implementation of tour_of_four_stools would eventually force a bigger cheese to stack onto a smaller cheese, causing the program to raise an IllegalMoveError.

Looking at others' Piazza posts and SLOGs, I got the sense that I wasn't alone in finding Tour difficult to code, so that's reassuring.  As a side note, I did have trouble with my time.sleep() function which very few people seemed to have.  I tried importing the sys module and using write(), but I just could not get time.sleep() to work properly on my computer.

Besides A1, I was introduced to binary trees in class this week.  The premise seems simple enough: a tree is comprised of a parent node with(out) several other child nodes that may or may not have their own child nodes.  This concept is very closely related to recursion, as seen in its preorder, postorder, and inorder traversal methods.  Its structure made me wonder if trees could possibly play a role in creating lighting effects in video games or CGI, as each node could point to a different shade or color.  Either way, I hope to read more about the use and purpose of trees in computer science.

Week 5: A1, continued...

Finally finished the entire TOAHModel module and managed to get the GUI version of the game working (how it works, though, is beyond me).  Going back to my previous question about number_of_moves, I decided to resolve that problem by simply passing in an empty list when initializing MoveSequence.  The first time I played the game, I noticed that it would allow you to stack a bigger cheese on a smaller cheese, which wasn't right; as it turns out, I forgot to raise an IllegalMoveError in the event of an illegal move, and once that was fixed, the game was 100% functional.

As for new developments...I've began work on ConsoleController and I'm sort of confident that everything is working as intended.  The main thing that stumped me was user input--that is, in what form move commands were to be entered.  Initially, I experimented with commas and lists (which really did not work out!) but found it too confusing and annoying to figure out, so I opted with just numbers separated by a space (something along the lines of 2 3, 4 1, 5 8....and so on) which was then split to create a list.  Once that was out of the way, everything in ConsoleController fell into place: I quickly finished play_loop and by then, the only thing I really had left was Tour.py (which I still refrained from thinking about).

I haven't really been looking at others' SLOGs at this point, but from what I can see on Piazza, a lot of people have technical questions about A1 and not many are stuck with actual programming.

As a last note, I did some digging into this four-stool problem and found a Wikipedia page on the Tower of Hanoi (http://en.wikipedia.org/wiki/Tower_of_Hanoi).  The four-stool variant is called Reve's puzzle, and unlike TOH, researchers are still working toward discovering an optimal solution to the number of steps.  I just thought it was pretty interesting how Reve's solution included a portion of the TOH solution.