Pretty nice blog post on sorting and efficiency. Check it out!

CSC148 SLOG at UofT: Assignment Topic Three: Sorting and Efficiency (La...:         The run-times of algorithms in computer science are categorized using different function types (logarithmic, exponential, polynomial...

Week 12: constant-time access and review

Final Post for CSC148H1

It is with a small bit of both sadness and relief that I shall write this final SLOG post for CSC148. I have had a wonderful time in this course, and will look forward with eagerness to moving onto CSC207 this fall. Hopefully, I will see many fellow friends and classmates next semester.

This week's final lecture covered the concept of constant-time access, and reviewed some material covered in past lectures in preparation for the final exam. 

Constant-time access refers to the practice of storing references to elements in consecutive memory addresses such that if the index of a list is known, the element contained at that index could be accessed within constant time. The downside to Python list's constant-access feature is most evident when we start dealing with huge lists that requires descriptive names in order to have a meaningful way to access values associated with those specific memory addresses. 

Be aware...

It is worth noting that when we convert strings, or tuples into integers using hash, we have to be mindful of the potential for collision to occur (i.e. two of the same key refers to two different elements). It should also be noted that the number of bits that could be stored in memory is dependent on the size of the memory itself. Thus, it is not possible to store exponentially large number of bits in memory, which becomes a problem when we deal with very large lists that requires a large number of keys.

Studying for finals
Given that the final exercise for CSC148 is due tomorrow, it seems like at this point, all thats left in terms of course work is to finish up our SLOGS and prepare for finals. I managed to score a pretty good grade on the last term test, but I was quite honestly really surprised to find that the class average for our section was 45%. Hopefully during the CSC148 finals, we won't be dealing with such low averages. This leads to a sort of side question: how are other students in our section studying for the finals? Figured I'd leave this open question on the blog (though I HIGHLY doubt if anyone will be answering it here, I'd really appreciate it if you leave a comment below), and will probably post once more on Piazza. It seems like throughout this entire semester, most CSC148 students interacted with one another via Piazza rather then throughout the slogs. Amazingly, there is not a single comment on any of my posts, despite repeated requests for them. Seems like a lot of people are just not really into the whole idea of a SLOG. Just food for thought.

And finally...

Congratulations to all fellow CSC148 students for surviving the course! I'll be looking forward to seeing you all again next year! Good luck on the finals!

And to end with some humour...

Cheers,

Fellow CSC148 Winter 2014 Student

Image cite:

Final Exams! - News - Bubblews. Digital image. N.p., n.d. Web. 4 Apr. 2014. <http://www.bubblews.com/assets/images/news/1831247139_1362455100.png>

Searching and Sorting Efficiency

Search and sorting:
Searching and sorting are common functionalities often employed in programming. Whether it be looking for the largest integer value in a list, searching for a specific name in a dictionary, or sorting a list in alphabetical order, searching and sorting algorithms are used to find (or sort) the things that we are looking for.

Which searching (and sorting algorithm) should I use?
However, there exists a plethora of differing sorting algorithms, ranging from Bubble Sort, Quick Sort, Merge Sort, and etc., which then leads to another whole host of searching algorithms that work on unsorted lists, sorted lists, and almost-sorted lists. Given this wide ranging availability of different options of searching and sorting a given set of data, how do programmers approach the problem of determining precisely which sorting and searching algorithm to use? The answer: it depends on the context of the problem. However, a simple analysis using the big-Oh notation of a function can tells us important information to determine which searching or sorting algorithm to use within a given problem.

Binary search in action

Example of merge sort

What is big-Oh notation?
Big-Oh notation is commonly used in programming to determine the searching or sorting efficiency of a given algorithm. To be more precise, the big-Oh notation of a function gives us its upper bound on its runtime as the size of its input increases. Sorting algorithms such as bubble sort have a runtime of O(n^2). Merge sort, another sorting algorithm, have a runtime of O(n log n), but uses more memory. Binary search (see image above), which employs a divide and conquer strategy, has a runtime of O(log n). A pure binary search however, will only work on a sorted list. Below is a table that displays the runtime efficiency of various searching and sorting algorithms in big-Oh notation.

On a final note...
When using big-Oh notation, it is important to use meaningful notation in describing the asymptotic runtime behaviour of a function. For example, it is perfectly legitimate to say that merge sort has a runtime of O(n^2). However, this doesn't give us an accurate approximation of the runtime behaviour of merge sort since O(n log n) provides a much tighter bound than O(n^2).

Image Citation:
What Should I Do If My System Isn't Working Properly? Digital image. N.p., n.d. Web. <http://www.sdasecurity.com/wp-content/uploads/2013/04/security-system-error-advice.jpg>.
Electric Engineering and Computer Science. Digital image. N.p., n.d. Web. <http://engineering.vanderbilt.edu/images/dept-slide-show/eecs-slide-4.jpg>.
Binary Search. Digital image. N.p., n.d. Web. <http://en.algoritmy.net/image/id/40163>.