Sorting, What is it? Why is it Important?

Whether it be a list of numbers that need to be sorted in order from largest to biggest, or a list of names to be organized alphabetically large database systems need to sort through lots of user input into an organized matter. Just as when organizing books in a library by subject, fiction non fiction, there are systems put in place to do so to the best efficiency, in order to get those books put away or sorted into their rightful place. Lets begin with naming different python sorting, lets use this list: 

[1,  34,  5,  6,  43,  2]
1) The Bubble Sort 

Bubble sort passes through the whole list, and switches items which are out of order, the first pass will result in the largest number being at the end of the list.

The list will look like this: 

[1,  5,  6,  34,  2,  43]

the runtime is O(n^2), the best case scenario everything is sorted, worst case everything will be exchanges 

2)Selection Sort 

Is an improvement of bubble sort as it only makes on exchange for each pass. Goes through the list, finds the largest integer and exchanges it with the last item 

in the list above after one pass the list will then be: 

[1, 34,  5,  6,  2,  43]

Selection sort makes just as many comparisons making it still O(n^2), however since there are less exchanges happening it usually will execute faster than bubble sort 

3) Insertion Sort 

It has a sublist that gradually gets larger and larger through each pass so, there will be a list of length one, where it is the smallest number. 

-Then there will be another item added from the original list, compared to figure where the next item should be located in the list, this continues until a final list that is sorted is returned. 

Still using O(n^2) 

4) Shell Sort 

Shell Sort is an improvement to insertion sort as it makes smaller sublists with an increment of i. Thos sublists are sorted through then after the increment decreases until reaching the increment of 1, Thus returning a fully sorted list. The runtime could fall between O(n) - O(n^2), it depends on the i. Which gives a little more control on how efficient the code could sort through a list of n size.

5) Merge Sort 

Significantly more efficient, it divides and conquers the list. Just as you might have to divide different tasks to a team of employees in order to get the job done the quickest.

It runs recursively, and continues to split the list in half until the base case of one item, then calls merge to sort through the two halves until the final list is returned. 

runs on O(nlogn) 

6) Quick Sort 

Takes the advantages of Merge sort without using the memory space, which could be in some cases an advantage, however could turn out not to work effectively in all cases. 

There is a pivot value usually the first item, who's main role is to split the list. This value is usually the split of the list. 

Then the left point and right point which are the items at the beginning of the list following the pivot value(if it is the first item), and the right being the the end of the list. 

The are then incremented(left) and decremented(right) until the left value is greater than the pivot, and the right is less then the pivot. Once these are found they are swapped this is repeated until the final list is sorted. In the best case, where the pivot point is chosen correctly, it will result in nlogn, however if there is uneven division, it could leave a runtime of O(n^2)  

Week 7: Recursion, how we love thee.

Week 7: recursion 

Recursion is hard to completely understand mainly because when programming recursively, you need to understand exactly what your program needs to originally do then call it within itself. Also you need to ensure your program won’t run an infinite amount of times, making the depth of recursion to large, and it not working at all. 

How I have been programing before took special cases in if statements however in recursion, one way to adapt from previous knowledge is by using the idea of these ‘special cases in if statements or possibly in while loops, but making them into a base case from your initial function then calling those base cases recursively in regards to your arguments. 

This is best explained by an example: 

the Fibonacci sequence of numbers can be expressed recursively as so: 

def fib(n: num)-> int: 

if n == 1: 

return 0          (THESE ARE YOUR BASE CASES) 

if n == 2: 

return 1 

# now you have two initial numbers and for all other cases you will want to get the fib sequence for n minus your base case values for n 

return fib(n - 2) + fib(n - 1) 

looking at this code you may wonder how does this work?

fib(3) 

will process it from the return statement then call then call what the values of 

fib(3 - 2) + fib(3 - 1) 

fib(1) + fib(2) 

0 + 1 

1 will be returned 

now fib(3) == 1 

say you want to call fib(4) 

fib(4-2) + fib(4-1) 

fib(2) + fib(3)  ------> (fib 3 is then called recursively giving the second value of 1)

1 + 1 

the return int will be 2 

say you want to call fib(5) 

fib(5 - 2) + fib(5 - 1)   

fib(3) + fib(4)   ------>   (value fib(3) and fib(4) are already within your program)

1 + 2 

the return int will be 3 

and so on, recursive works well as the function is actually recursively keeping track of each value needed instead of you programing the fib sequence and giving it the value. Essentially being the best approach to program the Fibonacci sequence 

This is a simple example, however once having an idea of approaching it as: 

1. make a base case of what you want to be accomplished with your program
2. then if a special case is called you will call the function once again 

Week 5: Scope, namespace...WHAT?!

In lecture this week we began with a simple trace of recursion, 

How I see it is simply, first you have a simple list, that finds the largest number. But what if you have a nested list. This case is simple, similarly you call the same function again through the nested lists, than find the max between the nested and non-nested lists. The examples given in the slides were straight forward and allows one to see how recursive calls could find the max number easily. Just as any day was a nice way to fully understand recursion, and how we can trace a code ourselves. 

Interesting enough we moved on to have a deeper understanding of scopes and namespaces. Namespaces are defined as the mapping of names to objects. Some examples of that could be the global names in a module, for example: If you have a module named GetStudent.py. Then have a class within that called Student(): or you have local names such as a method named add() 

The important thing I understand from a namespace is between module to module you can have the same name to a method in both, in order to differ between the two you must call with the prefix of the module or class, ex: GetStudent.add(). 

In addition to namespace, there are scopes. What the namespace is declared to be and the scope in which they can be found or called without having to assign where the function is. 

for example, a function named 

there is a local name of a function: add_numbers()  which is the inner-most 

--i  see this as the function that is in the program you are working with. 

then there could be a function which is called with the module name, so there is a module named mathematics, the outermost scope is mathematics.add_numbers() 

-- at this point it could be in, or out of the module, but it will search the module then find the local name of the function for execution. 

then the last place to search for this function name would be in the builtin namespaces. 

for example: max() 

--after not finding the name anywhere in your own namespaces, lets look through global namespaces. 

Week 4: blog post

Started the week off with a bang in tutorial!  Out of the labs so far, this one really helped me use what I have read and learnt about in lecture and apply it to hands on programming. I had walked into lab believing I have a full understanding of inheritance, but while working with my partner and TA I had learnt that I was approaching programming tasks incorrectly, for instance, when initializing the Motorized class we had included current_pos within the arguments, but the current pos will never be given by the user, it will always start at (0.0, 0.0) then the program will adjust it with the new position. Failure to draw out a program and understand what it is expected to become has hurt me in the past so I am training myself to first plan and draw out what is expected then start creating the program on the computer.

UNITTEST, so I'll be honest, and I hope all of you are as well. I totally forgot about unittest or that it was something of importance in our crazy student lives. I knew the name happened somewhere in my life as a CS student but it's significance or operations did not jog any memory, I knew it was a built in testing method in python. Overall the technicalities are not what I wanted to talk about because I think once we read what the expectations of a unittest were and how to implement it in your program it was pretty straight forward. What unittest has taught me this week which I had never taken into consideration in 108 was building a program, testing that program etc. Obviously with the assignments from last semester we did create a final product but I feel as if 148 is helping us build something of our own to a certain extent.

Lecture was great! Dustin really gave us interesting examples of how recursion is helpful in programming and gave examples of how it worked, I feel like I have an overall understanding of the topic.

In conclusion this week has really helped my understanding of the course, I felt pretty lost in the first three weeks. Even after completing the readings and going to lecture, there wasn't a connection or lasting understanding of the material. I'm excited for this week see you all in class, tutorial or in the lab working on a1! 

MUCH LOVE! :) 

Week Three, brings me glee!

    Realizing we are no longer on break has made is easy to fall behind. However this course hasn't been extremely overwhelming but has introduced newer concepts that I have touched upon but haven't done much work with. Some of these concepts this week can be transferred into real life thinking. Such as inheritance, just as we inherit genes from our parents, a child class inherits initial arguments from the parent class. A simple realation that helps me undertand aspects in object oriented programing.
    My computer science week begins with tutorial, which is my favorite part of any computer science course. Instead of being shown how to do things, I like to figure it out or apply it. I think thats why a majority of us are in the program.  What I find a little more difficult in the is following the lectures, a majority of it is simply reiterating what we read the night or two before, similar to every other course I'm in. It is possible that the attempt to get more involvement is there, but the students such as myself aren't participating, maybe because of an intimidation factor. Overall object oriented programming in this term is takes time to get used to, but interesting because instead of manipulating these databases we are keeping track of values in the objects. For those of us that took 108 last semester I'm enjoying the excersizes much more, I just wish there were some more hands on, hand writing code assignments as our final exam should be handwritten.

Thanks for reading, have a good week 4!