This week's classes focused on memory models, tracing , looked at fibonacci sequence and how it is implemented (how it can be) in Python and the consequences of recursion. The idea of memory models (which prior to taking the course was just a cool word in my opinion) is quite interesting. It's fairly basic, with variables referring to objects and different instances. I was very ill and so couldn't attend the test and so decided to instead read up on everything that I had difficulties with.
I found out that picturing a memory model in your head seems like a great way to solve a problem involving Binary Search Trees. While working on BST examples in Labs, my teammate and I mainly drew up what the results would be and it really helped figuring out the final answer.
It has been a very busy semester and I really need to do great in my final exam. I am not as fond of Python as others but see the need to get better at it and I think this is my last chance.
For this week's SLOG, Danny asked (in addition to our normal entry) to write about sorting algorithms:
Sorting has also been mentioned constantly in class and even Obama has a popular video online in which he describes Bubble sort as the least efficient way to sort a million 32-bit integers (Link to Obama video). It turns out a lot of different ways of sorting have been established over the years, each with pros and cons.
Selection Sort: Works by partitioning the list in two with the front part being sorted and the back part containing values that have yet to be sorted. It takes a long time as it needs to go through each element finding the next smallest item in the unsorted section and placing it at the end of the sorted section.
Quick Sort: Much more of a 'divide and conquer' sorting algorithm, the quick sort operates by first dividing a large list into two smaller sub-lists (low elements and high elements) and then recursion is used to sort the sub-lists. It is as its name states it a faster sorting algorithm, way more efficient and faster than the selection or bubble sort (for a long list of integers/items). Hackerrank.com had a great image helping the visualization of the QuickSort algorithm.
Merge Sort: Merge Sort, like Quick Sorting algorithms, is a comparison-based sorting algorithm which follows the same 'divide and conquer' pattern. It divides the list into n sublists with each containing 1 element. Then the algorithm proceeds to repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist left which will be the sorted list. Like the previous sorting algorithms, I prefer to look at a visualization of the sorting instead of just reading about it if I want to learn what it exactly does. The CS department of the University of Alberta has a great visualization in which you can clearly see the original list getting decomposed into multiple ones until it ends up sorted.
Efficiency: Used to describe how the properties of the algorithm that was written relate to the amount of resources used by the said algorithm. The normal way to estimate the complexity of an algorithm (via analysis) is using Big O notation. Big O notation represents the complexity of an algorithm as a function of the size of the input n. So efficiency is what compares different algorithms and 'ranks' them in order of best sorting algorithm or worst sorting algorithm depending on the cases. There are quite a few examples of Big O notation. such as:
O(logn) - eg. finding an item in a sorted array with a binary search or a balanced search tree.
O(n) - linear - finding an item in an unsorted list/array.
O(nlogn)- Heapsort, quicksort, mergesort, etc.
O(n^2)- quadratic - Multiplying two n-digit numbers by a simple algorithm, bubblesort, shell sort, quicksort, selection sort, insertion sort, etc.
Interesting SLOG of the week:
http://compsci148life.blogspot.ca/
Not a lot of blogs but I really liked his definitions for his/her sorting algorithms. They were precise (even though they were quite long) and I felt covered the whole spectrum in terms of defining precisely what the different sorting algorithms were about.
No comments:
Post a Comment