CS50 - week 2 - Algorithms

CS50 - week 2 - Algorithms

lecture 3
lecture 3 is in week 2 and the lecture-week numbering is probably not going to match for quite a while. This lecture introduces some more information about strings. Which is an array of chars of length one character larger then the amount of chars (due to an ending "/0" char), which we must keep in mind.

Most of the rest of this lecture was on the topic of algorithms. More precisely: searching algorithms and sorting algorithms. Some properties about these were discussed, such as how long these take to perform as the the number to search/sort increases. In the very zeroth lecture (as they started at lecture 0), David introduces binary search(= go to middle of set you want to search, discard half then go to the middle of the remainder, sorted sets only.) and here he discusses it again and compares it to linear search (= just look at everything in order). Binary search is much faster then linear search, btw. (as David states, you effectively half your problem each step.)

Then in the discussing only sorting, he first talks about three equally efficient sorting methods. (bubble sort, insertion sort and selection sort). For each of these doubling the amount of stuff you sort, you quadruple the amount of time it takes. Then he introduces as fourth sorting method: merge sort, which is just weird, but quicker.

problem set 3

There is one problem set, split into three "helper functions". This problem set is removed now. I thought it was a nice introduction to code that was over multiple files. But it was easier then previous problems, taking less than 3 hours to complete.

Helper function 1: duration
All three functions were meant to read instruction to play music. The first function must get the duration of a certain note. notes are either 1/1, 1/2, 1/4 or 1/8. so turning their chars into ints and multiplying by 8 gave their relative duration.
int duration(string dur)
{
    if (!dur)
    {
        return 1;
    }

    int number = 8 * (dur[0] - 48) / (dur[2] - 48);
    {
        return number;
    }

}

Helper function 2: is rest
the second function determines whether a note was meant to be played at a specific time. this wasn't very difficult either.
bool is_rest(string s)
{
    if (!s)
    {
        return 1;
    }
    if (strcmp(s, "") == 0)
    {
        return true;
    }
    else
    {
        return false;
    }

}

Helper function 3: pitch
This was pretty much the meat of the exercise. turning A4 into 440hz or c4 into 256hz. So it was given that a4 was 440 hz. One ocatave higher meant doubling the pitch. Different notes were 2^1/12 apart and lastly, flat and sharp notes exist. Near the bottom I multiplied and later divided by 10000 because otherwise the floats would round in annoying ways.
int frequency(string notes)
{
    // error
    if (!notes)
    {
        return 1;
    }
    // check length
    bool three = false;
    if (strlen(notes) == 3)
    {
        three = true;
    }
    char note = notes[0];
    int ndis = 0; // for note A
    // determine the note

    switch (note)
    {
        case 'B':
            ndis = 2;
            break;
        case 'G':
            ndis = -2;
            break;
        case 'F':
            ndis = -4;
            break;
        case 'E':
            ndis = -5;
            break;
        case 'D':
            ndis = -7;
            break;
        case 'C':
            ndis = -9;
            break;
    }

    // determine octave location (place 2 or 3)
    int i = 0;
    if (three == true)
    {
        i = 1;
    }
    int octave = notes[1 + i] - 48;

    // correct for sharp or flat
    if (i == 1)
    {
        char fs = notes[1];
        if (fs == 'b')
        {
            ndis--;
        }
        else
        {
            ndis++;
        }
    }

    // output frequency
    float a = 440;

    float exp = 10000 * ndis / 12;

    float c = a * pow(2, exp / 10000) ;

    // correct for octave
    c = c * pow(2, octave - 4) ;

    int d = round(c);
    return d;

}