Week 11: Sorting and Efficiency

Throughout this course, CSC148, we have covered three major topics of computer science: the ideas of object oriented programming, recursion, and sorting and efficiency of sorting algorithms. Having already spoken to you, the reader, about the former two topics I will spend this week discussing the latter, and its implications on my learning experiences and what I am going to take away from this course.

Sorting algorithms are used to sort through arrays, or lists in python, in an effort to find out if the object you are searching for is included in said array or not, usually returning a boolean statement of true or false for the result. I can see that the uses for sorting algorithms can extend far past simply looking through a list in hopes of finding some number, but rather its applications into databases, and how the efficiency of sorting algorithms can make a very large difference when searching into a database as large as, for example, serial numbers for all the products in all Costco stores across the world. Such a array in this database and can extend into the trillions of items, if not more, and when inventory needs to be conducted and barcodes are scanned to be cross-references with their place in the database, an efficient sorting algorithm that takes O(logn) will be much faster than a sorting algorithm that takes O(n^2). With many other real world applications the knowledge of algorithm efficiency will be very useful to me, especially when I will learn more effective methods for reducing algorithm run time for average case and worst case scenarios. 

Having already discussed specific sorting algorithms and their efficiency in the previous week, specifically merge sort and quick sort, I will not spend time discussing more as they were both great examples of efficient algorithms that are some of the most used and taught across the world. However I will briefly state that Professor Heap's explanation of the sorting algorithms discussed in class using a deck of cards and going through each step of sorting on the projector really helped cement my understanding of how each sorting algorithm works. As well the readings selected by Professor Heap, specifically the reading "Sorting in Interactive Python" with it's interactive python visualizer of the algorithm code, its step by step visualizations of the sorting algorithms steps, and the informative descriptions provided for each sorting algorithm were also a huge help in my understand.

In conclusion, I am glad that sorting and efficiency were taught so thoroughly in CSC148 and I understand and appreciate their importance and applications for computer science and the real world. 

Until next wee...oh right, this is the last week of the SLOG :'(. Farewell then my fellow SLOGers, TAs and Professor Danny Heap,

Maxim Isakov 

Week 10:Sorting and Big Oh

This week in CSC148 we had assignment 2 part 2 due on Thursday and both lectures in the week kicked off with encouraging words and helpful tips from Professor Heap.

In our readings this week we looked at many sorting algorithms such as, bubble sort, insertion sort, selection sort, etc, their code, their descriptions and what their time complexity was in terms of Big Oh.

During lectures we analyzed 2 specific searching algorithms, quick sort and merge sort.

Quick sort works as a divide and conquer solution, where a pivot is chose, sometimes at random, and then it is place in its correct sorted index with in a list. Then the list is divided into two sub-lists that are lower indices than where the pivot is situated or higher. These subsequent lists are then also quick sorted recursively until more sub-lists are created if need be, and thus eventually all items in a list will be selected as pivots and be sorted into their correct place in the list. The big Oh complexity we found depends on how many times we choose the pivot multiplied by log(n) since we divide the list in half at every step, thus big Oh of quick sort is O(nlogn). Here is a diagram visualizing the process:

The second algorithm we looked at, merge sort, which is also a divide and conquer type of searching algorithm. Merge sort works by dividing lists in half until there are n number of lists of length 1. Then lists in pairs of 2 are compared with each other and sorted into a a larger list from smaller to larger. This process continues until a completely sorted list is completely and thus merge sort is completed. Big oh complexity of merge sort is also O(nlogn) because we divide the list in half until we reach length 1 lists, thus log(n) and then this is multiplied by n because we need to build the list back up in order to complete the sorted list, and this depends on the size of n. Here is a diagram visualizing the process:

This week taught me that algorithm efficiency is truly important for sorting algorithms, especially when the length of the lists move into extremely large numbers. I have also learned that some algorithms behave differently in their average case rather than their worse case and will thus be more suitable for certain situations, while other algorithms will be better for other situations.

Until next week,

Maxim Isakov

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