Switch to Pensieve:

• Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number (which was in the email that assigned you to this lab).

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

Getting Started

To get help from a TA, If you do not have an in-person TA, you can reach your TA using this Zoom link.

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

Everybody say your name, and then figure out who most recently pet a dog. (Feel free to share dog photos. Even cat photos are acceptable.)

Scheme

Q1: Perfect Fit

Definition: A perfect square is k*k for some integer k.

Implement fit, which takes non-negative integers total and n. It returns whether there are n different positive perfect squares that sum to total.

Important: Don't use the Scheme interpreter to tell you whether you've implemented it correctly. Discuss! On the final exam, you won't have an interpreter.

    ; Return whether there are n perfect squares with no repeats that sum to total

    (define (fit total n)
        (define (f total n k)
            (if (and (= n 0) (= total 0))
                #t
            (if (< total (* k k))
                #f
            (or (f total n (+ k 1)) (f (- total (* k k)) (- n 1) (+ k 1)))
            )))
        (f total n 1))

    (expect (fit 10 2) #t)  ; 1*1 + 3*3
    (expect (fit 9 1)  #t)  ; 3*3
    (expect (fit 9 2)  #f)  ;
    (expect (fit 9 3)  #f)  ; 1*1 + 2*2 + 2*2 doesn't count because of repeated 2*2
    (expect (fit 25 1)  #t) ; 5*5
    (expect (fit 25 2)  #t) ; 3*3 + 4*4

Presentation Time: As a group, come up with one sentence describing how your implementation makes sure that all n positive perfect squares are different (no repeats). Once your group agrees on an answer, pick someone who hasn't presented to the course staff recently to share your group's answer with your TA (in person or on Zoom).

Scheme Lists & Quotation

Scheme lists are linked lists. Lightning review:

• nil and () are the same thing: the empty list.
• (cons first rest) constructs a linked list with first as its first element. and rest as the rest of the list, which should always be a list.
• (car s) returns the first element of the list s.
• (cdr s) returns the rest of the list s.
• (list ...) takes n arguments and returns a list of length n with those arguments as elements.
• (append ...) takes n lists as arguments and returns a list of all of the elements of those lists.
• (draw s) draws the linked list structure of a list s. It only works on code.cs61a.org/scheme. Try it now with something like (draw (cons 1 nil)).

Quoting an expression leaves it unevaluated. Examples:

• 'four and (quote four) both evaluate to the symbol four.
• '(2 3 4) and (quote (2 3 4)) both evaluate to a list containing three elements: 2, 3, and 4.
• '(2 3 four) and (quote (2 3 four)) evaluate to a list containing 2, 3, and the symbol four.

Here's an important difference between list and quotation:

scm> (list 2 (+ 3 4))
(2 7)
scm> '(2 (+ 3 4))
(2 (+ 3 4))

Q2: Nested Lists

Create the nested list depicted below three different ways: using list, quote, and cons.

First, describe the list together: "It looks like there are four elements, and the first element is ..." If you get stuck, look at the hint below. (But try to describe it yourself first!)

Next, use calls to list to construct this list. If you run this code and then (draw with-list) in code.cs61a.org, the draw procedure will draw what you've built.

    (define with-list
        (list
            (list 'a 'b) 'c 'd (list 'e)
        )
    )
    ; (draw with-list)  ; Uncomment this line to draw with-list

Now, use quote to construct this list.

    (define with-quote
        '(
            (a b) c d (e)
        )

    )
    ; (draw with-quote)  ; Uncomment this line to draw with-quote

Now, use cons to construct this list. Don't use list. You can use first in your answer.

(define first
    (cons 'a (cons 'b nil)))

    (define with-cons
        (cons
            first (cons 'c (cons 'd (cons (cons 'e nil) nil)))
        )
    )
    ; (draw with-cons)  ; Uncomment this line to draw with-cons

first ____

'(___ ___ ___)
   c   d  (e)

(cons ___ (cons ___ (cons ___ nil)))
       c         d        (e)

Q3: Pair Up

Implement pair-up, which takes a list s. It returns a list of lists that together contain all of the elements of s in order. Each list in the result should have 2 elements. The last one can have up to 3.

Look at the examples together to make sure everyone understands what this procedure does.

    ;;; Return a list of pairs containing the elements of s.
    ;;;
    ;;; scm> (pair-up '(3 4 5 6 7 8))
    ;;; ((3 4) (5 6) (7 8))
    ;;; scm> (pair-up '(3 4 5 6 7 8 9))
    ;;; ((3 4) (5 6) (7 8 9))
    (define (pair-up s)
        (if (<= (length s) 3)
            (list s)
            (cons (list (car s) (car (cdr s))) (pair-up (cdr (cdr s))))
        ))

    (expect (pair-up '(3 4 5 6 7 8)) ((3 4) (5 6) (7 8)) )
    (expect (pair-up '(3 4 5 6 7 8 9)) ((3 4) (5 6) (7 8 9)) )

Discussion: What's the longest list s for which (pair-up (pair-up s)) will return a list with only one element? (Don't just guess and check; discuss!)

Document the Occasion

Please all fill out the attendance form (one submission per person per week).