HW 7 - Streams, SQL

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/hw/hw07/

Solutions:

• Scheme: https://github.com/tomthestrom/cs61a/blob/master/homeworks/hw07/hw07.scm

• SQL: https://github.com/tomthestrom/cs61a/blob/master/homeworks/hw07/hw07.sql

Streams

Q1: Multiples of 3

Define implicitly an infinite stream multiples-of-three that contains the multiples of 3.

You may use the map-stream function defined below. map-stream takes in a one-argument function f and a stream s and returns a new stream containing the elements of s with f applied.

(define (map-stream f s)
	(if (null? s)
		nil
		(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))

Do not define any other helper functions.

(define (map-stream f s)
    (if (null? s)
    	nil
    	(cons-stream (f (car s)) (map-stream f (cdr-stream s)))))

(define multiples-of-three
  'YOUR-CODE-HERE
)

Q1: Solution

(define multiples-of-three
  (cons-stream 3 (map-stream (lambda (x) (+ x 3)) multiples-of-three))
)

Q2: Run-Length Encoding

Run-length encoding is a very simple data compression technique, whereby runs of data are compressed and stored as a single value. A run is defined to be a contiguous sequence of the same number. For example, in the (finite) sequence

1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of two-element lists:

(1 5), (6 4), (2 1), (5 3)

We will extend this idea to streams. Write a function called rle that takes in a stream of data, and returns a corresponding stream of two-element lists, which represents the run-length encoded version of the stream. You do not have to consider compressing infinite streams - the stream passed in will eventually terminate with nil.

scm> (define s (cons-stream 1 (cons-stream 1 (cons-stream 2 nil))))
s
scm> (define encoding (rle s))
encoding
scm> (car encoding)  ; Run of number 1 of length 2
(1 2)
scm> (car (cdr-stream encoding))  ; Run of number 2 of length 1
(2 1)
scm> (define s (list-to-stream '(1 1 2 2 2 3))) ; Makes a stream with the same elements as the list passed in
scm> (stream-to-list (rle s)) 
((1 2) (2 3) (3 1))

(define (rle s)
  'YOUR-CODE-HERE
)

Q2: Solution

(define (rle s)
    (define (compress strm prev count)
        (if (or (null? strm) (not (= prev (car strm))))
            (cons-stream (list prev count) (rle strm))
            (compress (cdr-stream strm) prev (+ 1 count))
        )
    )
    
    (if (null? s)
        nil
        (compress  (cdr-stream s) (car s) 1))
)

SQL

Q3: Size of Dogs

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.

Q3: Solution

CREATE TABLE size_of_dogs AS
  SELECT dogs.name AS name, sizes.size AS size FROM dogs JOIN sizes WHERE dogs.height > sizes.min AND  dogs.height <= sizes.max;

Q4: By Parent Height

Create a table by_parent_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.

Q4: Solution

-- All dogs with parents ordered by decreasing height of their parent
CREATE TABLE by_parent_height AS
  SELECT parents.child FROM parents JOIN dogs ON dogs.name = parents.parent ORDER BY dogs.height DESC;

Q5: Sentences

There are two pairs of siblings that have the same size. Create a table that contains a row with a string for each of these pairs. Each string should be a sentence describing the siblings by their size.

Q5: Solution

CREATE TABLE siblings AS
  SELECT DISTINCT 
  CASE WHEN p1.child > p2.child THEN p2.child ELSE p1.child END as sibling1,
  CASE WHEN p1.child < p2.child THEN p2.child ELSE p1.child END as sibling2
  FROM parents p1 JOIN parents p2 WHERE p1.parent = p2.parent AND p1.child != p2.child; 
-- Sentences about siblings that are the same size
CREATE TABLE sentences AS
  SELECT siblings.sibling1 || ' and ' || siblings.sibling2 || ' are ' || s1.size || ' siblings'
  FROM siblings
  JOIN size_of_dogs AS s1 ON siblings.sibling1 = s1.name
  JOIN size_of_dogs AS s2 ON siblings.sibling2 = s2.name
  WHERE s1.size = s2.size;

Q6: Low Variance

We want to create a table which contains the total height of all dogs that share a fur type, but only for the fur types where the heights are not spread out too much. To approximate this, we'll only consider the fur types where each dog with that fur is within 30% of the average height of all dogs with that fur.

For example, if the average height for short-haired dogs is 10, then in order to be included in our output, all dogs with short hair must have a height of at most 13 and at least 7.

Your output should first include the fur type and then the total height for the fur types that meet this criteria

Q6: Solution

-- Total size for each fur type where all of the heights differ by no more than 30% from the average height
CREATE TABLE low_variance AS
  SELECT fur AS fur, SUM(height) AS total_height
  FROM dogs
  GROUP BY fur
  HAVING height < (AVG(height) + AVG(height) * 0.3) AND height > (AVG(height) - AVG(height) * 0.3);