In this post, the fourth lecture of CS50 is summarized.

Search algorithm

Linear search

Anytime you search from left to right or from right to left, it’s called linear search.

Binary search

Pseudo code for the binary sesarch algorithm.

If no doors left
  Return false
If 50 is behind doors[miidle]
  Return true
Else if 50 < doors[middle]
  Search doors[0] thorugh doors[middle - 1]
Else if 50 > doors[middle]
  Search doors[middle + 1] through doors[n - 1]

Running Time

Although there is a more formal mathematical definition for the terms introduced below, for now we’ll briefly learn about the symbols used at expressing the running time of the algorithm.

• \(O\) refers to the upper bound of the running time. For example, binary search is \(O(logn)\).
• \(\Omega\) refers to the lower bound of the running time. For example, binary search is \(\Omega(1)\).
• If \(O\) and \(\Omega\) happen to be the same, we can use \(\Theta\).

strcmp

In string.h there is a function strcmp which compares the two string parameters and tells whether they are same. It retuns 0 if they are same. Why might it be valuable for strcmp function to return 0 if the strings are equal as opposed to a simple Boolean like true or false? It turns out strcmp actually compares the two strings for equality but also for what’s called, ASCII-betical order. It compares the integer values of the letters. If I use ‘==’ to compare two strings, I was not comparing the strings in the wway that you might have thought. ‘==’ is doing something different in python or java than it is doing in C. More details on next week.

structs

C allows us to create our own data structures, our own types of variables.

typedef struct
{
  string name;
  string number;
}
person;

Using ‘struct’ we can create our own data structure. A structure can be a variable that contains any number of other variables. ‘typedef’ is a keyword that means define the following type.

int main(void){
  person people[3];

  people[0].name = "LEE";
  people[0].number = "010-0000-0000";
}

In order to initialize ‘people’, we use dot to access their name and number field.

Sorting

Selection sort

I select the element I want again and again on the basis of how small it is. I look for the smallest, then the next smallest, and so forth.

For i from 0 to n-1
  Find smallest number between numbers[i] and numbers[n-1]
  Swap smallest number with numbers[i]

If we have n numbers, \((n-1)\) comparisons occurs to find the smallest number. \((n-2)\) for the next one. Thus, \(O(n^{2})\). With selection sort, what would be the best case scenario be? The best case would be every element is already sorted. But does selection sort appreciate that? The answer is no since selection sort does not take into account whether the list is already sorted. There’s no special conditional ‘if it’s already sorted exit early’. Thus, it is \(\Omega(n^{2})\). Also, \(\Theta(n^{2})\).

Bubble sort

I fix local problems again and again until I fix all of the minor problems.

Repeat n-1 times
  For i from 0 to n-2
    If numbers[i] and numbers[i+1] out of order
      swap them
  If no swaps
    quit

The number of comparison is \((n-1)^{2}\), so the running time is asymptotically \(O(n^{2})\). In the best case, if all elements are already sorted, you compare only \((n-1)\) times, so it is \(\Omega(n)\). We can’t say anything about theta notation for bubble sort because the upper and lower bounds are different but we seem to have done better asymptotically than selection sort.

Recursion

Recursion is a description for a function that calls itself. Below is a code written in iterative approach to print pyramid.

void draw(int n){
  for (int i = 0; i < n; i++){
    for (int j = 0; i < i + 1; j++){
      printf("#");
    }
    printf("\n");
  }
}

Now, lets write the code by using recursion.

void draw(int n){
  // If nothing to draw
  if (n <= 0){
    return;
  }
  // Print pyramid of height n - 1
  draw (n - 1);
  // Print one more row
  for (int i = 0; i < n; i++){
    printf("#");
  }
  printf("\n");

The point of introducing recursion is it’s going to be very powerful problem-solving technique since it tightens up the amount of code or the amount of lines that you need to write to convey an algorithm. Also, it allows us to solve problems in a fundamentally different way by using computer’s memory in an interesting way.

Merge sort

If only one number
  Quit
Else
  Sort left half of numbers
  Sort right half of numbers
  Merge sorted halves

With selection sort and bubble sort, we allowed ourselves constant amount of memory, just one variable. For instance, in selection sort we keep track of the smallest number. In bubble sort, the only number we track is i. We didn’t allow any additional memory. However, in programming and in CS, you can trade off one resource for another. If you want to spend less time solving a problem, you have to spend more space, spend more money in order to give yourself more space to reduce the time. Conversely, if you’re fine with things being slow in terms of time, then you can get away with very little space. In merge sort, we have an original array. In order to sort the left half, we steal some more memory and work on new space of memory. We do this process recursively. Technically, we can be more intelligent about using the memory and actually go back and forth between two memory spaces of array. In merge sort, we can divide a problem of size \(n\) \(log_2n\) times. It is the height of the chart below. Every time we divide the size of the problem, we have to take the numbers and merge them together \(n\) times. Every row of the chart below, there are n steps of merging. Thus, the total running time is \(O(nlogn)\). It is also in \(\Omega(nlogn)\), which means bubble sort might sometimes outperform it when the inputs are already sorted or certainly relatively small. But in general, data that we’re sorting probably isn’t very sorted. We could even adjust merge sort to do one pass to check initially, is the whole thing sorted, and then terminate early.