Week 9: Binary Search Trees and Time Complexity

This week in lecture we focused on algorithm efficiency and one of the notations used to quantify it, Big Oh. Big Oh notation is used to describe how efficient an algorithm by saying how fast it will run in the worst case scenario for an n-sized list.

One of the examples given to use to analyze Big Oh efficiency was a binary search tree, in which you can divide the tree into 2 parts because if the object you are looking for is bigger than the root, then it will be on the right side of the root, and if it is less that the root, then it will be on the left side. So for an average tree the big Oh would be O(logn) because it keeps dividing the list in half every time it searches, however in a worst case scenario the BST can be very poorly designed and have a very long chain of nodes with only one child, therefore the worst case efficiency would be O(n) because the complexity increases linearly for every item added to the list.

Algorithm performance is very important for computer scientists and programs because bad time complexities may overload a computer's processing capabilities, or simply have a function take very long to complete such as 10 minutes, then if a less complex algorithm were used to make a function complete in less than 1 second.

In many cases where the time complexity equation of a function as it depends on n such as: 7n^2 + 2n + 5, only the largest power of n will be considered for time complexity because if n is in the billions 7n^2 will be much larger than 2n or 5, therefore on 7n^2 is considered and the time complexity is O(n^2).

A binary search tree is an example of how creating certain conditions can optimize time complexity of searching through trees, as regular trees have random placement of nodes so the time complexity rises linearly but BSTs divide the list into 2 halves so that the time complexity rises logarithmically.

With my prior experience of Big Oh notation and time complexity from taking CSC165 last semester it was easy for me to understand the concepts discussed in class this week, especially since I was writing proofs for time complexity just a few months ago.

Until Next Week,
Maxim Isakov

Week 8: Linked Structures

This week in class was a continuation of last weeks topic, linked structures, which are inherently recursive structures. To study the concept we looked at linked lists which are data structures which
are made up of nodes, with each node having a value and a reference to the next object in the sequences.

For the linked list nodes we designed a wrapper class that can keep track of certain attributes of the linked list, such as size and the object at the very front, without making the user initialize them when creating the object. We wrote the bodies of functions that insert, delete, and reverse linked lists, all using recursion and the wrapper class attributes of size and front object to create base cases for the recursion.

We then looked at binary search trees (BST), another recursive data structure, which resembles tree data structures but a pre-condition of all BSTs is that the left child of the root is smaller than the root and the right child is larger than the root. We looked at how class methods can be made easier by creating helper functions indented within the methods that will do most of the functions job, and then a simple return statement can be called on the helper function with certain parameters changed, as seen in the insert method of BSTNode.

I was very content with this week's material because I felt I had a good understanding of the recursive nature of linked structures and binary search trees to the point of me having very little trouble creating methods regarding manipulating these data structures.

Until Next Week,
Maxim Isakov

Week 7: Recursion

After dealing with recursion for most of the term  and implementing it in our first assignment I've come to appreciate the usefulness of recursion in solving certain problems and how well it simplifies other problems that can be solves without recursion. The basic concept of recursion is that it takes a problem such as counting the depth of a tree, establishes a base case (a tree with one root and two nodes) to be run when the function is executed and if the nodes also have nodes (the depth of the tree is longer than 2) then the function is run but this time with the nodes as roots in the input of the function. Thus the function continually runs the function over and over again with different input until it reaches the end of the the tree, probably returning an accumulator than was counting each time the function was executed recursively, indicating that another depth level was accessed. Recursion proved to be the most effective way to solve the problem presented to use in assignment 1, figuring out a solution that did not involved recursion proved impossible to me, and now I can look at problems and feel an intuition on whether to use recursion to solve it or not.

Due to me being overloaded with midterms and assignments this week I was not able to attend the lecture or review the lecture slides so I cannot offer any input on what was presented in class unfortunately.

Until next week,
Maxim Isakov

Week 6: Recursive Structures

This week the topic of lectures was all about trees. Trees are a data structure in python that work recursively when going through them. Their structure is very much like trees in real life, except upside down, as they have a root that has leaves or nodes sprouting from it who themselves can be roots that can leaves, and this can continue infinitely. With this visualization of trees I saw the inherent recursive structure to trees, as to implement any actions on trees you needed create a base case for a simple tree with one root and leaves and then implement that function recursively for leaves that are roots themselves. We looked at some examples of functions that traversed trees, such as three ordering functions that order the values of each node in the tree in preorder, inorder, or postorder, and all three of these functions worked just as I suspected, recursively.

I did not spend too much time analyzing class materials this week as the first assignment was due on Thursday and while I got caught up trying to finish assignments for other classes I was able to do most of Assignment 1 with my partner, not having enough time to implement an algorithm for a four stools Tower of Hanoi game, but we did implement it on our time later in the week for practice.

Until next week,
Maxim Isakov

Week 5: Stools, Names, and Tracing

To start the week off Prof. Heap helped us out on Assignment 1 by going over the recursive elements of the Towers of Hanoi exercise which involves moving a stack of cheeses from on stool to another, without ever placing a larger cheese on top of a smaller cheese. It was not difficult to understand as the function to perform this have an if and else statement where if the size of the stack of cheese was 1 it would simply move the cheese to the targeted stool, and if it the stack was larger than 1 it would employ the function recursively on the the top cheese and subsequent cheeses under it, by implementing the function with different parameters entered to fulfill an algorithm to reduce the amount of moves used to move all the cheeses. This was used for a Tower of Hanoi problem with 3 stools which is simple when compared to one with 4 stools, which is the type of problem we are supposed to address in Assignment 1, so this was used to help us get a good understanding of recursion for the Tower of Hanoi but in no way did he solve the problem for us.

Next we covered names and namespaces in class, more specifically which order Python looks for them when executing. First and foremost Python looks at the innermost local scope, which is usually in the function body. If you assign a value to a name within a function that has another function within it that changes the values and you run the parent function, python will not change the value of the name because the original value is the local value. If you use the nonlocal statement before assigning a new value in a child function and then run the parent function it will change the value of the name to the one stated after the nonlocal statement as it creates a new local statement within that function. After local and nonlocal names are evaluated global names are evaluated. Even if you use the global statement within a child function like you did with the nonlocal statement it wont change the value of the name until you finish running the parent function as it creates a global or modular name change outside the function. Last but not least built in names that python initializes when a python interpreter is run, such as the isalpha function, and these names are looked for last by python.

Last, we were offered tips on tracing through recursive functions and their doctest examples. We were told to trace the easiest of the doctests and then plug in know results into the next most complex case, and repeat until done. I however prefer to just use the python visualizer provided to us in the software page of the CSC148 homepage as it takes you through every step of the function's execution.

Other than the class work I got started on Assignment 1 this week and am hoping on slowly progressing through it until it is done.

Until next week,
Maxim Isakov