CS50 Quiz 2018: Answer Key

Complementary Questions

Answers

1.1: 10000011
1.2: 11111101
1.3: If a counter is stored as an integer using a finite number of bits (e.g., 32), that counter can only count so high before overflowing, at which point the pattern of bits might be mistaken as representing a negative value.
1.4: After doubling 1073741824, that program was supposed to print 2147483648, but instead printed -2147483648 because i (a 32-bit value) overflowed. After doubling -2147483648, the program began to print 0 because -4294967296 is 100000000000000000000000000000000 in binary, but only 32 of those 33 bits (each a 0) fit in an int, and so i itself took on a value of 0 thereafter, since doubling 0 only yields 0.
1.5: The rocket’s software converted a 64-bit value to 16 bits, the result of which impacted the rocket’s nozzles, and so the rocket was remotely destroyed for safety’s sake.

False Alarm

Answers

2.1: An incredibly important option, PACOM (CDW) - STATE ONLY, is co-mingled with a drill, false alarm, and monthly test, with no indication of just how consequential it might be to select it accidentally.
2.2: Arguably, both the human and the UI are to blame. The human surely should have taken greater care when conducting a drill, and the UI surely should have made it more difficult for a user to err.
2.3a: With HTML could you implement the UI using a drop-down menu or list of links or even a button for each function.
2.3b: With CSS could you stylize the UI, perhaps even hiding the most impactful of functions by default.
2.3c: Via JavaScript could you prompt humans, even multiple times, to confirm their intentions, perhaps even having them type some word or sentence verbatim to be sure.
2.4: Via SQL could you store UI’s list of functions, one function per row, thereby avoiding hardcoding each in some HTML.
2.5: Humans might still accidentally confirm the wrong function, as might happen mindlessly or if they become too conditioned to confirming functions without thinking.

It Terns Out

Answers

3.1: 4
3.2: 3
3.3: 4
3.4: 27
3.5: 13
3.6: -13
3.7: +-0--
3.8: Instead of storing some electricity or no electricity to represent either of two values, as in binary, the computer could store some electricity, less electricity, or no electricity to represent any of three values in ternary.

A text file might just happen to start with those characters because a human happened to type them, and a binary file might just happen to start with those bytes because they happen to have significance in some other file format.

4.4

The bitwise AND of any bit with 0 is 0. The bitwise AND of any bit with 1 is that same bit. Since 0xf0 is 11110000 in binary, the effect of buffer[3] & 0xf0 is to preserve the first hexadecimal digit of buffer[3] and zero the second hexadecimal digit. So if (buffer[3] & 0xf0) == 0xe0, then buffer[3] must be between 0xe0 and 0xef, inclusive.

4.5

Rather than evaluate as many as sixteen expressions for equality, Zamyla’s proposed code evaluates just one, which might be 1/16th as much work!

4.6

#include <stdio.h>

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        return 1;
    }

    FILE *file = fopen(argv[1], "r");
    if (file == NULL)
    {
        return 1;
    }
    unsigned char buffer[8];
    size_t blocks = fread(buffer, sizeof(char), 8, file);
    fclose(file);

    if (blocks >= 2 && buffer[0] == 0x42 && buffer[1] == 0x4d)
    {
        printf("BMP\n");
    }
    else if (blocks >= 4 && buffer[0] == 0xff && buffer[1] == 0xd8 && buffer[2] == 0xff && (buffer[3] & 0xf0) == 0xe0)
    {
        printf("JPEG\n");
    }
    else if (blocks >= 4 && buffer[0] == 0x25 && buffer[1] == 0x50 && buffer[2] == 0x44 && buffer[3] == 0x46)
    {
        printf("PDF\n");
    }
    else
    {
        printf("\n");
    }

    return 0;
}

Memes

Answers

5.1

A field for a commenter’s ID, a field for the comment itself, a field for the comment’s number of likes, a field for the date and time at which the comment was posted.

5.2

If each comment is stored as a row in the table, the table might have a column for the ID of the comment, if any, to which another comment is a reply (e.g., parent_id).

5.3

function linkify(s) {
    let t = s;
    for (let friend in FRIENDS) {
        t = t.replace(friend, '<a href="https://www.facebook.com/' + FRIENDS[friend] + '">' + friend + '</a>');
    }
    return t;
}

Omega Directive

Answers

6.1: Selecting the smallest element among n requires that you examine all n elements, selecting the next-smallest element among n – 1 elements requires that you examine n – 1 elements, and so forth, the sum of which is in Ω(n²).
6.2: Merge sort effectively divides 1 array of size n in n arrays of size 1, which requires n log n such splits, and after each split, all n elements need to be merged, the result of which is ϴ(n log n) operations in total.
6.3: Because strings in C are identified by the address of their first byte and terminated with \0, strlen must necessarily iterate over every character in a string, from first to last, in order to count its characters and, thus, length.
6.4: Insofar as a list is an "object" in Python akin to a struct in C, odds are each list has a field (i.e., variable) that stores its current length, which len can access in constant type.
6.5: Odds are isupper checks whether the underlying ASCII value of a char is between A (i.e., 65) and Z (i.e., 90), inclusive, which requires only a constant number of comparisons (e.g., 2).

Slanted Cipher

Answers

7.1

A cipher is "secure" if it is impossible or, at least, very difficult, expensive, or time-consuming to recover, given some ciphertext, the corresponding plaintext.

7.2

Caesar’s cipher only allows for 26 possible keys, and so, simply by guessing and checking keys can an adversary, given some ciphertext, recover the corresponding plaintext easily and quickly via "brute force."

7.3

Each of the plaintext’s original characters remain visible in the ciphertext, and so an adversary could simply iteratively rearrange those characters, a la an anagram, to recover the plaintext.

7.4

The resulting ciphertext would be identical to its plaintext.

7.5

Hashing is a one-way operation via which a string of any length is mapped to a string of some fixed (typically shorter) length, whereas encryption is a two-way operation using some key that can be reversed via the same key.

7.6

def slant(message, depth):
    ciphertext = ""
    for i in range(depth):
        for j in range(i, len(message), depth):
           ciphertext += message[j]
    return ciphertext

Song that Never Ends

Answers

8.1

RecursionError: maximum recursion depth exceeded while calling a Python object

8.2

#include <stdio.h>

void song(void);

int main(void)
{
    song();
}

void song(void)
{
    printf("This is the song that doesn't end.\n");
    printf("Yes, it goes on and on my friend.\n");
    printf("Some people started singing it not knowing what it was,\n");
    printf("And they'll continue singing it forever just because...\n");
    song();
}

8.3

Segmentation fault

8.4

The C version eventually leads to a stack overflow, whereby the frames on the stack for each call to sing overflow the capacity of the stack, thereby overlapping the heap.

8.5

def main():
    while True:
        sing()


def sing():
    print("This is the song that doesn't end.")
    print("Yes, it goes on and on my friend.")
    print("Some people started singing it not knowing what it was,")
    print("And they'll continue singing it forever just because...")


if __name__ == "__main__":
    main()

8.6

On each iteration of the algorithm, David divided the problem in half, thereafter applying the very same algorithm to one half.

View As

Answers

9.1: An access token is a (seemingly random) string that a user is granted after logging into some system that can be used thereafter to make API calls, without providing one’s credentials (e.g., username and password) again and again.
9.2: Facebook’s View As feature allowed users to post videos, even though it was supposed to be view-only; Facebook’s video uploader generated an access token that had the same permissions as Facebook’s mobile app; that token was for the account of the user being viewed. Attackers could thus obtain an access token for you rather than for only themselves.
9.3: Facebook presumably logged users out forcibly so as to stop attackers from using access tokens that didn’t belong to them.
9.4: While a session token can be used to remember that someone is logged in, it is more generally used to maintain state over HTTP between a user and a "session," a server-side object in which data for that user can be stored.

Wonderful Queue

Answers

10.1

Using an array, which supports random access, allows you both to add and remove elements in constant time. However, this question was flawed insofar as the proposed struct should have contained an additional field of type int to store the index of the first (or, equivalently, last) shirt in the queue. All answers were thus accepted.

10.2

A linked list allows the queue to grow and shrink dynamically, without needing to hard-code the maximal size of the queue or iteratively allocate, free, and reallocate memory for the entire queue.

10.3

A queue can be implemented more simply with just one line of code in Python.

10.4

Operations on the queue might be faster without the overhead of interpreting Python.

10.5

q.append(s)
q.pop(0)