Due at 11:59:59 pm on Tuesday, 12/10/2019.

Starter Files

Download lab11.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

Exceptions

Exceptions allow us to try a chunk of code, and then catch any errors that might come up. If we do catch an exception, we can run an alternative set of instructions. This construct is very useful in many situations.

try:
    <try suite>
except Exception as e:
    <except suite>
else:
    <else suite>
finally:
    <finally suite>

Notice that we can catch the exception as e. This binds the name e to the exception object. This can be helpful when we want to give extra information on what happened. For example, we can print(e) inside the except clause.

Also, we have an optional else case. The else suite is executed if the try suite finishes without any exceptions.

We also have an optional finally clause, which is always executed, whether or not an exception is thrown. We generally don't need to use the else and finally controls in this class.

When we write exception statements, we generally don't just use the class Exception as above. Rather, we figure out the specific type of exception that we want to handle, such as TypeError or ZeroDivisionError. To figure out which type of exception you are trying to handle, you can type purposely wrong things into the interpreter (such as 'hi' + 5 or 1 / 0) and see what kind of exception Python spits out.

Iterators

Remember the for loop? (We really hope so.) The object the for loop iterates over must be an iterable! An iterable is a way of representing explicit sequences (like lists or strings) as well as implicit sequences (like the natural numbers 1, 2, 3, ...).

for elem in iterable:
    # do something

for loops only work with iterables. This means the object you want to use a for loop on must implement the iterable interface. To implement the iterable interface, an object must define an __iter__ method that returns an object that implements the iterator interface. To implement the iterator interface, an object must define a __next__ method to compute and return the next element in the sequence. If the iterator exhausts the sequence, it raises StopIteration to send a signal to indicate that it reaches the end.

An iterable object can create an arbitrary amount of iterator objects. In addition, the iterators are independent of each other; in other words they can have a different position in the sequence.

Here is a table summarizing the required methods of the iterable and iterator interfaces/protocols. Python also has more documentation about iterator types.

In Python, an iterator must also be an iterable. In other words, it must have a __iter__ method that returns itself (with the current state unaltered).

Analogy: an iterable is like a book (one can flip through the pages) and an iterator is a bookmark (saves the position and can locate the next page). Calling __iter__ on a book gives you a new bookmark independent of other bookmarks, but calling __iter__ on a bookmark gives you the bookmark itself, without changing its position at all.

Here is an example of a class definition for an object that implements the iterator interface:

class AnIterator:
    def __init__(self):
        self.current = 0

    def __next__(self):
        if self.current > 5:
            raise StopIteration
        self.current += 1
        return self.current

    def __iter__(self):
        return self

Let's go ahead and try out our new toy.

>>> for num in AnIterator():
...     print(num)
1
2
3
4
5
6

This is somewhat equivalent to running:

t = AnIterator()
t = iter(t) # iter(t) is the same as t.__iter__()
try:
    while True:
        # next(t) is the same as t.__next__()
        print(next(t))
except StopIteration as e:
    pass

Question 1

Implement an iterator class called ScaleIterator that scales elements in an iterable s by a number k.

class ScaleIterator:
    """An iterator the scales elements of the iterable s by a number k.

    >>> s = ScaleIterator([1, 5, 2], 5)
    >>> list(s)
    [5, 25, 10]

    >>> m = ScaleIterator(naturals(), 2)
    >>> [next(m) for _ in range(5)]
    [2, 4, 6, 8, 10]
    """
    def __init__(self, s, k):
        "*** YOUR CODE HERE ***"
        self.s = iter(s)
        self.k = k
    def __iter__(self):
        return self

    def __next__(self):
        "*** YOUR CODE HERE ***"
        return next(self.s) * self.k

Toggle Solution

Use OK to test your code:

python3 ok -q ScaleIterator

Generators

A generator function returns a special type of iterator called a generator object. Such functions can be written using a yield statement:

def <generator_fn_name>():
    <somevariable> = <something>
    while <predicate>:
        yield <something>
        <increment somevariable>

Calling a generator function (a function with a yield statement in it) makes it return a generator object rather than executing the body of the function.

The reason we say a generator object is a special type of iterator is that it has all the properties of an iterator, meaning that:

• Calling the __iter__ method makes a generator object return itself without modifying its current state.
• Calling the __next__ method makes a generator object compute and return the next object in its sequence. If the sequence is exhausted, StopIteration is raised.
• Typically, a generator should not restart unless it's defined that way. But calling the generator function returns a brand new generator object (like calling __iter__ on an iterable object).

However, they do have some fundamental differences:

• An iterator is a class with __next__ and __iter__ explicitly defined, but a generator can be written as a mere function with a yield in it.
• __iter__ in an iterator uses return, but a generator uses yield.

• A generator "remembers" its state for the next __next__ call. Therefore, the first __next__ call works like this:

  1. Enter the function, run until the line with yield.
  2. Return the value in the yield statement, but remember the state of the function for future __next__ calls.

  And subsequent __next__ calls work like this:

  1. Re-enter the function, start at the line after yield, and run until the next yield statement.
  2. Return the value in the yield statement, but remember the state of the function for future __next__ calls.

Use OK to test your knowledge with the following What would Python print questions:

python3 ok -q generators -u --local

def generator():
    print("Starting here")
    i = 0
    while i < 6:
        print("Before yield")
        yield i
        print("After yield")
        i += 1

>>> g = generator()
>>> g # what type of object is this?
______
<generator object ...>
>>> g == iter(g) # equivalent of g.__iter__()
______
True
>>> next(g) # equivalent of g.__next__()
______
Starting here
Before yield
0
>>> next(g)
______
After yield
Before yield
1
>>> next(g)
______
After yield
Before yield
2

Toggle Solution

Trace through the code and make sure you know where and why each statement is printed.

You might have noticed from the Iterators section that IteratorB, which didn't define a __next__ method, failed to run in the for loop. However, this is not always the case.

class IterGen:
    def __init__(self):
        self.start = 5

    def __iter__(self):
        while self.start < 10:
            self.start += 1
            yield self.start

for i in IterGen():
    print(i)

Why does this iterable work without defining a __next__ method?

The for loop only expects the object returned by __iter__ to have a __next__ method. The __iter__ method is a generator function because of the yield statement in the body. Therefore, when __iter__ is called, it returns a generator object, which you can call __next__ on.

Question 2: Scale

Implement the generator function scale(s, k), which yields elements of the given iterable s, scaled by k.

def scale(s, k):
    """Yield elements of the iterable s scaled by a number k.

    >>> s = scale([1, 5, 2], 5)
    >>> type(s)
    <class 'generator'>
    >>> list(s)
    [5, 25, 10]

    >>> m = scale(naturals(), 2)
    >>> [next(m) for _ in range(5)]
    [2, 4, 6, 8, 10]
    """
    "*** YOUR CODE HERE ***"
    for elem in s:
        yield elem * k

Toggle Solution

Use OK to test your code:

python3 ok -q scale

SQL

Setup

For this lab, you're going to move away from Datahub and onto your own machines. You can complete this lab by either installing SQLite onto your computer or use one of the computers in lab using your EECS login information. To find your EECS login information, you can visit the EECS instructional account site.

The simplest way to start using SQLite is to download a precompiled binary from the SQLite website. The latest version of SQLite at the time of writing is 3.23.0, but you can check for additional updates on the website.

Windows

1. Visit the download page linked above and navigate to the section Precompiled Binaries for Windows. Click on the link sqlite-shell-win32-x86-*.zip to download the binary.
2. Unzip the file. There should be a sqlite3.exe file in the directory after extraction.

3. Navigate to the folder containing the sqlite3.exe file and check that the version is at least 3.8.3:

   $ cd path/to/sqlite
   $ ./sqlite3 --version
   3.9.2 2015-11-02 18:31:15 bda77dda9697c463c3d0704014d51627fceee328

Mac OS X Yosemite (10.10) or El Capitan (10.11)

SQLite comes pre-installed. Check that you have a version that's greater than 3.8.3:

    $ sqlite3
    SQLite version 3.8.5

Mac OS X Mavericks (10.9) or older

SQLite comes pre-installed, but it is the wrong version.

1. Visit the download page linked above and navigate to the section Precompiled Binaries for Mac OS X (x86). Click on the link sqlite-shell-osx-x86-*.zip to download the binary.
2. Unzip the file. There should be a sqlite3 file in the directory after extraction.

3. Navigate to the folder containing the sqlite3 file and check that the version is at least 3.8.3:

   $ cd path/to/sqlite
   $ ./sqlite3 --version
   3.9.2 2015-11-02 18:31:15 bda77dda9697c463c3d0704014d51627fceee328

Ubuntu

The easiest way to use SQLite on Ubuntu is to install it straight from the native repositories (the version will be slightly behind the most recent release):

$ sudo apt-get install sqlite3
$ sqlite3 --version
3.8.6 2014-08-15 11:46:33 9491ba7d738528f168657adb43a198238abde19e

Usage

Note: If you downloaded a precompiled binary above, make sure that the sqlite3.exe file is in the same directory as your .sql file. (Extract and move it out from the zip file you downloaded.)

After writing your code in the .sql file, you can test and verify your output on the terminal with one of the two following commands.

1.) Runs your code and then exits SQLite immediately afterwards.

    sqlite3 < lab13.sql

2.) Runs your code and keeps SQLite open for further commands, which is similar to running Python code with the interactive -i flag. You can type .help to see some of the commands you can run.

    sqlite3 --init lab13.sql

To exit out of SQLite after using the second command, you can hit Ctrl-D type .exit or .quit.

SQL Basics

Creating Tables

You can create SQL tables either from scratch or from existing tables.

The following statement creates a table by specifying column names and values without referencing another table. Each SELECT clause specifies the values for one row, and UNION is used to join rows together. The AS clauses give a name to each column; it need not be repeated in subsequent rows after the first.

CREATE TABLE [table_name] AS
  SELECT [val1] AS [column1], [val2] AS [column2], ... UNION
  SELECT [val3]             , [val4]             , ... UNION
  SELECT [val5]             , [val6]             , ...;

Let's say we want to make the following table called big_game which records the scores for the Big Game each year. This table has three columns: berkeley, stanford, and year.

We could do so with the following CREATE TABLE statement:

CREATE TABLE big_game AS
  SELECT 30 AS berkeley, 7 AS stanford, 2002 AS year UNION
  SELECT 28,             16,            2003         UNION
  SELECT 17,             38,            2014;

Selecting From Tables

More commonly, we will create new tables by selecting specific columns that we want from existing tables by using a SELECT statement as follows:

SELECT [columns] FROM [tables] WHERE [condition] ORDER BY [columns] LIMIT [limit];

Let's break down this statement:

• SELECT [columns] tells SQL that we want to include the given columns in our output table; [columns] is a comma-separated list of column names, and * can be used to select all columns
• FROM [table] tells SQL that the columns we want to select are from the given table
• WHERE [condition] filters the output table by only including rows whose values satisfy the given [condition], a boolean expression
• ORDER BY [columns] orders the rows in the output table by the given comma-separated list of columns
• LIMIT [limit] limits the number of rows in the output table by the integer [limit]

Note: We capitalize SQL keywords purely because of style convention. It makes queries much easier to read, though they will still work if you don't capitalize keywords.

Here are some examples:

Select all of Berkeley's scores from the big_game table, but only include scores from years past 2002:

sqlite> SELECT berkeley FROM big_game WHERE year > 2002;
28
17

Select the scores for both schools in years that Berkeley won:

sqlite> SELECT berkeley, stanford FROM big_game WHERE berkeley > stanford;
30|7
28|16

Select the years that Stanford scored more than 15 points:

sqlite> SELECT year FROM big_game WHERE stanford > 15;
2003
2014

SQL operators

Expressions in the SELECT, WHERE, and ORDER BY clauses can contain one or more of the following operators:

• comparison operators: =, >, <, <=, >=, <> or != ("not equal")
• boolean operators: AND, OR
• arithmetic operators: +, -, *, /
• concatenation operator: ||

Here are some examples:

Output the ratio of Berkeley's score to Stanford's score each year:

sqlite> select berkeley * 1.0 / stanford from big_game;
0.447368421052632
1.75
4.28571428571429

Output the sum of scores in years where both teams scored over 10 points:

sqlite> select berkeley + stanford from big_game where berkeley > 10 and stanford > 10;
55
44

Output a table with a single column and single row containing the value "hello world":

sqlite> SELECT "hello" || " " || "world";
hello world

Data

In each question below, you will define a new table based on the following tables.

create table parents as
  select "abraham" as parent, "barack" as child union
  select "abraham"          , "clinton"         union
  select "delano"           , "herbert"         union
  select "fillmore"         , "abraham"         union
  select "fillmore"         , "delano"          union
  select "fillmore"         , "grover"          union
  select "eisenhower"       , "fillmore";

create table dogs as
  select "abraham" as name, "long" as fur, 26 as height union
  select "barack"         , "short"      , 52           union
  select "clinton"        , "long"       , 47           union
  select "delano"         , "long"       , 46           union
  select "eisenhower"     , "short"      , 35           union
  select "fillmore"       , "curly"      , 32           union
  select "grover"         , "short"      , 28           union
  select "herbert"        , "curly"      , 31;

create table sizes as
  select "toy" as size, 24 as min, 28 as max union
  select "mini",        28,        35        union
  select "medium",      35,        45        union
  select "standard",    45,        60;

Your tables should still perform correctly even if the values in these tables change. For example, if you are asked to list all dogs with a name that starts with h, you should write:

select name from dogs where "h" <= name and name < "i";

Instead of assuming that the dogs table has only the data above and writing

select "herbert";

The former query would still be correct if the name grover were changed to hoover or a row was added with the name harry.

In the following questions, update lab11.sql with your solution.

Question 3

Some people just love little dogs. Create a short_dogs table with three columns, name, fur, and size, containing the dogs of height < 40 cm.

-- All short dogs
create table short_dogs as
-- REPLACE THIS LINE
  select name, fur, height as size from dogs
    where height < 40;

Toggle Solution

-- Example:
select name from short_dogs;
-- Expected output:
--   abraham
--   eisenhower
--   fillmore
--   grover
--   herbert

Test your solution with OK:

python3 ok -q short

Question 4

The Fédération Cynologique Internationale classifies a standard poodle as over 45 cm and up to 60 cm. The sizes table describes this and other such classifications, where a dog must be over the min and less than or equal to the max in height to qualify as a size.

Create a size_of_dogs table with two columns, one for each dog's name and another for its size.

-- The size of each dog
create table size_of_dogs as
-- REPLACE THIS LINE
  select name, size from dogs, sizes
    where height > min and height <= max;

Toggle Solution

-- Example:
select name from size_of_dogs where size="toy" or size="mini";
-- Expected output:
--   abraham
--   eisenhower
--   fillmore
--   grover
--   herbert

Test your solution with OK:

python3 ok -q small

Question 5

Create a table by_height that has a column of the names of all dogs that have a parent, ordered by the height of the parent from tallest parent to shortest parent.

-- All dogs with parents ordered by decreasing height of their parent
create table by_height as
-- REPLACE THIS LINE
  select child from parents, dogs where name = parent order by -height;

Toggle Solution

For example, fillmore has a parent (eisenhower) with height 35, and so should appear before grover who has a parent (fillmore) with height 32. The names of dogs with parents of the same height should appear together in any order. For example, barack and clinton should both appear at the end, but either one can come before the other.

-- Example:
select * from by_height;
-- Expected output:
--   herbert
--   fillmore
--   abraham
--   delano
--   grover
--   barack
--   clinton

Test your solution with OK:

python3 ok -q parent_height

Question 6

Create a table tallest that includes the height and name of every dog that shares the 10's digit of its height with at least one other dog and has the highest 1's digit of all dogs that have the same 10's digit.

-- Height and name of every dog that shares height 10's digit  
-- with at least one other dog and has the highest 1's digit of all dogs 
-- that have the same 10's digit
create table tallest as
-- REPLACE THIS LINE
  select max(height), name from dogs group by height/10 having count(*) > 1;

Toggle Solution

-- Example:
select * from tallest;
-- Expected output:
--   28|grover
--   35|eisenhower
--   47|clinton

Explanation: grover is the tallest 20-something dog. eisenhower is the tallest 30-something dog. clinton is the tallest 40-something dog. barack is not included because there are no other 50-something dogs.

Test your solution with OK:

python3 ok -q tallest