CS50 Test 2017: Answer Key

Analyze This

Answers

1. Yes.
2. \$O(n)\$, where \$n\$ is the number of cards, since Stelios needs to iterate over the cards twice, once based on their last digit, once based on their first digit. If curious, this happens to be an algorithm called radix sort!
1. Yes.
2. \$O(n^2)\$, where \$n\$ is the length of the array. On each iteration from left to right or from right to left, Maria still makes the same number of comparisons: \$n - 1\$ on the first iteration, \$n - 2\$ on the second iteration, \$n - 3\$ on the third iteration, and so forth, the sum of which is still \$n*(n-1)/2\$, which is in \$O(n^2)\$. If curious, this happens to be an algorithm called cocktail shaker sort!
1. Yes.
2. \$O(n^2)\$, assuming Natalie’s shuffling algorithm is in \$O(n)\$ (as is possible with Fisher-Yates shuffle, if curious), where \$n\$ is the number of cards. After each look for the queen of hearts, Natalie reduces the number of cards by 1, which means as many as \$n\$ looks, and after each such look (save the last), she shuffles the cards, which means a total of \$n - 1\$ shuffles. If each shuffle costs \$O(n)\$ time, the total cost is thus \$(n-1)*O(n)\$, which is in \$O(n^2)\$. If Natalie’s shuffling algorithm is instead in \$O(n^2)\$, as might be the case if Natalie doesn’t have random access to the cards and must instead iterate through them while shuffling, then Natalie’s search for the queen of hearts would instead be in \$O(n^3)\$. But if we consider Natalie’s number of cards to be finite (e.g., 52), then Natalie’s algorithm is in \$O(1)\$.

Being Served

Answers

200, because the request succeeded, with cats in the response.
301 (or 302), because the user was redirected to another Location.
403, because the user is forbidden to access the page if not logged in.

Emoji

Answers

Strictly speaking, 3 bytes are necessary, since its code point (0x1F383) comprises 5 hexadecimal digits, each of which represents half of a byte, which collectively total 2.5 bytes (though bytes cannot be fractional). If we store that code point in a wchar_t, the size of which is 4 bytes, then 4 bytes are necessary.
A char in C is only 1 byte, which is too small to fit a jack-o-lantern’s code point.

emoji get_emoji(string prompt)
{
    while (true)
    {
        string code = get_string(prompt);
        if (strlen(code) < 3 || strlen(code) > 10)
        {
            continue;
        }
        if (strncmp(code, "U+", 2))
        {
            continue;
        }
        bool isx = true;
        for (int i = 2, n = strlen(code); i < n; i++)
        {
            if (!isxdigit(code[i]))
            {
                isx = false;
                break;
            }
        }
        if (isx)
        {
            return strtol(code + 2, NULL, 16);
        }
    }
}

Fair and Balanced

Answers

Yes (because \$16 + 26 = 42 = 3 + 39\$).
Yes (because \$0 + 0 = 0 = 0 + 0\$).

bool balanced(int array[], int n)
{
    int left = 0, right = 0;

    for (int i = 0, j = n - 1; i < j; i++, j--)
    {
        left += array[i];
        right += array[j];
    }

    if (left == right)
    {
        return true;
    }
    else
    {
        return false;
    }
}

Functions

Answers

Because this hash function looks only at a string’s first character (which is assumed to be a letter), it only supports a range of 26 values (i.e., buckets), which means collisions might be more likely than they would be with more buckets. Moreover, if some first letters are more common than others (as is the case with English words), then collisions might be even more likely. If the hash tables use linear probing, insertions and lookups are likely to approach linear time; if the hash table uses separate chaining, some chains are likely to become long, in which case insertions and lookups might also approach linear time.
Insofar as a character is represented in ASCII by a unique sequence of bits, a string, which is just a sequence of characters, is similarly represented by a unique sequence of bits. A sequence of bits, meanwhile, uniquely defines a number in binary, which has a unique representation in decimal as well. This hash function is thus perfect in theory since each of its inputs yields a unique output. The hash function is imperfect in practice insofar as it requires too many buckets. To support all strings of length \$n\$ requires \$2^{8*n}\$ buckets, which means even short strings of length 4 would require \$2^{8*4}=2^{32}=4,294,967,296\$ buckets. Even if each bucket requires only 1 byte, that’s already 4 gigabytes of space. Moreover, you couldn’t store a value that large in a variable (in C at least), since the size of an int, for example, is just 4 bytes. If the hash value is stored as an int, two different strings might hash to the same value due to integer overflow.
It’s more space-efficient (i.e., cheaper) to store 256 bits for each image rather than each image (which might be kilobytes or megabytes). And it’s more time-efficient (i.e., faster) to compare only 256 bits (rather than kilobytes or megabytes).
If we assume that the strings in a trie are of some maximal (i.e., bounded) length, \$k\$, as is the case with English words, then lookups of those words in a trie require \$O(1)\$ steps insofar as \$k\$ is, by definition, constant. Because of collisions, though, a hash table can devolve, in the worst case, into an array or linked list of words, in which case lookups of words are dependent on the number of words already in the hash table; if the number of words is \$n\$, then lookups are in \$O(n)\$. :stem: latexmath

Helping `help50`

Answers

Looks like you tried to use modulo (%) with a float. Did you mean for n to be an int?
Looks like you’re trying to assign get_string itself (rather than its return value) to input. Did you mean to call get_string? Did you omit some parentheses if so?
Looks like you’re trying to compare a char against 0xff. But the maximal value of a char (which is technically signed) is 127, and 0xff is 255. Did you mean to declare buffer[0] as a BYTE (i.e., unsigned char)?
Looks like you’re trying to initialize a pointer (a "scalar type") with a data structure. Did you mean to declare root as a struc? :stem: latexmath

Now Boarding

Answers

typedef struct
{
    passenger *passengers;
    int capacity;
    int size;
}
pqueue;

If passengers is NULL
    Allocate space for as many passengers as there are seats
    Initialize capacity to that number of seats
    Initialize size to 0
If size < capacity
    Insert new passenger at passengers[size]
    Increment size
Else
    Put passenger on standby

\$O(1)\$, since passengers, as a dynamically allocated array, supports random access.

For each passenger in passengers
    Look at passenger's group
    If lower than any we've seen before
        Remember that passenger
Remove remembered passenger from pqueue
Shift all passengers after that passenger
Decrement size

\$O(n)\$, since the algorithm shifts as many as \$n-1\$ passengers after dequeuing one.

Stack Smashing

Answers

A stack canary is a value (e.g., an int) that’s stored on the stack when a function is called, in addition to a return address and any arguments or local variables. If that value happens to change before it’s time to return from one function to another, a stack buffer overflow is assumed and the program terminates.
Miners used to bring canaries into coal mines to serve as warning signs of carbon monoxide, as the canaries would exhibit signs of illness before the miners themselves. Stack canaries play a similar role insofar as they reveal stack buffer overflows that might be indicative of an attack.

void f(char *s)
{
    char t[50];
    strcpy(t, s);
}

Z++

Answers

function subtract($x, $y)
{
    return(add($x, -$y))
}

function multiply($x, $y)
{
    if ($x < 0)
    {
        return(-multiply(-$x, $y))
    }
    if ($y < 0)
    {
        return(-multiply($x, -$y))
    }
    $product <- 0
    $i <- 0
    while ($i < $y)
    {
        $product <- add($product, $x)
        $i <- add($i, 1)
    }
    return($product)
}

function multiply($x, $y)
{
    if ($x < 0)
    {
        return(-multiply(-$x, $y))
    }
    if ($y < 0)
    {
        return(-multiply($x, -$y))
    }
    if ($y < 1)
    {
        return(0)
    }
    return add($x, multiply($x, subtract($y, 1)))
}