CS50 Quiz 2016: Answer Key

Cookies

Answers

  1. function validate(phone)
{
    if (phone.length != 10)
    {
        return false;
    }
    for (var i = 0; i < phone.length; i++)
    {
        if (phone.charAt(i) < "0" || phone.charAt(i) > "9")
        {
            return false;
        }
    }
    return true;
}

  2. function validate(phone)
{
    var num_digits = 0;
    for (var i = 0; i < phone.length; i++)
    {
        if ((i == 3 || i == 7) && phone.charAt(i) == "-")
        {
            continue;
        }
        if (phone.charAt(i) < "0" || phone.charAt(i) > "9")
        {
            return false;
        }
        num_digits++;
    }
    if (num_digits == 10)
    {
        return true;
    }
    else
    {
        return false;
    }
}

  3. This implementation is vulnerable to SQL injection attacks since it doesn’t escape users' input. If the value of phone contains some substring of SQL, the database might be "tricked" into executing it.

    This implementation also fails to validate (the format of) users' input, instead presumably trusting that the front end has. If a user has somehow disabled JavaScript or circumvented the front end altogether (as by sending HTTP requests via some program), though, the value of phone might not actually be formatted as a phone number but will still be inserted into the database.

Downword Slant

Answers

  1. Yes.

  2. Yes.

  3. No. Just because a word isn’t a downword doesn’t mean it’s an upword. For instance, this is neither a downword nor an upword.

  4. def downword(word):
    if not word.isalpha():
        return False
    for i in range(len(word) - 1):
        if word[i].lower() < word[i+1].lower():
            return False
    return True

It’s Time Again

Answers

  1. In order to copy n elements, all n elements must be accessed, which requires at least n steps.

  2. Whereas searching a list for an element (as via x in s) is documented as being in O(n), which means it requires linear time, searching a set (as via x in s) is documented as being in O(1), which means it requires constant time. Asymptotically, constant time is faster than linear time.

  3. Odds are str objects in Python keep track of their underlying strings' lengths with an instance variable, as with an int. Accessing the value of an instance variable requires only constant time.

Machine Learning Mario

Answers

  1. If an algorithm is stateless, then it has no memory (i.e., state). On each invocation with some input, the algorithm will return the same output.

    Implementations of autocomplete, by contrast, remember (i.e., keep track of) the words already inputted by a user in order to predict the user’s next words.

  2. Pipes (PP) must come out of the ground (==). Most of the ground (=) should be contiguous. Pyramids (=) should be sloped.

  3. Google has access to much more data from many more users, so Google can train its algorithm much more thoroughly.

SQL Sequels

Answers

  1. SELECT "title" FROM "films" WHERE "title" LIKE 'Toy Story %'

    or

    SELECT "title" FROM "films" WHERE "predecessor_title" LIKE 'Toy Story%'

  2. INSERT INTO "films" ("title", "year", "predecessor_title", "predecessor_year", "increase")
    VALUES('Hannibal', 2001, 'The Silence of the Lambs', 1991, 16)

  3. SQLite would store 16 as an INTEGER since it has no fractional component.

  4. CREATE TABLE "films" (
    "id" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "title" TEXT NOT NULL,
    "year" INTEGER NOT NULL
);
CREATE TABLE "sequels" (
    "film_id" INTEGER NOT NULL,
    "predecessor_id" INTEGER NOT NULL,
    "increase" NUMERIC NOT NULL
)

Stranger Things

Answers

  1. Dyn’s DNS servers were overwhelmed with requests from the DDoS attack and couldn’t respond to DNS requests from actual users. Users were thus unable to look up the IP addresses of sites they wanted to visit, rendering them effectively inaccessible.

  2. Many IoT devices have administrative interfaces with default usernames and passwords that attackers know. Attackers can thus log into those devices remotely and install malware. Most users also do not know (how) to upgrade IoT devices' firmware (i.e., built-in software), so even when manufacturers release security updates, most IoT devices remain unpatched.

  3. Upon receiving a TCP/IP packet from a device with a private IP address, a home router must change the packet’s source address from that private IP address to the home router’s own public IP address and the packet’s source port (which is already a pseudorandom number) to some other pseudorandomly generated number (that it hasn’t already used for some other connection on behalf of another device). For the server’s packet, the destination address should be the home router’s public IP address, and the destination port should be the pseudorandom number that the home router generated for its own packet. The home router, meanwhile, needs to remember the source address and source port of the device for whose packet it generated that pseudorandom number.