Week 11: Sorting and Effeciency

Week 11

--------------------------------------------------------------------------------------

Sorting and Effeciency

To sort things, is to place the elements from a collection in some kind of order. For example, a list of names could be sorted in ascending or descending order. There exist many sorting algorithms such has bubble sort, selection sort, merge sort, etc. The fact that there are so many different types of algorithms shows how important of a topic this is in computer science. The efficiency of these sorting algorithms depends on the type of sort function used and also the length of the list being sorted.

Here are the Run Times for Quick Sort versus Bubble Sort:

Quick sort works by choosing a pivot value and splits the list based on that value and sorts the list in a divide and conquer fashion. Bubble sort on the other hand, makes multiple passes through a list as it compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place.

Random list generated

FOR 1000 ITEMS:

Time in Seconds

--------------------------------------------------------------------------------

Unsorted List

0.006000995635986328 - quick sort, pivot = L[0]

0.18508195877075195 – bubble sort

Sorted List

0.1340789794921875 - quick sort, pivot = L[0]

0.09106993675231934 – bubble sort

As Shown above, quick sort is much more efficient than bubble sort when it comes to sorting an unsorted list. The efficiency of quick sort can be denoted in big-oh notation as O(nlogn), while bubble sort is O(n^2).

Though quick sort is more efficient than bubble sort when it comes to an unsorted list, it is less efficient using an already sorted list. This makes sense because of the pivot we have chosen for quick sort. In this case, the pivot is L[0]  so the split points are not in the middle and are very skewed to the left, causing uneven division.

Parham Taher

Week 7 Recursion

Week 7

--------------------------------------------------------------------

Recursion

Recursion is pretty much defining something in terms of itself. Many OOP languages such as Python support recursive calls. Recursion can be implemented by creating a function that can call itself in order to accomplish sub problems involving things such as nested lists or fractal trees. Recursion can simplify the solution of a problem, often resulting in shorter, more easily understood source code.

Here is a fractal tree as an example:

Here is an example of nested lists using recursion:

This function will return the total number of non-list elements within nested list L

def recursion_len(L):

    """ (possibly nested list) -> int

    >>> recursion_len([1, 'two', [[], [[3]]]])

    3             

    """

    return len([recursion_len(x) if isinstance(x, list) else x for x in L])

In the above example, if the element of the list is a list itself, then a recursive call will be made, else it will simply produce that element.

To solve a recursive problem involves 3 basic steps:

1.      Try to express the problem as a simpler version of itself

2.      Determine when to stop (stopping cases)

3.      Determine the recursive steps

Recursion is a tricky concept to grasp, but I found it useful to relate the concepts of recursion to the concepts of stacks. Similar to a stack, recursion uses the LIFO (Last In First Out) method. Basically, every call to the recursive method creates a new set of local variables that are made into a stack which then unravel from the top returning values 1 by 1.

Parham Taher

Week 3 Object-Oriented Programming

My Experience with Object-Oriented Programming

Object-Oriented Programming or OOP for short is organized around objects instead of actions. Programmers can create an object by defining the data type, structure and create functions (methods) to use on the data. This can be done using a class in python. OOP is very advantageous since it simplifies the job of the programmer. The objects are like representations of real world objects which are easier to understand. Objects can be reused and modified and subclasses of the objects can also be created. Subclasses use code that has already been written in the main class, which of course reduces the amount of code you have to write.

An Example of a Class:

class Calculator:

    """ Create a new Calculator object which can add two numbers together

        This object has attributes num1 and num2

    """

    def __init__(self, num1, num2): #The method that is called to initialize an object

        self.num1 = num1

        self.num2 = num2

    def add(self): #Method that adds two numbers

        return self.num1 + self.num2

By assigning to a new variable using dot notation creates/modifies the variable inside the object

>>> c = Calculator(1, 2) #The instance variables are 1 and 2

>>> c.num1 = 3 #The instance variable, num1 is 3

>>> c.num2 = 5 #The instance variable, num2 is 5

Throughout the past two weeks however, I have learned a few ways to optimize the above class. The next example will show how "n" numbers can be summed instead of just two, by using list comprehensions.

class Calculator:

    """ Create a new Calculator object which can add n numbers"""

    def __init__(self, numbers: [float, ]): #Initializer method

        #This is the list comprehension

        self.numbers = [float(i) for i in numbers] 

    def add(self): #Method that adds many numbers

        return sum(self.numbers)

Using a for loop, the list comprehension takes in a list of numbers, converts each value into a float and ends up with a list of floats under the variable “numbers”, which can be used later for calculation. As you can see, it is much more efficient than manually assigning a new variable to every number.

In the past, I have worked with Visual Basic and a bit of Java, which are both OOP languages, But have never really got involved with the intricacies of classes which we have covered in the past 2 weeks. I am fairly comfortable using object-oriented programs, but creating my own objects using classes were a bit tricky. I find that the tutorials were actually very helpful in the learning process, since we got hands on experience with the material that was covered. I find that writing the code myself is much more advantageous than just listening in lectures, and by practicing outside of lectures, will help me do better in this course.

Parham Taher