Hints on Assignments and Sorts

Half of the portion of this week's lectures is focused on Assignment 2 Part 2. The prof used all of the monday class to provide substantial hints as to how the functions in regex_functions should be programmed. Some expressed dismay since they spent time beforehand figuring out what the code should be and then the prof tells the entire class about the solution, so they feel that their efforts are wasted since they could've just came to class and listened, and allocate the time they used to solve it on something else. However, personally, I think it is perfectly justified for the prof to give hints like he did in class, note that he didn't have such a session right after the assignment II is assigned but rather only three days before it is due. It is extremely helpful towards those who have thought heavily on the assignment over the past month and are still stuck due to a small issue; all they needed to finish their code are those few lines about the assignments on the prof's class sides. For some people it is not as if they have no idea how to code in python, but rather just a push to get them started.

On the second portion of the week, we looked at a few more kinds of sorts which perform significantly better than the ones we had before such as selection sort or insertion sort. The sorts we saw were quick sort and merge sort, they all require the partitioning of the list into smaller bits and call the code recursively to sort everything. The performance difference can be seen as the length of the list scales, the prof puts a timer in each of the code for all the sorts and merge sort comes out as the "best" sort using a fraction of the time as other sorts for list with long length. The focus of this week has been on the implementation of the merge sort, the prof using cards went through, step by step, each recursive step of a short list and translated it into python code giving the student some idea as to how these efficient sorts are programmed. In the second last week of school, I hope we can go into more details about the complexity of all the sorts and have a precise way in determining the big oh complexity of algorithms.

Complexity

This week a new topic was started, it was a topic which was covered moderately in CSC108 and it is complexity and run-times. Complex is a method of classification of programs based on the amount of steps it takes to complete a program depending on the amount of information that it process. The motivation for this concept is clear, as the complexity of a program is directly related with its performance, thus in order to modify or improve a program to make it more efficient, it is necessary to understand the level of complexity of the code. For example, in assignment one, to execute the recursive code to find the smallest number of moves, the complexity is O(n!),  and in class we were told that some students were able to solve the minimum number of moves for moving 1000 cheeses in a matter of seconds, while it takes me a full minute to find the minimum of 20 moves. Thus, modifying the algorithm that repeatedly runs in a code can greatly improve the performance. But how is the program's performance quantitified? The way to do this is by running time analysis, which puts the running time as a function of the size of the input for a specific program  and it can range for code that are constant for all inputs like appending to list to code that grows logarithmically like a binary search tree. The prof then went on to compare linear search and binary search, and various sorting methods to contrast the amount of time that algorithms of different complexity take to do the same problems. These difference the prof demonstrated in class sparked my interest in learn more about how to implement code with various complexities; it serves as a reminder that I should always keep the concept of efficiency in mind while programming and try to reduce the running time of accomplishing the goal of a function as small as possible.

LinkedList

This week the professor dived further into the concept of linked list, the concept of linked list is not so difficult after studying recursion and trees for around a month now.  The past week is more so a cumulative review of all we learned rather than introducing new concepts. The objective is to create a different class to represent a linked list, which is similar to a tree except each node only has one children in its list. Following the class design steps, first is to figure out some of the inherent properties that the class should have which would be included in the initialization part. Since Linked List is basically a chain, we would want it to have a head and also a tail which we call rest which consists of the rest of the chain. Now with the basic structure figured out we include the desired methods such as prepend, adding a node to the front of the chain, or decapitate, removing a front node. Then the prof went on to define an alternative version of the LinkedList concept remain the same, but we added new methods that are commonly used in a list such as insertion, deletion at a desired index of the LinkedList. These were achieved through recursion as the functions calls on the function itself until it reaches the bases where it reaches the desired LinkedList position and uses prepend or decapitated depending on the method. This carefully analysis of the LinkedLink reinforces my knowledge on object oritented programing and recursion at the same time allowing me to furthermore review the concepts we've learned, and this will definitely help me in completing assignment two which requires similar manipulation of Trees and recursion.

More On Recursion/Trees

The week leading up to the midterm has been focused on a new ADT named Trees. Though we have yet to see any major application of trees other than LinkedList (A tree with arity one), the foundations have been very well laid out. In its essence, Tree in python is a form of data structure that contains numerous data of the same structure that can contain even more pieces of data. An intuitive way to understand this data structure is through its name as observed in nature. A tree has a source where its branches can grow, and on each branches there can either be leaves or more branches and it goes on in this way forming the entirety of the Tree. In programming, the joints in which the branches grow are called "nodes" and the branches that grow from it are the "children" of the node, and the nodes at with no further branches are, naturally, "leaves". Since these Tree contain information that are very much like itself, a very natural way of defining a Tree structure is via recursion. To initialize a Tree, we define it's node with a value, and go on to define it's branches which can either be None by default, or another Tree structure, and eventually reach Trees with value at the node, but no children. A tree's children is represented as a list containing more Trees, the reason for this is, perhaps, for an easy access to each children Tree through the indexing of the list. Here we can see another benefit for recursion being that it is a natural way to define objects with fractal-like property. Not only is recursion used in the initialization of the Tree class, it is used in various method for its properties as well such as arity, height, number of leaves. The implementation to find all of these properties for a tree requires a recursive function until it reaches the bases case, the trees that do not have anymore children.  For example,  to find the number of leaves in the a tree, the easiest way and the cleanest way to do so, is to create a recursive function that goes to the children of children trees until one reaches a Tree without children then add one to the total number of leaves. Also, list comprehension is used in these functions as well to find things such as the sum, minimum and maximum. Overall, it seems that CSC148 is using what we learned in previous weeks cumulatively to introduce us to more complex concepts, in the near future I hope we can see how using the recursive structure of trees can be used to solve practical problems. Thanks for reading.