ICS 33 Fall 2024, Exercise Set 3

Problem 1 (3 points)

This week, we introduced Databases and, more specifically, relational databases and the SQLite database management system that implements them, along with SQL, the language used to interact with them. Whenever we learn a new technology, we need to start by experimenting first with the basics, and then climbing to gradually greater heights as we gain each foothold. For SQL and SQLite, our best bet is to have a database to experiment with, so I've created one for us to use as the basis of that experimentation; you'll find it linked below.

problem1.db

The database is made up of four tables that describe four kinds of things:

A collection of employees. (The employees' names were generated randomly, using the Random Name Generator provided by Behind the Name.)
An indication of which employees have which other employee as their manager. (Each employee, except the chief executive officer, has exactly one manager.)
A collection of departments in which employees can be members.
The memberships of employees in departments.

The details of the tables' structures are probably best described by the SQL used to create them, which is as follows.


CREATE TABLE employee(
    employee_id INTEGER NOT NULL PRIMARY KEY,
    name TEXT NOT NULL CHECK (length(name) > 0),
    title TEXT NOT NULL CHECK (length(title) > 0)
) STRICT;

CREATE TABLE employee_manager(
    employee_id INTEGER NOT NULL UNIQUE,
    manager_id INTEGER NOT NULL,
    PRIMARY KEY (employee_id, manager_id),
    FOREIGN KEY (employee_id) REFERENCES employee(employee_id),
    FOREIGN KEY (manager_id) REFERENCES employee(employee_id),
    CHECK (employee_id <> manager_id)
) STRICT;

CREATE TABLE department(
    department_id INTEGER NOT NULL PRIMARY KEY,
    name TEXT NOT NULL UNIQUE CHECK (length(name) > 0)
) STRICT;

CREATE TABLE membership(
    employee_id INTEGER NOT NULL,
    department_id INTEGER NOT NULL,
    PRIMARY KEY (employee_id, department_id),
    FOREIGN KEY (employee_id) REFERENCES employee(employee_id),
    FOREIGN KEY (department_id) REFERENCES department(department_id)
) STRICT;

Getting started

Start this problem by downloading the provided database and executing SQL queries against it. One way to do that is to use the sqlite_shell.py script provided along with the Databases notes. Try writing some queries — it doesn't matter much what they are, just that you start with some "finger exercises," especially if you've never written SQL queries before. Take a look at the data, so you get a sense of what you're looking at. How many employees are there? How many departments are there? Pick an employee: Who has that employee as their manager?

The problem

Now that you've gotten a foothold, write SQL queries that answer the following questions about the data in the database. We're not asking you what the data is; we're asking you to write the SQL queries that find the answers to these questions. Note that, by "SQL query," we mean a single SELECT statement; that's all you should be writing in your solution to each part.

What is the job title held by Constantin Phelps?
What are the names of the employees in the department named Sales?
What are the names of the employees who report to Athina Muto?

We will not be pre-grading your work on these, which means we will not be willing to answer a question such as "Is my query correct?" or "What is the right output data for this query?" Part of what this problem is asking you to do is to use the database to determine these things on your own — including the determination of whether a query's output is correct — as you would do if you were working on a problem like this outside of coursework. One of the central problems when working with a database is building an understanding of its underlying data.

What to submit

Submit one PDF named problem1.pdf, which contains your three SQL queries and nothing else.

Problem 2 (3 points)

In this problem, you'll strengthen your abilities to write Comprehensions in Python, by writing three functions, each of which has a body that consists only of a return statement whose expression is a comprehension. The three functions you'll need to write are as follows.

A function multiples that accepts two arguments, count (a positive integer) and multiplier (any number), and returns a list containing exactly count values, each of which is a multiple of multiplier (i.e., the first value is multiplier, the second value is multiplier * 2, and so on).
```
>>> multiples(5, 6)
    [6, 12, 18, 24, 30]
>>> multiples(3, 5.5)
    [5.5, 11.0, 16.5]
>>> multiples(4, complex(1, 1))
    [(1+1j), (2+2j), (3+3j), (4+4j)]
```
A function with_non_zero_lengths that accepts zero or more positional arguments, and returns a dictionary whose keys are those arguments and whose values are the lengths of those arguments, excluding any objects whose lengths are zero.
```
>>> with_non_zero_lengths()
    {}
>>> with_non_zero_lengths('Boo', 'is', 'happy')
    {'Boo': 3, 'is': 2, 'happy': 5}
>>> with_non_zero_lengths(range(3), range(0), range(1))
    {range(0, 3): 3, range(0, 1): 1}
```
A function make_diagonal that takes one positive integer argument n and returns a two-dimensional list with n rows and n columns, in which all elements are None except the elements on the diagonal (i.e., the first column of the first row, the second column of the second row, and so on), which contain the string 'B' instead.
```
>>> make_diagonal(1)
    [['B']]
>>> make_diagonal(3)
    [['B', None, None], [None, 'B', None], [None, None, 'B']]
```

To be clear about the pattern we're after here, all three of your functions will need to look something like this when you're done.


def do_something(...):
    return ________

with the function's name changed to the correct one, the ... replaced by whatever parameters you think are appropriate, and the ________ replaced with a Python expression that is a comprehension.

Notably, it is not necessary to type-check the parameters in any way; if they don't meet the stated requirements, it's fine to let them cause whatever failure is natural in that circumstance.

Limitations

The Python standard library is entirely off-limits in this problem. Your functions must not require any module to be imported.

What to submit

Submit one Python script named problem2.py, which contains your three functions and nothing else. Neither docstrings, comments, nor type annotations are required, since we've all agreed already on what problems we're solving here.

There is no credit being offered for writing automated tests — though you certainly might want to, since that's a great way to ensure that your code works as you expect — and we'd prefer you not submit them even if you do.

Problem 3 (2 points)

In our conversation about Comprehensions, we discussed what it means for an object to be hashable, and noted that sets are not permitted to store objects that are unhashable. Dictionaries present an interesting variant of the same rule, which is that their keys must be hashable, but their values can be anything we'd like them to be, hashable or not.

Given what we discussed, what do you think is the reason for this rule? In particular, why is it permissible for the values in a dictionary to be unhashable, even if its keys must be hashable?

What to submit

Submit one PDF named problem3.pdf, which contains your answer to this question.

Problem 4 (2 points)

In this course, we're concerning ourselves not just with how things work, but also with how well things work, which means we've started taking costs like running time and memory usage into account explicitly, by using asymptotic analysis to quantify it.

During our conversation about Comprehensions, we saw that Python offers dictionary comprehensions, which allow us to construct dictionaries and their contents — their keys and values — in a single expression. Convenience is nice, but we also have to be aware of whether there are costs involved that we might not be willing to pay.

What is the closest-fit O-notation for the time required for a dictionary comprehension to construct a dictionary containing n keys and their associated values? (It's fair to assume that the keys are hashable and unique.) In no more than three of four sentences, explain why you think this is true; we're as interested in your explanation as we are in your answer, though you'll need to stay on message here (i.e., irrelevant information will be viewed as unfavorably as incorrect information).

What to submit

Submit one PDF named problem4.pdf, which contains your answer to this question.

Deliverables

In Canvas, you'll find a separate submission area for each problem. Submit your solution to each problem into the appropriate submission area. Be sure that you're submitting the correct file into the correct area (i.e., submitting your Problem 1 solution to the area for Problem 1, and so on). Under no circumstances will we offer credit for files submitted in the incorrect area.

Submit each file as-is, without putting it into a Zip file or arranging it in any other way. If we asked for a PDF, for example, all we want is a PDF; no more, no less. If you submit something other than what we asked for (e.g., a text file when we asked for a PDF, even if its filename ends in .pdf), we will not be offering you any credit on the submission. There are no exceptions to this rule.

Of course, you should also be aware that you're responsible for submitting precisely the version of your work that you want graded. We won't regrade an exercise simply because you submitted the wrong version accidentally.

Can I submit after the deadline?

Unlike some of the projects in this course, the reinforcement exercises cannot be submitted after the deadline; there is no late policy for these. Each is worth only 2% of your grade, with the lowest score dropped — see the Reinforcement Exercises page for details — so it's not a disaster if you miss one of them along the way.

You're responsible for making a submission in order to receive credit, which means you'll want to be sure that you've remembered to submit your work and verify in Canvas that it's been received. A later claim of having forgotten to submit your work or having misremembered the due date will not be grounds for a resubmission under any circumstances.

What do I do if Canvas adjusts my filename?

Canvas will sometimes modify your filenames when you submit them (e.g., by adding a numbering scheme like -1 or a long sequence of hexadecimal digits to its name). In general, this is fine; as long as the file you submitted has the correct name prior to submission, we'll be able to obtain it with that same name, even if Canvas adjusts it.