Week 11 - Sorting and Efficiency

So during this week, sorting and efficiency was discussed and the ways to categorize them. There are many kinds of sorts such as the shellsort, insertion sort, selection sort, bubble sort, quick sort and many others; each producing a sorted list whilst using different and or hybrid methods to sort. And it is this difference in methods that allow for different sorts to have different run time or efficiency.

                Take bubble sort for example, I can say that the big-Oh for this type of sort is n² and this makes sense. Consider a list with 1 million items, the worst case scenario in this case would involve running 999,999 iterations which is approximately x². Bubble sort runs by taking the item in question and comparing it to the value next to it. If it is bigger it shifts the item to the right otherwise, it stays the same and the next value is the new item in question. It runs constantly through all the items in the list in which the list gets shorter by n-1 times. So what is big-Oh? Big-Oh simply indicates the scaling of the algorithm as the size of the list if items increases indefinitely in the worst case scenario. Therefore, big-Oh value of n² means it will take n² times long as the list grows big. In blunt efficiency terms, it’s a terrible sorting algorithm to use for long lists.

                Another more efficient example is the merge sort. In this case, the value of big-Oh is n log(n) and this can be explained by the nature of the sort. Merge sort uses a divide and conquer approach where it breaks the list into 2 constantly, relative to the first item in the list. I.e. the items that are bigger or equal to the first item and the items that are less that the first item. This is run many times until all the smaller broken up list are properly sorted and then the merge begins. The breaking into two separate parts constantly is the reason behind the log(n) and the n comes from figuring out the items that are bigger or smaller than the first item in the list.

                These analysis of worst case run times can be used to identify good sorts but more importantly choose the right sort for the problem in question. For example, although bubble sort has a big-Oh value of n² if the list is very close to being sorted, the best case scenario for bubble sort becomes n. n being much more efficient then n² even though it is the same sorting algorithm.

Week 10 – The Test…

                Well it was test week and I can just say it was terrible. I completely blanked out when it came to the question that involved linked lists. The structure of linked lists in combination with the fact I had to recursively find an answer only made the question even more puzzling during test time. As mentioned before, I detest linked lists and when its use was required during the test, it made me panic half way through the test.

                It wasn't until after the test I look through the notes to see how one makes and uses linked list and after comparing what I remember written on the test, it made me depressed and very frustrated. I don’t quite remember the question specifically, however the major problem I had with the problem was recursively building the list of nodes and returning and maintain the built up list as it moves up the recursive iterations. It turns out I was over thinking the question and that all it was required was a return statement that automatically goes up if it is correct. That is what I call… a major failure. Hopefully, I can learn from this stupid mistake and move on with my life with the final exam.        

Week 9 - Binary Search Trees

So this week was about binary search trees and how to use them to sort data in a useful format. Essentially, binary search trees are a series of nodes each containing a left node and a right node along with a value, root. It is organized by relative size to one another in that all items that is greater than the root goes on the right side of the node in question, and everything that is smaller than the root goes on the left side. It was also learned that the binary search tree is recursive in nature and it makes sense due to the property of the nodes in that it potentially has a left and or right node. Therefore at any given node, it may branch into two “separate” binary tree with all the properties of a binary search tree intact.

I remember doing this back in high school however I realize that we have never touched recursion. Yet alone finding items in a pre-built binary search tree. However, considering that I am aware of how binary search trees work and know it behaves, I’m confident that the only thing I need to work on is the technical aspect of having to manipulate the nodes in Python rather than Java.

Week 8 - Linked Lists

                This week the lectures was about the idea of linked lists and it uses. The idea of linked lists are quite literal in which we can imagine an arrow. It consists of a head and tail in which the tail represents the last list created and or source, compared to the head in which it points to the next potential list in a series of list. This series is called a linked list.

                Linked lists is used to provide an organized way to provide a logical list of variable or collections, meaningful to the programmer. For example consider the addition or subtraction of a polynomial, one might find it useful to separate the terms through linked lists and then use the linked list structure to manipulate the terms to perform the mathematical arithmetic.

                Personally, I don’t find linked lists particularly useful for organizing a series of data. I find using binary trees to be easier and more efficient compared to linked lists. So it is highly unlikely that I will make use of linked lists when programming unless it is absolutely require for an assignment and or problem explicitly calls for the need to implement linked lists.

                

Week 7 - Recursion

Well if I had known earlier that I had to talk about recursion this week, I would have not gone into much detail as I have in week 4 when recursion was being taught. Therefore, this entry in the slog will be quite similar to that of week 4.

                So to the question of what recursion is. Recursion is simply put, a function where it attempts to call upon itself repeatedly to get a final value or solve a problem. This is a powerful and unique technique where by the programmer does not need to write excessive code to bring about a solution to a problem where it would seem it would have numerous outcomes and or iterations as such code will have to be written iteratively. Writing code iteratively to solve a lengthy problem with seemingly unknown number of iterations can be both tedious, difficult, impossible and or potentially inefficient. However, it is not say it is the best solution to everything. There are times where writing iterative code is simply easier to read and write due to not having to trace it through multiple layers of code as it calls itself repeatedly.

                As a rule of thumb, if one knows precisely the number of iterations the code would require to fulfill its purpose, one would write code iteratively. Whereas if the code can have multiple iterations that the programmer cannot foresee depending on the parameters given in a function, one would use a recursive function so that the computer would figure the outcome by itself.

                An example would be the code written to draw a Sierpinski’s Triangle whereby 2 integers will be provided, the number of triangles as well as the number of dots. As one can see, the code can be written iteratively but will be both tedious and long. However, a recursive function exists whereby it not only shortens the code, it allows other programmers to understand the function of the code to draw the triangle depending on whatever the user inputted.

                As for my person opinion on recursive functions, they are quite useful albeit painful to analyze when it requires multiple iterations as I easily can get lost in the code. And the fact that it is easy make a single mistake thereby get a wrong answer at the end. Also my opinion as to when recursive functions should be used is explained above. (Use recursive if one does not know the number of iterations the code must go through to produce a useful output and or purpose. Otherwise write and use iterative code as it is often simpler to analyze and understand.)

Week 6 - Trees

So this week, the subject of interest in lectures this week were data structures and one of the concept of organizing data was through branches and leaves or data trees. Of course data trees doesn't actually involve physical trees, branches nor leaves rather they are nothing more of than an analogy of organizing data through means of true and false statements/ binary comparisons and causing new 'branches' to grow with its own 'leaves'. Methods as to how to form these trees were also discussed, which included post-order, pre-order, in-order traversals where it would lead to the exact same tree at the end however the methodology being different.  Another form of organizing data was through linked lists where we quite literally have a list linked to a new list which is repeated over. In doing so we have a new analogy to work with, tails and heads where it represents the flow of data. For example, the head would indicate the list moving forward whereas the tail would represent the data prior or the origin. As I have said before in the past weeks, this so far is nothing new as I remember this being taught in high school and i distinctly remember analyzing data trees from both school assignments as well as from competitions i have participated in, in the past. However, I'm also aware that data structures was second to last thing that was taught back in high school. I distinctly remember in high school that the last topic covered was working with UIs and and GUI. Oddly enough, I found working with GUI and UIs to be the annoying as well as challenging of course this was all taught in Java and not Python.

Week 5 - Assignment 1 Progress

Well, I decided that it's probably time I spent more time and thought into the assignment this week considering it's due next week. As such, this week's slog will be going over what has been discovered while trying to solve and code the Towers of Hanoi problem. As of now, most of the main components of the program has been solved such as the recursive function responsible for finding the solution to the problem.  The solution to the problem simply involved 2 recursive functions each designed specifically for either a 3 spool or 4 spool game where the function repeatedly calls itself to find the most optimal solution. The conditions are met through a series of if statements which decides where and how a cheese on the selected spool moves based on the relative sizes of the cheese in question. The main difficulty of writing the code however was the fact that the required functions was dependent on the starter program, whereby it took time to read through the starter code to understand what the functions did as well as call. As a result of dissecting the code, I was able to figure out the function calls that was missing and thereby write one up so that the code runs. Unfortunately, it would seem that the GUI will take some time to implement because I have yet to understand how it runs. This will probably be solved by later on as I start drawing conclusions and experiment with the code.