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.

Week 4 - Recursion

So this week was all about recursion and understand how to both code and analyze recursive functions. The idea behind a recursive functions is easy however analyzing recursive function can easily get complicated; often requiring multiple iterations where its easy to make mistakes.I have done this before in high school so the concept of recursive functions is not new to me however, I know that these functions can get really complicated and often back-tracing can be hard. The way I imagine recursive functions is a series of nested while loops. Where the code constantly calls its self repeatedly to get a desired number or value of some sort. As you get your value, you feed it back up the x number of loops or iterations of your code to get your final answer. This code can be used for things such as permutations, where writing a code that runs a finite time can be tedious and or impossible. One of the examples I've learned from high-school is the Sierpinski's Triangle where you draw x numbers of triangles within a larger triangle with y number of dots. As one can see, a writing a finite code can get complicated  whereas a recursion code simplifies it. Anyhow, as of this point of the course, I don't think I'm lost or learning something completely new as of yet although practicing back tracing as well as writing code can be helpful in avoiding errors.

Object Oriented Programming

Well this week, we talked about object oriented programming or OOP and I guess it’s best if I described what OOP is. OOP is simply a model or a way of approaching problems by making distinct objects which pertain specific attributes the programmer wants to manipulate and or keep track of. In doing so, one can essentially create many object to manipulate around in order to perform a desired, useful function. For example if one would like to manipulate fractions, one might make a new object called Fractions with instance variables that represents the numerator, the denominator and perhaps an integer for mixed fractions. Creating a constructor class will allow the programmer to reuse and recycle the code many times to create many objects of type fractions to manipulate around.

As an avid gamer, one can appreciate OOP when knowing virtually everything in video games can be represented as an object. This includes the variety of units, terrain, environment and others. Another reason why OOP is useful is error correction and or making something easier to modify later on. By simply changing the constructor class of the object, one can change the properties of the same object called throughout the whole program, which makes errors easier to solve.

As for the concepts and techniques learnt so far about OOP, it’s nothing really new compared to high school other than the fact that I’m learning it in Python for the first time. My first programming experience came from Java and as such I’m constantly analyzing the similarities and differences between the two languages. Especially when it comes to the topic of hierarchy and inheritance, being able to understand certain things due to having experience coding in Java is quite helpful knowing how this topic was quite confusing when I first learnt it back in high school. Although I can tell that the pace of this course is very fast compared to high school and it will only be a mater of time before it goes beyond what was taught in high school.