CS50 — Week 3 (Algorithms):
Week 3 of CS50 covered algorithms. More specifically, it looked at the running time of algorithms and how the program could be more effective and efficient. Using an example of searching for a name in a phonebook using different types of sorting methods, the lecture introduced the notion of upper and lower bounds for the running time of the program.
The upper bound (represented by a big ‘O’) is the worst case scenario — how much time/many steps maximally?
On the other hand, the lower bound (represented by the omega notation ‘𝛺’) is the best case scenario — how much time/many steps minimally?
Using the example of searching through a phonebook, I will now explain the different types of searching. The types include: linear, binary, selection, bubble and merge.
Linear search is going through the phonebook one page at a time and is obviously very time consuming.
Binary search is opening the phonebook halfway and determining which half is required and continuing this process. This is a logarithmic process but a downside is that the data needs to be sorted prior to searching.
Selection search iterates through the unsorted portions of a list, selecting the smallest element each time and moving it to its correct location.
Bubble sort isolates a small number of data sets within a larger array and sorts it there e.g. two numbers and sorting left for lower and right for higher repeatedly. Bubble sort compares pairs of adjacent values one at a time and swaps them if they are in the incorrect order. This continues until the list is sorted.
Merge sort sorts half of the array then sorts the other. It then merges the two halves together. Merge sort recursively divides the list into two repeatedly and then merges the smaller lists back into a larger one in the correct order.
The lab for Week 3 was to run a program using the different types of searching and identify which type of search was used based on the time it took to complete the task.
The problem sets for Week 3 revolved around elections. Plurality (also known as first past the post) takes a single vote from a chosen number of voters and tallies up which candidate got the most votes and by extension are the winner of the vote. In the event of a tie, joint-top candidate names are all printed.
Runoff elections are another form of election which combats disadvantages of plurality elections. Runoff, on the other hand, takes three votes from each voter based on preference and can continue to be somewhat happy with the result if their second favourite is voted in rather than their least favourite. If voter 1’s top choice is eliminated through being the least popular, then their second choice will then be taken into account and so on.
Runoff was a difficult problem set as it was no simple feat to work out how to eliminate a candidate and then take the next vote into account. It took me a few days of trial and error and approaching the problem from different ways but I eventually solved it and the solution can be seen below.
Week 3 was definitely the hardest week of the course so far. Having read about the problem set (Tideman) for the more comfortable students and recognising how I’d struggled with Runoff, I made the decision to save Tideman for a later date when I’m more confident in my programming ability.
Thank you for reading!
