CS50’s Introduction to Algorithms

This is 4th blog in my ongoing CS50 Series. Readers are suggested to go through 0th, 1st & 2nd blog for a better understanding of subject matter. In this blog, you will learn about the algorithms.

Credit: www.pandorafms.com

In the previous blog, I discussed some important concepts of C language. In this blog, I will discuss the following topics

• Algorithm & its Efficiency
• Linear Search
• Binary Search
• Bubble Sort
• Insertion Sort
• Selection Sort
• Recursion
• Merge Sort
• Summary

Algorithm & its Efficiency

The algorithm means step by step instructions for solving a problem. There can be different ways to solve the problem. Suppose you want to find the contact of a person in the phone book, you can use the following ways.

1. You can start by flipping through the book, one page at a time until we find the contact of a person or reach the end of the book.
2. You could also flip two pages at a time, but we may miss the name.
3. The more efficient way will be, to go to middle pf phonebook and decide whether a person’s name will be in left or right half as per alphabetical order and immediately throwing half of the problem. Repeat this by dividing the problem in half each time. Thus you can find the contact of the person in very few steps (10 steps for 1024 pages)

To understand which algorithm is best, there is a need to measure their efficiency. The efficiency of algorithms is measured in terms of increase in time required to solve the problem with an increase in input n (here n = number of pages in phonebook). Computer Scientists use following two terminologies to describe the efficiency of the algorithm.

• Big O (O) Notation
  Big O notation is the upper bound of the number of steps for the algorithm to solve the problem or the efficiency in a worst-case scenario. For example, if an algorithm takes n steps in the worst case then the worst-case efficiency of an algorithm is O(n) or “on the order of n”.
• Big Omega (Ω) Notation
  Big Ω notation is the lower bound of the number of steps for the algorithm to solve the problem or the efficiency in a best-case scenario. For example, if an algorithm finds the first element as a target element (best case) and only takes 1 step then the best case efficiency of an algorithm is Ω(1).

Now let’s get back to the problem, to find the contact of a person in the phone book, the worst-case efficiency of all the three ways you adopted is shown in the following figure, where X-axis shows an increase in the time to solve the problem w.r.t. increase in the size of the problem (n = number of pages in the current problem)

Big O Notation (Credit: CS50 )

• The first way is represented by the red line, time to find the contact increases linearly with the increase in the number of pages. The worst-case efficiency will be O(n)
• The second way is represented by the yellow line, the slope of the line is less steep but still linear. The worst-case efficiency will be O(n) because as the size of the problem becomes bigger & bigger, red & yellow line will come closer and will be approximately same.
• Third & final way is represented by the green line: logarithmic, time to solve the problem increases very slowly (logarithmically) as the size of the problem increases.

Thus the third way is the most efficient way (algorithm) amongst all three ways to find the contact of the person in the phonebook.

Linear Search

In Linear Search, the idea is to iterate across each element of the array from left to right, searching for the specified element. Pseudocode is a plain language description of the steps in an algorithm intended for human reading rather than machine reading. Pseudocode for linear search can be written as follows.

• Repeat, starting at the first element
  • If the first element is what you are searching for, Stop.
  • Otherwise move to next element.

Worst Case Scenario: O(n)
Best Case Scenario: Ω(1)

Linear Search (Credit: Shivam Frequency)

Binary Search

The binary search uses a divide & conquer approach, reducing the search area by half each time, trying to find a target number. To use binary search, however, the array must be sorted. Pseudocode for binary search can be written as follows.

• Repeat, until array size is of size 0
  • Calculate the middle point of the current array
  • If the target is at the middle, Stop.
  • Otherwise if the target is less than the element at the middle, repeat changing the endpoint at the left of middle.
  • Otherwise if the target is greater than the element at the middle, repeat changing the start point at the right of middle.

Worst Case Scenario: O(logn)
Best Case Scenario: Ω(1)

Binary Search (Credit: Shivam Frequency)

Bubble Sort

In bubble sort, the computer moves higher valued elements towards the left end and lower valued elements toward the right end of the array. This can be by comparing adjacent elements then swapping them if the first element is greater than the second element. Pseudocode for bubble sort can be written as follows.

• Set swap counter to a non zero value
• Repeat until the swap counter is 0.
  • Reset the swap counter to 0.
  • Look at each adjacent pair
  • If two adjacent elements are not in order, swap them and add 1 to swap counter

Worst Case Scenario: O(n²)
Best Case Scenario: Ω(n)

Bubble Sort (Credit: Geeksforgeeks)

Insertion Sort

In insertion sort, the sorted array is built by shifting unsorted elements as we go on checking the elements. Pseudocode for insertion sort can be written as follows.

• Call the first element of the array “sorted.”
• Repeat until all elements are sorted:
  • Look at the next sorted element. insert it into the “sorted” portion by shifting the requisite number of elements.

Worst Case Scenario: O(n²)
Best Case Scenario: Ω(n)

Insertion Sort (Credit: Geeksforgeeks)

Selection Sort

In selection sort, the computer searches for the smallest element in an array and swap that element with the first element, thus building a sorted array element by element. Pseudocode for selection sort can be written as follows.

• Repeat until no unsorted element remain
  • Search the unsorted part of the array to find the smallest element
  • Swap the smallest found value with the first element of an unsorted array.

Worst Case Scenario: O(n²)
Best Case Scenario: Ω(n²)

Selection Sort (Credit: Geeksforgeeks)

Recursion

There is an old joke about Recursion:

‘To understand recursion, you must first understand recursion’

The definition of the recursive function is one that as a part of its execution, invokes itself. Every recursive function has two cases

• Base case
  When the base case is triggered, it will terminate the recursive process.
• Recursive case
  It is an actual case where recursion occurs.

Look at the following function to calculate factorial of a number.

int fact(int n)
{
if (n == 1) //base case
return 1;
else // recursive case
return n * fact(n- 1);
}
int main (void)
{
printf(“%i \n”, fact(5));
}

Here fact() is recursive function as it is calling itself again and again during its own execution. You will understand it in a better way from the following visualization.

Merge Sort

The idea of merge sort algorithm is to sort smaller arrays and then combine those smaller arrays in sorted order. Pseudocode for the merge sort can be written as follows.

• Sort the left halve of the array
• Sort the right halve of the array
• Merge both the halves

Worst Case Scenario: O(nlogn)
Best Case Scenario: Ω(nlogn)

Merge Sort (Credit: Geeksforgeeks)

Summary

After learning so many searching & sorting algorithms, it will be confusing for you to remember how each algorithm works. But don't worry, I have a solution. The following table will help you remember all the basic concepts of algorithms.

Conclusion

I hope that this blog was helpful to you. This series of blogs on CS50 will continue. Thank you very much for your patient reading. You can find my next blog here. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. You can connect with me on LinkedIn or by visiting my website on Medium. Happy Learning.