Sorting Algorithms

November 29, 2013

TOPIC(s): Listed Above

Over the course of this semester and past year of learning programming, all sorts of new concepts and ideas were introduced, some not so easily as the others. If there was any particular area I was lacking until now, it was in the analysis of algorithm analysis. Thankfully, with the help of the professor, students, and student posts on Piazza I was able to understand this concept better compared to when I first was introduced to it earlier this year.

Sorting algorithms were one of those areas where in terms of both concept and code I had trouble at first. The types the class took a look into were the ever so familiar selection and insertion sort, and as well as some new one such as merge and quick. Out of the ones which I had most confusion on at first was quick sort, where instead of the usual finding an element in a list and doing various comparisons, the algorithm (much like merge sort) took the list and separated it into three elements, a list before the chosen pivot value, and a list after the pivot. It was taking a look after the code with recursion which helped in clarity of the quick sort.

The merge sort on the other hand I found interesting in terms of concept and the code. In concept the list would continually keep breaking down in half until essentially there is one element in new lists, sort itself, and combine with other nearby lists and do the same sorting. In terms of efficiency, I realized that with all the recursive calls called in Abstract way, in terms of sorting large item lists the efficiency would become relatively slow.

With these in mind, it still awes me to wonder how people could come up with many different ways of searching through and sorting through a list. On top of the learned and new methods in this class, there is also the built-in, which is noticeably the fastest in efficiency out of all the sorting algorithms available.

Week Eleven

Saturday November 23, 2013.

TOPIC(s): [Attributes in Hiding]

This week the class took a turn into more complex features of Python's classes in terms of assigning the initialize attribute statements. Being a relative new programmer before I took the course, I found it understandable why programmers would change variable names in classes, for in order to ensure that the class would function in a certain way the programmer intended it to be. Giving a short example, a unique class of turning a matrix code of numbers into string of words would not particularly involve a float point value. With this topic, the use of exceptions that was introduced earlier in the course broadened, where it was used here in a much stricter environment compared to the traditional "if-else" statements and hierarchy in the "try-except" clauses.

With this topic, I learned various more "properties" and built-ins of Python, such as the property, which takes in methods of a class, and sets the properties of a instance variable name that it is assigned to. So instead of the user calling the methods of the class individually, property takes care of setting the attribute properties in one go, or that is how I thought this built-in takes it. The last interesting feature learned this week was that there are different versions of using recursion. Where instead of calling on the function name directly inside itself, in cases of arbitrary class methods such as __str__ and __eq__, the two items would be compared...

 ex - return one == two
return str(one + two)

within the function body, and recursion is called in this manner.

Week Ten

November 18, 2013

TOPIC(s): [Midterms and Fall Break]

With the last week having been taking two days off and the term test 2 on the day we came back, the past weekend was left to studying the material discussed in the course until now. Here are some general clarifications I have come to realize during the little study period.

Before I had believed that Linked Lists, being initialized as a list in its class definition, was originally a 2 element list with first element being an object, the second being a sequence of nested Linked Lists or an object in its basic case. ex - [2, LinkedList(4)]. But after some more reading it was close, but that Linked Lists were a class consisting of two elements - LinkedLists(4, LinkedLists(3)), where each second element may or may not consist of sequences.

The rest of the material were studied in process of preparing for the midterms.

Week Nine

November 9, 2013.

TOPIC(s): [Sorting Algorithm and Analysis]

This week the class took into a look at the different types of sorting algorithms. Having learned of a couple already such as the bubble, insertion sort my interests waned into the ones I have not been familiar with - the merge and quick sort.

If I were to summarize what the new sorts were, for my own learning purposes, is that merge sort takes a given list and splits each list into consecutive halves until there is essentially one item in the list, and compares which element in list is greater. And in within each sublist the algorithm would sort itself, and continue comparing with other present sublists until finally the entire list is sorted.

Quick sort on the other hand, designates a "pivid" index to sort the list into two parts: elements found to be larger than the pivid, and elements found to be lesser in value from it. And essentially the pivid value would be inserted between the two parts. Using recursion, another rounds of quick sort is run to sort the other two sublists and then we have the final sorted list.

After writing up the code for the assignment due last Tuesday, I have come to better and fully understand recursion, even if it is a bit late. It was hard to visualize in my case, but for no matter how long the function of a recursive function is, or what variable is passes, the recursive would pass over until essentially.

As the week starts to arrive, I pace myself into finding a more and new understanding Binary Trees and Linked Lists and of revisiting myself in the nifty code tricks such as tuple unpacking learned throughout the months for the utmost testing period coming very soon.

Week Eight

November 3, 2013.

Topic(s): [ Binary Search Trees and Algorithm Analysis]

This week the class took a brief look into binary search trees and introduced some mathematical forumulae on algorithm search types and their best and worst case scenarios. Having come from a background with nearly no prior computer programming experience other than basics in coding of HTML in high school, I was as good as lost when I was first introduced to algorithm analysis and the efficiency of running a program.

 Particularly in this course and CSC108, the class is using Python in learning the basis of computer functions, syntax and properties, I had no idea as to what the instructors were talking of during the first intro course. But as learning the basis of this topic on a intuitive level in another course, it helped me clear up my understanding on this topic further as the prof talked over the topic of efficiency. And as a person who is very interested in coding when it comes to her own interests such as HTML, phone OS and even gaming, I learned that this subject is a very practical to put to use in real life. That is one important thing which I have come to understand this week.

My only problem that I am facing is a lingering confusion on one part of the recursion topic which was covered several weeks ago. Over the weeks of practising through the exercises and on other files on my own time, this concept was as good as crystal clear. The only confusion I would have was a lingering thought in the exercise 5 that was given, where for the first part of the exercise we had to use recursion in order to take care of assigning instance variables properly according to what they were passed as a value.

If recursion takes care of anyalsis and forming a return value based on what the function/method/program told it to do, how would recursion, in this case, have taken care of assigning proper variable statements in this case?

For example, if the recursion was called in order to find the root of a tree, through searching the most inner-parts, then how would it take care of things such as:

self.root = Node(x)
self.root.left = Node(x, y)
self.root.left.left = ...
self.root.left.left.right = ...
self.right.left.left.left.root.left = ...

And so on. You catch my drift.
All-in-all, other than these confusions I have come to understanding quite a number of concepts as well. And as I am currently working on figuring out the second part of Assignment 2 due this Tuesday, I hope this will help me to understand more concepts, especially in binary strings and so on.

Peace out!
- [insert diagram here] traingle-angel man [/insert diagram]

Week Seven

October 26, 2013.

With the midterms over, the amount of work has calmed down in a sense. Though the complexity of the homework and exercises only seemed to grow more difficult. This week as we learned of the function helper call in class methods, it helped understand how different parts of the class parameters are called in different ways. If it is anything I had gained a clearer understanding of this week was that class parameters, when already defined, can take additional parameters if they contained recursive properties. For example:

__init__(self, left, right):
to
[inside a function method call]
self.left.node
self.right.right.left.node


This method also gave me a clear understanding of writing certain helper code to certain method calls. In the case of the exercise 5, I found it helpful to define a helper inside set_depth function which recursively accounted for counting all the nodes within a binary tree. That goes without saying that, for this exercise, I had the trouble of figuring out how to recursively assign variable statements if the variables were defined with different names. I realized the idea of this part of the exercise. Here is an example of what I mean.

if X:
return 1 + sum(self.item.set_depth(4))
vs.
if X:
return 1 + sum(self.item.left.left.set_depth(3)...)

If I were to say the most challenging of the exercises so far, it would be this one.

Another key idea I have came to learn this week was tuple unpacking. Understanding that tuple can be seperated by "," it gave me a clearer understanding (and a better method) of how assignment statements would work in a much simpler format.

As the coding of concept gets more complex, I hope to gain a better knowledge of how to properly translate my ideas of solving an algorithm to code.

Cheers!

Week Five

October 13, 2013
----------------------->

Topics: [Recursion and Trees]

When I saw the diagram of the trees in the slides as I walked into the lecture room, I was just itching for a smile. Doing a double major of Computer Science and Linguistics, I was well aware of the notion of the hierarchical tree and the concept of nodes and paths (or "branches" as we linguistics say), though in a more grammatical concept. While in CS I learned this week that there are the three different traversal types - pre-order, in-order, and post-order, the material was review in terms of being introduced to the tree structure. So when the directions of the trees were being shown on the slides I was able to follow them pretty easily. Left subtree, root, right; Left subtree, right, node, etc.

The only lingering questions which I thought was that how would recursion work in this way necessarily? For I was under the impression that recursion called inside functions were used in order to create a wanted value or outcome for an inner part of the given parameter. In terms of the given tree of numbered nodes, would the recursion be the repeated two's, in this case?

Other Notes:

This week I would say I came to better understood recursion through the labs that were required to write recursive functions. Recursive functions need a base case, and they generally need to pass an argument of a parameter that is not the full "object" itself. Otherwise, a maximum recursive depth error would occur.

ex. reverse_string(s: str).
......
    return reverse_string(s)     
vs.     
   for n in s:
         return reverse_string(n) + ....

And another note is pertaining to the "one line" return statements. Punctuation of return statements are key - [] would return the code, whereas () would cause the code to generate a "generator object"

File "C:\Program Files (x86)\Wing IDE 101 4.1\src\debug\tserver\_sandbox.py", line ?, in __main__.reverse_string
Failed example:
    reverse_string('clock')
Expected:
    'kcolc'
Got:
    <generator object <genexpr> at 0x000000000310F870>

In terms of recursion concept, I think I have it fully grasped. All that is left is making sure I am able to properly put the concept into coding usage :3