CS50x Week 3: Game of Fifteen

This week I learned different sorting and searching algorithms. Sorting means arranging the elements in an array in ascending or descending order. Searching means finding an element in an array.

Sorting algorithms

  • Bubble sort
  • Selection sort
  • Insertion sort
  • Quick sort

Searching algorithms

  • Binary search

Bubble sort

Imagine you have a list of numbers, from left to right, unsorted. One of the ways to sort it is bubble sort. Compare the first two elements, if the first element is bigger than the second, switch the first and second element’s position, so the bigger one can move to the right, then compare the second and third element, after you gone through the list once, the numbers are getting better because the bigger number starts to “bubble up”, continue this operation from the start of the list until the list is sorted.

There are many sorting algorithms, you can check cs50’s study website https://study.cs50.net/ for details and animations. Alternatively, you can check this website http://www.sorting-algorithms.com/. MIT bubble sort demo http://web.mit.edu/6.mitx/www/6.00-sortingDemo/sortingDemoBubble.html, click on the play button of graph visualization.

Binary search

Binary search is similar to the bisection search in week 2 of MIT 6.001x course. It eliminates half of the search possibilities on each iteration. The difference between them is binary search deals with distinct element (0, 1, 2, 3,…), while bisection search deals with continuous numbers (numbers between 0 to 100). Both binary search and bisection search requires the array to be sorted before they are performed, because we need to know if our guess is bigger or smaller than the answer.

Big O, Omega, and Big Theta

Different sorting and searching algorithms has different efficiency, the most efficient algorithm performs the task fastest and the least efficient performs the task slowest. How do we measure the efficiency of an algorithm? We learned something called big O, O and Omega, \Omega . Big O states the function of time taken to perform an algorithm at its worst case (e.g. when the array to be sorted is totally opposite from order), and Omega states the function of time taken to perform an algorithm at its best case (the array is already sorted).

Bubble sort, insertion sort, and selection sort has Big O of n^{2} , which means if the array to be sorted gets bigger, the time taken to sort it increases exponentially. You can view the Big O and Omega of various sorts at wikipedia. Binary search has Big O of log{n} , it means when the array size gets bigger, the time taken won’t increase significantly. Quick sort has a Big O of n^{2} , while having an Omega of nlog{n} , so at some good cases, quick sort can perform very fast, but if it met a bad case, it may perform very slow. There are some cases where Big O is equals to Omega, we called it Big Theta, \theta .

GDB debug and importance of pseudocode

Always write pseudocode before writing your code. Pseudocode lets you organize your logic without having to worry about syntax yet. If you do not write pseudocode, you may get confused when an error occurs, and you do not know if its logic problem or the syntax problem.

Example of pseudocode for binary search:

Implementation of code:

GDB debug is a very useful tool to debug your program. It lets you go through step by step of your program execution, and let you view each variable at each step, also, you can modify variable in gdb to test your program.

Problem sets

There are two sections for this week’s problem set, the first deals with sorting and searching, the second implements a game called 15 puzzle.

Searching and sorting

First problem is to make a program that generates a list of pseudorandom numbers. Then, we have to program a file called find to sort the numbers and search for a value chosen by user.
1. Standard edition: Program bubble sort, then linear search.
2. Hacker edition: Program counting sort, then binary search.

Game of Fifteen

  1. Standard edition: tiles are generated at a specified configuration.
  2. Hacker edition: tiles are generated at random (but must be solvable – http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html) + GOD mode is added.

I am unable to implement the GOD mode of hacker edition of game of fifteen, it has something to do with divide and conquer and greedy algorithm http://larc.unt.edu/ian/pubs/saml.pdf.

My codes: https://github.com/shaunlgs/CS50x
Other posts in the series: Harvard CS50x 2014

Leave a Reply