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.

Object-Oriented Programming

Over the past couple of weeks, I have learned much in CSC148 under the teachings of Danny Heap. The readings are a huge help as well. Considering that I didn't really have any past knowledge of programming before I came to the University of Toronto, I found the readings incredibly useful when I needed to know some background knowledge of programming. Specifically speaking, the readings regarding object-oriented programming in week one and inheritance during week three. I found these readings to be extremely helpful when I didn't understand certain concepts of inheritance and the overall background of programming. I had no idea that object-oriented programming stretched as far back as the 60's. I realized that everything that we do in Python to an extent revolves around object-oriented programming. Classes, instances, and methods are all part of object-oriented programming. We use object-oriented programming to deal with ideas and concepts that apply to the real world. Whether it be a graphing program or even a game, it all deals with objects in order to obtain the desired goal. One of the few questions that I have about object-oriented programming is how complex could our programs become. Considering that in class we have been only working with smaller classes and functions that don`t require a lot of time, what is the extent of complexity in object-oriented programming. I essence, at some point in time during the course I would like to see a very big and complex piece of programming that deals with object-oriented programming, and try and follow the logic and steps behind the code. Even though I am only in first year, I would like to know how complex could things get and how they could evolve in the future.