Test: Sample Solutions

Baby Shark Dance

  1. A 32-bit int in C can only represent numbers as high as 2,147,483,647 (which is \(2^{31} - 1\)). If YouTube were to store a view count larger than that in an int, integer overflow would result, and the view count would likely no longer be accurate.
  1. Yes. Integers larger than the maximum possible int value can be represented using this representation, but can’t be represented with an int alone. For example, the number 3,000,000,000 is larger than would fit in an int, but could be represented using a linked list.
  1. Yes. Negative integers can be represented with an int, but cannot be represented using this representation. Since each node can only store a digit from 0 to 9, there’s no way this representation can be used to store negative numbers. For example, -1 can be represented in an int, but has no representation using this linked list representation.
  1. bool divisible_by_three(node *n)
{
    // Keep track of sum of digits so far
    int sum = 0;

    // Iterate through linked list nodes
    node *tmp = n;
    while (tmp != NULL)
    {
        // Add current digit to total sum
        sum += tmp->digit;
        tmp = tmp->next;
    }

    // Check if total sum is divisible by 3
    return sum % 3 == 0;
}

  1. bool equal(node *a, node *b)
{
    // Iterate over both lists in parallel
    while (a && b)
    {
        // If current digits differ, integers aren't equal
        if (a->digit != b->digit)
        {
            return false;
        }

        // Move on to next nodes
        a = a->next;
        b = b->next;
    }

    // Integers are equal if we made it to end of both lists
    return a == NULL && b == NULL;
}

    bool equal(node *a, node *b)
{
    // Base case: both values are NULL
    if (a == NULL && b == NULL)
    {
        return true;
    }

    // Check for different lengths
    else if (a == NULL || b == NULL)
    {
        return false;
    }

    // Check current digit and recursively check other digits
    else
    {
        return a->digit == b->digit && equal(a->next, b->next);
    }
}

  1. void increment(node *n)
{
    // Base case, when digit is less than 9
    if (n->digit < 9)
    {
        // Increment least-significant digit
        n->digit++;
    }

    // Recursive case
    else if (n->next != NULL)
    {
        // Change 9 to 0 and recursively add one to the next digit
        n->digit = 0;
        increment(n->next);
    }

    // Base case: additional digit needed
    else
    {
        // Set current digit to 0
        n->digit = 0;

        // Add a new digit set to 1
        node *tmp = malloc(sizeof(node));
        tmp->digit = 1;
        tmp->next = NULL;
        n->next = tmp;
    }
}

Complexities of Space

  1. \(O(1)\). Selection sort only requires a constant amount of space to iterate over its input (as with i) and perhaps some space for a temporary variable via which to swap two items. That amount of space is independent of n.
  1. \(O(n)\). Given an array of size n as input, merge sort requires space for a second array, which itself is of size n (i.e., \(O(n)\)), into which it can merge sorted halves from its input. The input array as well as that second array can alternately be reused for subsequent merges.
  1. Because this function calls itself n times recursively, n (i.e., \(O(n)\)) frames accumulate on the stack (before the last of those calls returns), each of which contains space for, at least, one argument (an int).
  1. int sum(int n)
{
    int total = 0;
    for (int i = 1; i <= n; i++)
    {
        total += i;
    }
    return total;
}

    int sum(int n)
{
    return (n + 1) * n / 2;
}

Cracking Passwords

  1. \(O(n)\). In the worst case, the adversary might have to try hashing all \(n\) words in the dictionary.
  1. For each word, w, in dictionary
    For each character, c, in ASCII
        Call check_password_hash on concatenation of w and c

    \(O(n)\). Since there are 128 ASCII characters (or 256 in Extended ASCII), the adversary might now have to try hashing \(128 \times n\) (or \(256 \times n\)) strings instead, but that’s still in \(O(n)\). Or, if unsure whether c was prepended or appended to w, the adversary might now have to try hashing \(2 \times 128 \times n\) (or \(2 \times 256 \times n\)) strings instead, but that’s in \(O(n)\) too.

  1. For each word, w1, in dictionary
    For each word, w2, in dictionary
        Call check_password_hash on w1 + " " + w2

    \(O(n^2)\), because there are \(n^2\) possible pairs of \(n\) English words.

  1. \(O(10^n)\), because there are \(10^n\) possible combinations of \(10\) decimal digits.

Don’t Be Evil

  1. Changing a page’s HTML and CSS via Chrome’s Developer Tools only affects your local (cached) copy of a page’s HTML and CSS; it does not affect the HTML and CSS on the server, which other users will continue to see.
  1. This feature allows users (who know about the route) to impersonate (i.e., log in as) other users, without knowing their passwords.

  1. An adversary might have a form on their site that submits to your site via POST, a la:

    <form action="https://www.example.com/buy" method="post">
    <input name="shares" type="hidden" value="1">
    <input name="symbol" type="hidden" value="NFLX">
    <input type="submit" value="mwah ha ha">
</form>

    An adversary might even have a form on their site that submits automatically to your site via POST using JavaScript, a la:

    <form action="https://www.example.com/buy" method="post">
    <input name="shares" type="hidden" value="1">
    <input name="symbol" type="hidden" value="NFLX">
    <input type="submit" value="mwah ha ha">
</form>
<script>
    document.querySelector('form').submit();
</script>

    Or no form at all, using Ajax instead:

    <script>
    $.post('https://www.example.com/buy', {shares: 1, symbol: 'NFLX'});
</script>
  1. Code can do anything on your computer that you can do, including delete files and worse. If that code is compiled, you can’t (easily) see what it might do. And even if you compile innocuous code that itself doesn’t do anything bad, the compiler you use to compile it might very well inject malicious code into it!

Finsta

  1. Whereas id is a 4-byte INTEGER, username is TEXT, the values of which might take up more space and thus be slower to search. And if Instagram wants to let users change their usernames, it’s faster (and less redundant) to update usernames in one table than in multiple tables, as might happen if they were used as primary and foreign keys.
  1. SELECT message FROM messages
WHERE sender = (SELECT id FROM users WHERE username = '@harvard')
AND recipient = (SELECT id FROM users WHERE username = '@yale')

  1. DELETE FROM messages WHERE id = 1636;
  1. Instagram could add a column to messages called, e.g., unsent, the default value of which is 0, which could be set to 1 when a message is unsent.
  1. UPDATE messages SET unsent = 1 WHERE id = 1701;

  1. Instagram could remove recipient from messages and instead create a new table, recipients, each of whose rows associates a message with a receipient:

    CREATE TABLE recipients (
    message_id INTEGER,
    user_id INTEGER,
    FOREIGN KEY(message_id) REFERENCES messages(id),
    FOREIGN KEY(user_id) REFERENCES users(id)
);

    Multiple rows (with the same message_id) could thus associate a message with multiple recipients.

Flaskless

  1. def parse(url):

    # Keep track of parameters
    args = {}

    # Check for "?"
    if "?" not in url:
        return [url, args]

    # Limit search to just query string
    path, query_string = url.split("?")

    # Iterate over parameters
    for param in query_string.split("&"):
        field, value = param.split("=")
        args[field] = value

    # Return path and parameters
    return [path, args]

  1. def render_template(template, args):

    # Open template
    with open(template) as f:

        # Read template
        html = f.read()

        # Iterate over args
        for arg in args:
            html = html.replace("{{ " + arg + " }}", args[arg])

        # Return HTML
        return html

Getting Input

  1. Just like swap in Week 4, the input to scanf must be passed by reference (i.e., address) rather than by value (i.e., copy) so that scanf can actually modify its value.
  1. No. If a user inputs an integer larger than 2147483647 (which is \(2^{31} - 1\)), n will overflow within scanf, before the function’s condition is even checked.
  1. While this implementation allocates space for s (which is a pointer), it doesn’t actually allocate space for any characters. And this implementation doesn’t even initialize s to NULL, in which case its value is unknown (i.e., garbage). As a result, scanf will try to store characters at an unknown location in memory, none of whose subsequent bytes have been allocated for that purpose, thereby triggering segmentation faults.
  1. Even if this implementation had allocated a buffer of bytes for characters (as via malloc) and assigned s the address of the first byte, the user might still input more characters than there are bytes, overflowing the buffer, in which case the function might still trigger segmentation faults.
  1. You could first allocate a buffer of some size with malloc. You could then use getchar to get the user’s input one character at a time, growing the buffer with realloc as needed in order to fit each additional character. You could then NUL-terminate the buffer and return the address of its first character, instead returning NULL if malloc or realloc return NULL at any point.
  1. Whereas scanf doesn’t know the size of the buffer passed in as its input (and might thus write beyond its boundary), getchar only gets and returns one character at a time, which can be safely stored in a single char. The caller (e.g., get_string) can then decide whether it needs to (try to) allocate more memory to store that char along with others already read.

Happy Cats

  1. document.addEventListener('DOMContentLoaded', function() {
    window.setInterval(function() {
        document.querySelector('#count').value++;
    }, 1000);
});

  1. document.addEventListener('DOMContentLoaded', function() {
    document.querySelector('#cat').addEventListener('click', function() {
        document.querySelector('audio').play();
    });
});

Logical Questions

  1. This circuit outputs a 1 when both inputs are 0. Under all other circumstances, the circuit outputs a 0. This is also known as a NAND operation.
  1. This circuit outputs a 1 when both inputs are the same (in other words, both 1s or both 0s).
  1. This circuit outputs a 1 when both inputs are different (when A is 1 and B is 0, or when A is 0 and B is 1). This is also known as an XOR (exclusive or) operation.

Nom Nom Nom

  1. Even in incognito mode, your computer will still send your IP address to LinkedIn, and your browser will still send HTTP headers like User-Agent (which identifies your OS and browser and versions thereof). If LinkedIn thus sees similar requests within a narrow window of time, some with cookies and some without, they might infer that the requests are from the same user.
  1. If first-party cookies are disabled, websites that rely on them to implement sessions might no longer be able to remember that a user is logged in or that users have items in their shopping carts.
  1. Third-party cookies can be used to track users. For instance, if two websites, A and B, embed advertisements from ad.doubleclick.net (which sets a cookie), and a user visits A followed by B, then the advertiser will know that the user has visited both of those websites because when the user visits B, the advertiser will see the same cookie that it set when the user visited A!
  1. Duo is likely trying to set a third-party cookie when a user checks that box, to remember that a user has checked it. But because Safari and Brave are blocking that cookie, Duo never sees the value of its Set-Cookie header again, unable as a result to remember who has checked that box.

Programming in B

  1. function or($a, $b)
{
    if ($a)
    {
        return(true)
    }
    if ($b)
    {
        return(true)
    }
    return(false)
}

  1. function and($a, $b)
{
    if ($a)
    {
        if ($b)
        {
            return(true)
        }
    }
    return(false)
}

  1. function remainder($a, $b)
{
    return(subtract($a, multiply(divide($a, $b), $b)))
}

  1. function meow($n)
{
    if (greater($n, 0))
    {
        print("meow")
        meow(subtract($n, 1))
    }
}