Week 4

Last Time

  • Last time we looked at numbers and how we might search them and sort them, with algorithms like:

    • linear search

    • binary search

    • bubble sort

    • selection sort

    • insertion sort

    • merge sort

  • We started using basic terms to describe running time (in units of steps taken), like:

    • n2

    • n log n

    • n

    • log n

    • 1

    • …​

  • The notation for running time includes:

    • O, worst-case running time

    • Ω, best-case running time

    • Θ, if both of those are the same

Strings

  • Now we’ll take a closer look at strings and how they are actually stored by the computer.

  • Let’s look at compare0.c:

    #include <cs50.h>
    #include <stdio.h>
    
    int main(void)
    {
        printf("s: ");
        string s = get_string();
    
        printf("t: ");
        string t = get_string();
    
        if (s == t)
        {
            printf("same\n");
        }
        else
        {
            printf("different\n");
        }
    }
    • It looks like this program takes two strings from the user and compares them.

    • But it doesn’t work, when we put in two strings that look the same.

  • Hm, mysterious. Let’s try to copy the string:

    #include <cs50.h>
    #include <ctype.h>
    #include <stdio.h>
    #include <string.h>
    
    int main(void)
    {
        printf("s: ");
        string s = get_string();
        if (s == NULL)
        {
            return 1;
        }
    
        string t = s;
    
        if (strlen(t) > 0)
        {
            t[0] = toupper(t[0]);
        }
    
        printf("s: %s\n", s);
        printf("t: %s\n", t);
    
        return 0;
    }
    • Now we’re getting a string s from the user, copying it to a string called t, and then making the first letter of t uppercase.

    • But when we run the program, it again doesn’t behave like we might expect. Both s and t are capitalized!

  • Another example we can look at:

    #include <stdio.h>
    
    void swap(int a, int b);
    
    int main(void)
    {
        int x = 1;
        int y = 2;
    
        printf("x is %i\n", x);
        printf("y is %i\n", y);
        printf("Swapping...\n");
        swap(x, y);
        printf("Swapped.\n");
        printf("x is %i\n", x);
        printf("y is %i\n", y);
    }
    
    void swap(int a, int b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    • We have a function called swap that’s supposed to take two values, a and b, and swaps them. It takes a, puts the value into a temporary variable called tmp, and then stores the value of b into a. Then the value of tmp, which is the original a, is stored into b.

    • But when we run this program, too, it doesn’t swap the values of x and y in main.

  • So we open our debugger, and step over each line of our program: