CS50 Algorithms

Took cs50 algorithms harvard .edu course recently I found it very interesting and educative . lets begin :-)

Definition

a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

Overview

Recall that computing involves taking some form of input, and then processing that input in order to produce some form of output. Processing input will often require the use of an algorithm, which are sequences of instructions that can be executed by a computer. In computer science, these algorithms are usually written in code. Computers depend upon such algorithms in order to perform tasks. In many cases, multiple different algorithms can be used to achieve the same result. However, in some cases, one algorithm will be faster than another at arriving at the correct result.

A Correct Algorithm

Algorithms are just sequences of steps that a computer can follow in order to translate input into output. Algorithms can be expressed in English as a detailed list of steps.

Take, for example, the task of finding a name (e.g. “John Doe”) in a phone book. One possible algorithm (represented to the left) involves picking up the phone book, opening to the first page, and checking to see if John Doe is on the page. If he’s not, flip to the next page, and check that page. Keep repeating this until you either find John Doe or get to the end of the book.This algorithm is correct — if John Doe is in the phone book, then this algorithm will successfully allow someone to find him. However, algorithms can be evaluated not only on their correctness but also on their efficiency: a measure of how well an algorithm minimizes the time and effort needed to complete it. The one-page-at-a-time algorithm is correct, but not the most efficient.We could improve the algorithm by flipping two pages at a time instead of one — though we’d have to be careful of the case where we might skip over the page with John Doe’s name, at which point we’d have to go back a page. But even this algorithm is not the most efficient.

1 pick up phone book

2 open to first page of phone book

3 look at names

4 if “John” is among names

5 call John

6 else if not at end of book

7 flip to next page

8 go to line 3

9 else

10 give up

1 pick up phone book

2 open to middle of phone book

3 look at names

4 if “John” is among names

5 call Doe

6 else if “John” is earlier in book

7 open to middle of left half of book

8 go to line 3

9 else if “John” is later in book

10 open to middle of right half of book

11 go to line 3

12 else13 give up

Searching

• We can think of an array with a number of items as a row of doors, where a computer can only open one door to look at an item, one at a time.
• For example, if we want to check whether a number is in an array, with an algorithm that took in an array as input and produce a boolean as a result, we might:
• Open each door, or look at each element, one at a time, from the beginning to the end.
• This is called linear search, where we move in a line, since our array isn’t sorted.
• start in the middle and move left or right depending on what we’re looking for, if our array of items is sorted.
• This is called binary search, since we can divide our problem in two with each step, like what David did with the phone book in week 0.
• start in the middle and move left or right depending on what we’re looking for, if our array of items is sorted.
• This is called binary search, since we can divide our problem in two with each step, like what David did with the phone book in week 0.
• We might write pseudocode for linear search with:

For i from 0 to n–1
    If i'th element is 50
        Return true
Return false

• We can label each of n lockers from 0 to n–1, and check each of them in order.
• For binary search, our algorithm might look like:

If no items
    Return false
If middle item is 50
    Return true
Else if 50 < middle item
    Search left half
Else if 50 > middle item
    Search right half

• Eventually, we won’t have any parts of the array left (if the item we want wasn’t in it), so we can return false.
• Otherwise, we can search each half depending on the value of the middle item.
• We can label each of n lockers from 0 to n–1, and check each of them in order.
• For binary search, our algorithm might look like:

Big O

• different types of algorithms and their running times:

• The more formal way to describe this is with big O notation, which we can think of as “on the order of”. For example, if our algorithm is linear search, it will take approximately O(n) steps, “on the order of n”. In fact, even an algorithm that looks at two items at a time and takes n/2 steps has O(n). This is because, as n gets bigger and bigger, only the largest term, n, matters.
• Similarly, a logarithmic running time is O(log n), no matter what the base is, since this is just an approximation of what happens with n is very large.
• There are some common running times:
• O(n2)
• O(n log n)
• O(n)
• (linear search)
• O(log n)
• (binary search)
• O(1)
• Computer scientists might also use big Ω, big Omega notation, which is the lower bound of number of steps for our algorithm. (Big O is the upper bound of number of steps, or the worst case, and typically what we care about more.) With linear search, for example, the worst case is n steps, but the best case is 1 step since our item might happen to be the first item we check. The best case for binary search, too, is 1 since our item might be in the middle of the array.
• And we have a similar set of the most common big Ω running times:
• Ω(n2)
• Ω(n log n)
• Ω(n)
• (counting the number of items)
• Ω(log n)
• Ω(1)
• (linear search, binary search)

Linear search

• Let’s take a look at numbers.c:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // An array of numbers
    int numbers[] = {4, 8, 15, 16, 23, 42};

    // Search for 50
    for (int i = 0; i < 6; i++)
    {
        if (numbers[i] == 50)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

• Here we initialize an array with some values, and we check the items in the array one at a time, in order.
• And in each case, depending on whether the value was found or not, we can return an exit code of either 0 (for success) or 1 (for failure).
• We can do the same for names:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // An array of names
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};

    // Search for EMMA
    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

• We can’t compare strings directly, since they’re not a simple data type but rather an array of many characters, and we need to compare them differently. Luckily, the string library has a strcmp function which compares strings for us and returns 0 if they’re the same, so we can use that.
• Let’s try to implement a phone book with the same ideas:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"EMMA", "RODRIGO", "BRIAN", "DAVID"};
    string numbers[] = {"617–555–0100", "617–555–0101", "617–555–0102", "617–555–0103"};

    for (int i = 0; i < 4; i++)
    {
        if (strcmp(names[i], "EMMA") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

• We’ll use strings for phone numbers, since they might include formatting or be too long for a number.
• Now, if the name at a certain index in the names array matches who we’re looking for, we’ll return the phone number in the numbers array, at the same index. But that means we need to particularly careful to make sure that each number corresponds to the name at each index, especially if we add or remove names and numbers.

reference:lecture3-CS50x