Sorting and Big O

This week, Danny got the chance to talk to us about Sorting Algorithms and their respective run times. Through the use of the playing cards and the diagram that was drawn two weeks ago, Danny helped me gain a better understanding of sorting. When referring to merge sort, it was difficult at first to understand why it was O(n log n). Through Danny's long explanation on the slide, it made it incredibly clear. Danny broke down the sort bit by bit and was able to determine the runtime without error. This made it easier for me to understand how merge sort's run time worked. By splitting the list n times and merging them, we get two separate linear run times of O(n). By increasing the number of sub lists, the equation increases by an exponent. However, when the exponent is the size of log n, the sub lists have a size of one, which means that the runtime must be O(n log n). On other algorithms, like the ones from the test for example, you could tell that one of them just had a normal runtime of O(n) considering that the runtime always depended on a constant of 10.  Lastly, it was a big help to see the hierarchy of upper bounds in the week previous. Danny had drawn out huge circles depicting what each Big O was less than or greater then. Showing the smallest run time to the largest run time helped refresh my memory from CSC165. In conclusion, even though I find Sorting and Big O to still be confusing at times, by dissecting the methods through merge sort, Danny had been able to show us exactly why it had a run time of O(n log n) and explained it simply enough for the class and I to understand.

Week 9: Binary Search Tree and Big-O (Late Post)

I apologize for the lateness of this post. Usually this post would have been handed in on Friday, March 14, 2014, but due to travel and WiFi connectivity problems, I am posting last weeks response now. During last weeks lectures, Danny talked about Binary Search Trees and Big-O run times. Both of these lectures reminded me of my CSC165 class I had in first semester. I did have trouble with the Big-O notation from the CSC165 class considering that we were not coding but actually trying to prove it on paper. It's relieving to hear that it won't be necessarily required of me to do that. Thanks to Danny, he was able to re-iterate some of the characteristics of the Big-O and refresh my memory of what it is. Furthermore, when it comes to Binary Search Trees, using both insertion sort and selection sort, he was able to show me the differences of the two sorting methods effectively using the playing cards and the projector. I find the concept of searching through a Binary Tree easy considering that if you are searching for a number less than the root, you can ignore the right sub-tree and recursively call the same function on the left sub-tree to find the number you are looking for. In conclusion, Week 9 for me was like a refresher week from CSC165 and a helpful reminder for the different kinds of sorting. Thanks to Danny, I have gained a better understanding of these concepts and I hope they can benefit me more effectively throughout the next coming weeks.

LinkedList, Binary Trees, and Test

During this week, a lot has happened in CSC148. in the lectures, Danny talked a little bit more about Linked Lists, and he began to teach us about Binary Trees. During Mondays lecture, he taught us the two different ways to think of Linked Lists. The first way is to think of it as a list made up of an item and then the remaining list. The other way to think about it is an object with a value with a reference to other objects. These two different ways of thinking helped me get a better idea of what Linked Lists are. On Wednesday, Danny gave us back our test marks and taught us a bit about Binary Trees. I find the concept behind Binary Trees to be a little simple since its just a tree with the left node less than the root and the right node greater than the root. Furthermore, I got a 79% on the first term test which in my opinion is a good mark. I could have done better if I had reviewed Trees a bit more but a 79% is good nonetheless.

Recursion Week 7

For the past couple of weeks, Danny has taught us how to use recursion. It has been one of the most useful methods of programming that I have learned so far in this entire course. Recursion can be used in most of my programming code to solve my problems. It's is useful when it comes to Trees, Linked Lists, and re-iterating over certain loops.When given data of nested lists, dictionaries or tuples, recursion allows us to recall the same function to go into the nest of data to grab the information that we need. For example, in week 4 we were given the following code:

def rec_max(L):
    """
    Return the maximum number in L, a possibly nested list of numbers.
    
    >>> rec_max([17, 21, 0])
    21
    >>> rec_max([17, [21, 24], 0])
    24
    """
    return max( # the maximum of
        
        # list of maximums of sublists or plain numbers in L
        [rec_max(x) if isinstance(x, list) else x for x in L])

 This code during the lecture allowed us to the find the maximum element within the list of nested lists. Without recursion, it would be difficult to implement the code for this function. With recursion, by recalling the same function and re-iterating over the list every time an item in the main list is a list, we can append each item within the nested lists to one big list. Once we have the one big list of all the items without the nest lists, we can find the maximum element with ease. 



Furthermore, by utilizing the recursion method combined with list comprehension, I am now able to write code for complicated functions within one line. Without the combination of these two methods, writing code for my functions would be extremely difficult and long to do. In conclusion, by using recursion, I can recall the same function to preform the same function over a series of data to collect the information that I need with ease. Without recursion, coding things like Trees and Linked Lists would be incredibly difficult. 

Recursive Structures

This week, Danny taught us about nodes and its properties like edges and roots. It's great that Danny was able to give us all the terminology related to the structure. It med it much easier to point out things while tracing through the examples and explain why with my fellow classmates. Danny helped make the lectures easier to follow through the use of picture and drawing out the sequence with pre-order and in-order. Without the picture I would have had a much harder time understanding the material. Other than that, this weeks lecture were very interesting and new to me during this course so far.

Recursion Cont'd

This week, Danny allowed us to trace some recursive functions. This week gave me some insight in how I should be thinking about recursion and the steps to follow. I thought that this weeks lectures were really helpful as well as the tutorial. The tutorial gave me a better understanding of what recursion does and how I should be coding programs that require recursion. Thanks to my TA, he was able to explain recursion to me in a way that was understandable to me. This weeks tutorial and lecture helped me greatly with our first assignment.

Week Four, Recursion

This week, we were given a better understanding of what recursion is. The whole concept behind recursion is interesting to me. I especially liked Wednesdays class where by using recursion and turtles, we were able to create a display of many fractals. At first when the tracing the code, I had a little bit of trouble. I wasn't following the recursion method when tracing and it gave me a weird picture. Now that I have seen what it actually is with the display of fractals, it's easier to trace the code and demonstrate what it does. I will probably look over the readings again just so I can get a better understanding of recursion but overall I got the gist of the concept. Recursion will be a handy thing for me when it comes to coding and once I 'master' it as Danny says, then I will feel more confident.