ICS 33 Fall 2024, Exercise Set 3 Solutions

Problem 1


SELECT title
FROM employee
WHERE name = 'Constantin Phelps';


SELECT e.name
FROM employee AS e
     INNER JOIN membership AS m ON m.employee_id = e.employee_id
     INNER JOIN department AS d ON d.department_id = m.department_id
WHERE d.name = 'Sales';


SELECT e.name
FROM employee AS e
     INNER JOIN employee_manager AS em ON em.employee_id = e.employee_id
     INNER JOIN employee AS m ON m.employee_id = em.manager_id
WHERE m.name = 'Athina Muto';

Problem 2


def multiples(count, multiplier):
    return [index * multiplier for index in range(1, count + 1)]


def with_non_zero_lengths(*keys):
    return {k: len(k) for k in keys if len(k) != 0}


def make_diagonal(n):
    return [['B' if row == column else None for row in range(n)] for column in range(n)]

Problem 3

There are at least a couple of reasons why keys in a dictionary must be hashable, mirroring similar rules for the elements of sets.

The keys in a dictionary are meant to uniquely identify a correspoding value, which means that a particular key can only have one value associated with it. If keys are unhashable, they also may be mutable, which would allow us to mutate a dictionary's keys after adding them, allowing them to subsequently become duplicates of one another.
The hashes of a dictionary's keys form the basis of a fast algorithm for finding those keys later. If we ask "What is the value associated with the key 'Boo'?" in a dictionary with millions of keys in it, we want that answer to be found in O(1) time (i.e., about as quickly as in a dictionary with ten keys); hashing offers an algorithm that meets that promise.

The values, on the other hand, are not subject to the same requirement, because neither of those things is true of them.

The values of a dictionary do not have to be unique. Any value can be associated with any key at any time, including duplicates.
From a performance perspective, the goal is that we be able to find values quickly given keys, but not the other way around.

Consequently, there's no particular reason to disallow the values from being unhashable (and, by extension, from being mutable). And, in fact, there's usefulness in having them be mutable; for example, we might have a dictionary in which the keys are people's names and the values are lists of other people who are their friends, with those lists changing over time.

Problem 4

An asymptotic analysis of dictionary comprehensions would revolve around understanding what they do behind the scenes, which boils down to this.

Start with an empty dictionary.
One at a time, iterate through key/value pairs and add them to the dictionary.

What are the associated costs of these operations?

It's reasonable to imagine that building an empty dictionary takes O(1) time. Since we don't tell dictionaries "Here's how big you're going to be" when we first create it, the cost of starting with an empty dictionary is not something that will grow as a function of what we plan to do with it later.
Dictionaries are strongly related to sets; in fact, a dictionary is ultimately a set where each element has a value associated with it. So, the act of adding a key and a value to a dictionary is a lot like adding an element to a set: Determine if it's there already, then either add the key and its associated value (if it isn't) or update its value (if it is). Because a dictionary's keys are hashable (like the elements of sets are), we can reasonably assume that checking whether a key exists takes O(1) time — since its hash will determine where it belongs — and that adding a new key also takes O(1) time for the same reason. With a total of n key/value pairs to be added, this would reasonably be expected to take a total of O(n) time.

O(1) + O(n) = O(n), so our closest-fit O-notation here is O(n).