Week 11 - Sorting and Efficiency

There are various sorting algorithm such as Bubble sort, Insertion sort, Selection sort, Quick sort, and Merge sort. Each of the algorithms have your on particular cases to apply in different problems, and diverge in performance during the time (depending in the size of the data structure). In this post, I going to describe the Quick sort and Merge sort. The Quick sort algorithm consists in elect a pivo, then compare the rest of the n elements, and if the n element in bigger then pivo, you keep the element in the place. When the algorithms complete to run, the elements before the pivo are smaller than itself, and the rest elements are bigger than the pivo. The running time of the algorithm is O(n log n), but it depend in the choose of the pivo. In the worst case the Quick sort can run in O(n^2). Also, the Quick sort uses the behavior of “divide and conquer” in problems. The Merge sort algorithm consists in divide the problem in two halfs until you reach sizes of one. When you reach this condition you star return and compare the two halfs sorted, so in the end you will have the n elements in the data structure stored. The runing time of the algorithm is O(n log n) in the worst case and the best caso, so it is a stable algorithm. There are some situations where the Merge sort is indicate such as sort linked lists or random acess (Quick sort) is much more expensive than sequential access.

The Quick sort can be more efficient if the pivo, expecially the first, randomly choose the pivo and half of the list. In this particular case, the quick sort is faster than Merge sort. In case that choose a difficult pivo, it will increase the runtime. Instead of Quick sort, the Merge sort always aplly the same method to slip the list until reach one size, then start to compare, so with time it will always be proportional between the runtime and the size of data structure.

Week 7 - Recursion

Recursion happens in programming when the function  itself  at least once. So, a recursive function call itself until they find the base case( the value that function knows the result) and then start to close the recursive call until return something meaningful. If a function do not have at least one base, it will generate a infinitive loop, then the program will crash. So, when programmers are creating the structure of a function, they need to be aware of the advantages and consequences of using recursion.  One pro is to reduce the code. When programmers write a recursive function, they compact their code, and make it clearly . Another advantages is there are some data structure, such as binary tree or tree that use the recursion in their own concept, so to design the methods to deals with this data structure, for example, find a node in an binary tree. There are, however, some consequences, one of them is to allocate more memory to trace the code. This happens because the recursive function need to call itself until they get into the step that they know the result. Another consequence is many cases, the recursion can take more time to process than a iterative function. There are some program which takes the recursion as a solution, for example, the sum of a list, or the Fibonacci sequence, the binary search. The conclusion of recursion is that every case the programmers must decide which method is better to apply, in many cases, the best solution is recursion.

Week 6 - Tree

The topic of this week was "Trees", which is a data structure used to store data. Every 'Tree' has a root, and at least one child. In the lectures, we developed, using recursion, the pre order, in onder and pos order. I saw 'Three' in my university in Brazil, but I think I understood better with the explanation  on the lecture.

Week 3: Object-Oriented Programming

OOP ( Object-Oriented Programming)

The OOP ( Object-Oriented Programming) is a model language programming, which is structured by creating classes to abstract something that exists in the real world. So, the classes makes possible to create a customized type of data, and this can be used to create a new 'Object' which has the type of the data (class) allocate in the heap. Each class has their own methods (functions that add the class's behaviors) and attributes (variables that store information which the class need to work properly). Another benefit of OOP is making the concept of recicle code. In the past, the structured programming was used to create softwares, but this model had the main problem which was the maintenance of code. When some function get some bug, the programmer had to change in every single line that used the bugged function. Then, the OOP came and makes the code more clear and easier to fix because the class bugged is the most cases in one single file, so the programmer just need to access the file and make the appropriate updates. Also, the class makes the program shorter because the developers can create as many instances of the determinate class as they want. The inheritance is another feature of OOP. The concept of inheritance determinate that you have a superclass, which is a general class, and their subclasses. The subclasses inherit all the methods and attributes of his father (superclass), and they can implements new methods and attributes to make the subclass more specific. If is necessary, the developer can overwritten in the subclass the methods that superclass implements.

Since I have already studied OOP in my hometown university in Brazil, I used a simple examples to easily linked the concepts of OOP with real life. The developer wants to create a class called 'Animal', in these class, and he/she want to add characteristics and the common behaviour or actions of animals. So, the first step to create a class is to define what is method and attributes. In this particular case, if we think all the physical characteristics such as eyes, color, age, and weight are attributes of the class 'Animal'. The common behaviour or actions such as move, feed, and sleep  are the methods of 'Animal'.  Inside the class 'Animal', if the programmer want to call one method inside the other method or use an attribute, in Python, he/she need to use the reserved word 'self' which identify that is bellow of the class. For example, if we want to call the helper method 'bite' inside of method 'feed', the line has to be similar with ' self.bite()', in our examples, we can read the same line as 'Animal.bite()' because the 'self' is used to replace the class's name. After you define all the methods and attributes, it is possible to create an object of the class 'Animal'. Because of 'Animal' it is too general class, we want to create two subclasses called 'Lion' and 'Bird'. In these situation, we use inheritance because we want the attributes and method of 'Animal', but at the same time each animal has particular attributes and methods, so we create a class with line ' class Lion (Animal) '. For checking if the relationship is correct, the question 'is a'  must be true to 'subclass is a superclass', in our example, 'Lion is an animal' make sense, but if we say 'Animal is a Lion' this statement does not make sense. In some cases, you need to overwrite the method of superclass, because the subclass have the same action (method), but the behaviour is completely different. If we think in the method 'feed'  both lion and bird feed, but the birds, unusual of the rest of animals, 'peck' instead of 'bite' their food. In order to solve the problem, the programmer must overwrite the method  of 'Animal.eat()' inside of the subclass 'Bird'. That was a simple example that I create in my brain to understand better the lectures that professor Heap is given to us and describe what I have been learning in the CSC 148.