CS50 Lecture 3 Algorithms
This lecture is all about algorithms. David started lecture with a flashback. In Week 0 David make an introduction to algorithms with an example of searching a name on a phonebook. And in this lecture he continue to explain algotihms with ne same example.
Algorithm, is sequencial instructions to solve a problem. According to this explanation it is obvious that there could be a several way to solve a problem. Also, David show 3 different way to solve the problem of find a name on a phonebook problem. First approach is look every single page to find the name. Second approach is look every second page (this is also dangerous way as you may miss the name during search). Third approach is open the middle page of the phonebook and check first letter and compare the one that you are looking. If the letter is alphabetically bigger that yours, check first half of the book, if the letter is alphabetically smaller that yours check second half of the book (This algorithm is also called Binary Search).
As there is more than one way to solve a problem we need an indicator to compare these ways during coding. And this indicator is called Big-O in computer science. David compare these three algorithms according to Big-O Notation.
Lecture continue with explaining different algorithms. David explained Linear Search in which you check every element one by one until you find yours. And the other algorithm is Binary Search, in which you need a sorted array to implement.
Later, David explain struct data type. This a bit out of content. The reason the David explain this in case we would like to implement a phone book we need some datas like name, phone, etc. to refer a single person. If we use different arrays to store these data it is possible to make errors, during implementation. So can use structs, which is a custom data type that we can add different features like; name, number, address, etc.
At last, David talks about Sorting algorithms. He describe Selection Sort, Bubble Sort and Merge Sort.
In Selection Sort, first we look for the smallest element on the array then swap this element with the first element of the array. Then we continue to do this for the second and other elements. Once we reach the last last element we have sorted the array.
In Bubble Sort, we started to compare two elements with starting from the begining. We put the smallest element to the left and the biggest to the right. Every step we just compare only two elements. We continue to do this until there is no swap between elements.
In Merge Sort, we use recursive coding. Which is also explained by David before Merge Sort. First we divide our array to smallest until we have only one element in one array. Then we start to merge these arrays with comparing. And in the step before end we have two sorted arrays. Again we merge these two arrays by comparing every element from first element to last.
Let’s Solve The Problem Set
Okay this one is though but very instructive also. All problems are about election system. Actually, we are going to implement 3 different algorithms for finding the winner of an election.
First one is the simplest, Plurality algorithm. All you have to do is getting input from user (a.k.a. voter) then find the candidate that took the most vote and announce it as the winner. The tricky part is if there is a tie between the candidate, your code should announce every candidate as winner. That why we need another algorithm which takes us to second problem.
Second problem is Runoff Algorithm. As mentioned above, we need this algorithm to solve tie situation in an election. We have a starter code, and we need to use terminal (I love to use terminals :) )to download starter code. Once we open the starter code, David (or I don’t know who) prepared most of the code for us. We need to complete the functions with comment “TODO”. In Runoff algorithm we ask user to write every candidates names on the balot according to their preferences (rank). Then we will check the first preferences to find the winner. In case, a candidate has the votes more than half of the voter. We announce that candidate as the winner. Otherwise, we need to do some trick things.
First we need to find the candidates that has the minimum number of votes. Then we eliminate these candidates. Then we will find the voter that vote these candidate as their first preference and check the candidate on second preference from their ballot. Then we add votes to these candidates. Again we count the votes to check if any candidate has more than half of the votes. We continue this algorithm to find the winner. I suggest you to watch walkthrough video for this problem. It is so instructive.
The last problem is Tideman algorithm. This is also tough problem. In general this algorithm finds pairs according to preferences. And after it complete to find pairs, it will create another array that includes pairs without creating a cycle (which means an infinite loop). The output of this algorithm is a graph. And this algorithm announces the source of the graph as a winner.
My solutions for the lab and problem set is on the link below. Hope to see you on Week 4. Happy Coding.
Github : https://github.com/volkansahn/CS50-Fall2020.
