6W1 Summer 2016

Class Notes     What's Due?

Fri Jun 16
End of semester: "This is the moment...".

Final Exam: here (answers to be posted late tonight).

Lindley Hall 102 shortly into our last exam:

Illustration of QuickSort from a make up exam earlier today:

(qsort (list 4 2 3 1 5 4 3 6 2 3)) = 

(append (qsort (list 4 2 3 1 2 3))
        (list 4)
        (list 5 6))                =

(append (append (qsort empty)
                (list 1)
                (qsort (list 4 2 3 2 3)))
        (list 4)
        (append (qsort (list 5))
                (list 6)
                (qsort empty)))    =

(append (append empty 
                (list 1)                
                (append (qsort (list 2 2 3))
                        (list 3)
                        (qsort (list 4))))
        (list 4)
        (append (list 5)
                (list 6)
                empty))            = 

(append (append empty 
                (list 1)                
                (append (append (qsort (list 2))
                                (list 2) 
                                (qsort (list 3)))
                        (list 3)
                        (list 4)))
        (list 4)
        (append (list 5)
                (list 6)
                empty))            = 

(append (append empty 
                (list 1)                
                (append (append (list 2)
                                (list 2) 
                                (list 3))
                        (list 3)
                        (list 4)))
        (list 4)
        (append (list 5)
                (list 6)
                empty))            = 

(append (append empty 
                (list 1)                
                (append (list 2 2 3)
                        (list 3)
                        (list 4)))
        (list 4)
        (list 5 6))                = 

(append (append empty 
                (list 1)                
                (list 2 2 3 3 4))
        (list 4)
        (list 5 6))                =

(append (list 1 2 2 3 3 4)
        (list 4)
        (list 5 6))                = 

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

Thu Jun 15
Here are the notes as we wrote them in class today.

Wed Jun 14
Here are the answers to the first four problems on the review sheet.

Here are the answers to the next six problems on the review sheet.

Answers to problems 11, 12 and 13 on the final exam review sheet.

Problems 14 and 15 from the final exam review sheet.

Problem 16 from the final exam review sheet.

Problems 17 and 18 from the final exam review sheet.

Sent over to the class distribution list just now:

From: German, Dan-Adrian
Date: Wed, Jun 14, 2017 at 11:59 AM
Subject: final exam prep
To: c211 6w1 sum 2017
Cc: me 

As discussed today in lecture preparation for the final exam should include:

(a) reviewing any older assignment turned in or not
(b) homework 10
(c) the study guide posted
(d) the sample final examposted

Please respond to this message by the end of the day today (11:59pm) with the following

(a) your expectations for the final

(b) a short list of things/problems you'd like me to go over tomorrow (during the last lecture)

We will continue holding office hours (including the extended 7-8pm LH125 office hours) through Friday evening. 

Adrian German 

Here are the notes as we wrote them in class today.

Tue Jun 13
Lecture notes as we wrote them in class today.

Today's blackboard (click to enlarge):

Sent just now to the email distribution list:

final exam review (solutions)
from: german, dan-adrian
when: tue 6/13/2017 12:12 pm
show all 35 recipients: no. 

​​​Just a quick note to let you know I posted the answers to all the problems on the 
final exam review. Find them (where else?) on the What's New? for tomorrow 6/13 in 
groups (six links overall). I will continue to have extra office hours daily 7-8pm 
in LH125 for makeups and general help. If you have questions or need any kind of help 
with Homework 10 or anything else please let me know. 

Adrian German

Mon Jun 12
The notes as we wrote them in class today.

Grades for Lab 18 and Exam 05 have been posted.

Exam 05 average quite high (among test takers): 88.82 as some of you predicted.

Grades for Homework 07 (solution proposed by Jonathan) being uploaded now.

Sun Jun 11
Grades for Lab 16 and Exam 04 have been posted.

(Averages: 65.48 (subst), 58.33 (discard-first) and 61.90 (overall)).

Pretty low for two problems discussed in class and at the help session.

Grades for Lab 17 (solutions) have now been posted.

Grades for Homework 06 (here's a solution) have been posted now.

Grades for Homework 08 (solution) have been posted.

Grades for Homework 09 (solution) posted.

Sat Jun 10
If you want to read about Mindset and Carol Dweck.

Grades for Lab 11 (solutions) now complete.

Grades for Lab 12 (solutions) now posted.

Grades for Lab 14 (solutions) have been posted now.

Grades for Lab 15 (solutions) posted.

Fri Jun 09
No answers will be posted for Exam 05.

Here's the C211 Final Exam from the Fall semester of 2014.

Here's a typical C211 Final Exam review.

And here's (essentially) your Homework 10 (and last).

I will retype it and post it separately soon.

The anonymous survey from yesterday (last for this semester).

Alernative answers to Lab 15 (using nested maps).

Thu Jun 08
Here's the Tower of Hanoi exercise we played today.

Here's what it led to (switch to ASL for this):

; tower of hanoi
(define (hanoi size start middle end)
  (cond ((= size 1) (begin (display (string-append "move disk from " start " to " end)) (newline)))
         ; this is the bottom, the fixed point, the base case
        (else (begin
                (hanoi (- size 1) start end middle) ; delegate to a contractor (a smaller problem)
                (begin (display (string-append "move disk from " start " to " end)) (newline)) ; make your move
                (hanoi (- size 1) middle start end)))) ; delegate the last part (smaller problem) like before

This week we discussed QuickSort:

(define (q-sort lon)
  (cond ((empty? lon) lon) ; empty list is sorted already 
        ((empty? (rest lon)) lon) ; one element list sorted too 
        (else (let ((pivot (list-ref lon (quotient (length lon) 2)))) ; choose a pivot
                (let ((leq (remove pivot (filter (lambda (elem) (<= elem pivot)) lon))) ; create lists
                      (gt (filter (lambda (elem) (> elem pivot)) lon))) ; via filtering (thanks ISL!)
                  (append (q-sort leq) (list pivot) (q-sort gt))))))) ; then recur and combine 

(check-expect (q-sort '(4 2 6 4 1 5 3 3 7 2)) (list 1 2 2 3 3 4 4 5 6 7))
We also discussed permutations:
; subtract-from : [ListOf Atom] Number -> [ListOf Atom]
; returns the list without the element at valid index index
(define (subtract-from los index)
  (cond ((zero? index) (rest los))
        (else (cons (first los) (subtract-from (rest los) (sub1 index))))))
(check-expect (subtract-from '(a b c d e f) 2) '(a b d e f))
(check-expect (subtract-from '(a b c) 0) '(b c))
(check-expect (subtract-from '(a b c d) (sub1 (length '(a b c d)))) '(a b c))

; perm : [ListOf Atom] -> [ListOf [ListOf Atom]]
; calculates and returns all permutations of its input
(define (perm los)
  (cond ((empty? los) (list empty))
        ((list? los) (apply append
                            (map (lambda (index)
                                   (map (lambda (x)
                                          (cons (list-ref los index) x))
                                        (perm (subtract-from los index))))
                                 (build-list (length los)
                                             (lambda (x) x)))))
        (else (error "Bad input."))))

(check-expect (perm '()) '( () ))

(check-expect (perm '(a)) '((a)))

(check-expect (perm '(a b)) '((a b) (b a)))

(check-expect (perm '(a b c)) '((a b c) (a c b) (b a c) (b c a) (c a b) (c b a)))

Wed Jun 07
Here's a picture of Yibo with today's blackboard:

Here are today's questions (minute paper as distributed in class).

Furthermore here's what we typed today.

Tue Jun 06
Notes as we wrote them in class today.

The board of today (click to enlarge, has map for generation of permutations):

Answers to Lab 15 will be posted here today.

Answers to Homework 08 will be posted here today.

Answers to Exam 04 will be posted here today.

Study Guide for Exam 05 will be posted here today.

Answers to Homework 06 will be posted here today.

Homework 10 and the Study Guide for the Final Exam to be posted today as well.

Pairs that were established yesterday:

  • John - Jonathan
  • Aining - Katherine
  • Manuel - Daniel R
  • Joel J - Robert B
  • Yibo - Kristopher

Remember, if you change your mind new pairs can be formed.

Here are some materials prepared by Jeremiah for his lab yesterday:

For each one right click, Save as ..., then open with DrRacket.

Mon Jun 05
Lab 17 posted, Homework 09 updated with an example.

Notes as we wrote them in class today.

To answer the last question from lecture today compare this with what we wrote in class:

;  cross : [ListOf [ListOf Atom]] -> [ListOf [ListOf Atom]]
;  produces the cartesian product of its inputs
; (define (cross lol)
;   (cond ((empty? lol) ...)
;         ((list? lol) (... (first lol) ... (cross (rest lol)) ...))
;                                           ^ what's the promise here?
;         (else "Bad input.")))
(define (cross lol)
  (cond ((empty? lol) lol)
        ((empty? (rest lol)) (map list (first lol))) 
                             ; one extra wrinkle when dealing with the fixed point 
        ((list? lol) (apply append ; a-ha! did you see that?
                            (map (lambda (promise-elem)
                                   (map (lambda (first-elem)
                                          (cons first-elem promise-elem))
                                        (first lol)))
                                 (cross (rest lol))))) ; see how I build on the promise?  
                     (else "Bad input")))

(check-expect (cross empty) empty)

(check-expect (cross '((1 2 3)))
              (list (list 1) (list 2) (list 3)) )

(check-expect (cross '((1 2 3)  (a b)))
              (list (list 1 'a) (list 2 'a) (list 3 'a) (list 1 'b)
(list 2 'b) (list 3 'b)))

 (cross '((1 2 3) (a b) (+ -)))
  (list 1 'a '+)
  (list 2 'a '+)
  (list 3 'a '+)
  (list 1 'b '+)
  (list 2 'b '+)
  (list 3 'b '+)
  (list 1 'a '-)
  (list 2 'a '-)
  (list 3 'a '-)
  (list 1 'b '-)
  (list 2 'b '-)
  (list 3 'b '-)) )
The board from today:

Sun Jun 04
I'm not posting any answers to Exam 04 before you turn your self-assessments in.

And here's why if this still needs to be explained:

"Critical thinking is thinking that assesses itself. To the extent that our students need us to tell them how well they are doing, they are not thinking critically. Didactic instruction makes students overly dependent on the teacher. In such instruction, students rarely develop any perceptible intellectual independence and typically have no intellectual standards to assess their thinking with. Instruction that fosters a disciplined, thinking mind, on the other hand, is 180 degrees in the opposite direction." (Read more).
Not to mention that one of the problems was worked out on Thu night at the study session and posted afterwards and the other one (subst) is very similar to another one that was also worked out and posted that night too (discard-all: put the new where you discard the old).

Reading assignments for the rest of the course:

I'm on the road today (driving to and from Ann Arbor, MI), so I'm going to be slow with e-mail.

Sat Jun 03
Whoever told you that Computer Science is easy lied to you. Computer Science is not easy, but it is a lot of fun. It is precisely the ability to overcome obstacles that makes it so much fun. It requires discipline, commitment and hard work. It requires that you build the ability to know when you're right and when you're wrong. The fun is all at the end of each accomplishment. Everybody can succeed that is willing to plan accordingly for it!

Yesterday Kristopher stopped by and we worked out this from Exam 04 study guide:

; A SEx is one of:
;   -- Atom 
;   -- [ListOf SEx]
; depth: SEx -> Number
; determines depth of its input
; examples: (depth 3) is 0
;           (depth empty) is 1
;           (depth '(1 2 3)) is 1
;           (depth '(1 (((3 4 5) 6)) 7 8 (9))) is 4
;           (depth '((1 2 (3)) (1 2) 3)) is 3
(define (depth sex)
  (cond ((atom? sex) 0)
        ((empty? sex) 1)
        ((list? sex) (add1 (apply max (map depth sex))))
        (else (error "Bad input."))))

(define (atom? sex)
  (or (number? sex)
      (symbol? sex)
      (string? sex)))

(check-expect (depth 3) 0)
(check-expect (depth '()) 1)
(check-expect (depth '(())) 2)
(check-expect (depth '((()))) 3)
(check-expect (depth '((1 2 (3)) (1 2) 3)) 3)
(check-expect (depth '(1 (((3 4 5) 6)) 7 8 (9))) 4)
(check-expect (depth '(1 2 3)) 1)

Fri Jun 02
Exam 04 in class today continues in lab.

We plan to have two lab assignments and one homework next week.

We plan one more lab and one more homework for the week after.

If you're feeling too tired to work click here.

Here's what we worked during the help session last night.

Thu Jun 01
Notes as we wrote them in class today.

Help Session in LH030 @7pm today.

Today's board (click to enlarge):

Here are the answers collected today in class.

Wed May 31
Resources updated (with two more books), study guide for Exam 04 posted.

Notes as we wrote them in class today (addressed today's lab a tiny bit).

Tue May 30
Notes as we wrote them in class today.

Reminder: from now on your assignments need to contain

  • your name/username inside the .rkt file you submit
  • along with a brief self-assessment (as originally asked)

Failure to provide these will result in points being taken off.

Recall you need to use the design recipe every time you design/define a function. You need to write down your data representation, examples, signature(s), purpose statement(s), templates etc. Your self-assessment starts with your check-expects. These will appear in two distinct flavors during your development: (a) examples you come up with before you write the template and (b) actual check-expect statements for after you finish implementing the function.

Homework 05 graded, solution will be posted here soon.

Exam 03 graded, average score was 78.59; by problem averages were:

  1. sum: 93.91 (apparently easiest)
  2. largest: 86.96 (third easiest, tied)
  3. remove-odds: 86.30 (third easiest, tied)
  4. sort: 83.04 (some avoided the predicate)
  5. throw-dice: 75.96 (third hardest)
  6. extract: 52.30 (apparently hardest)
  7. foldl vs foldr: 61.09 (apparently second hardest)
  8. build-list: 89.13 (second easiest)

Please come pick up your exams from me at your earliest convenience.

Mon May 29
Memorial Day today, no classes.

If you want to meet with me today please e-mail me.

Sat-Sun May 27-28
I am in Ann Arbor, MI, accessible by e-mail, returning Sunday night.

Fri May 26
Exam 03 as administered in class today.

Weekly survey of thoughts collected yesterday in class.

Thu May 25
Starting today (effectively replacing his office hours)
  • Jeremiah will hold a help/PLTL session
  • in LH125 from 7-8pm (every Tue and Thu).

The notes as we wrote them in class today.

No new lab assignment today. Review for Exam, work on homework.

We will still take attendance in lab. Lecture notes contain review problems.

Here's a simple exercise worked out with Yibo after class yesterday.

As always with .rkt files right click, save file as..., then open with DrRacket.

Wed May 24
We don't have class on Monday 5/29 (Memorial Day).

Exam 02 stats:

  • Overall average: 85.93
  • Problem 1 average: 81.17
  • Problem 2 average: 93.61
  • Problem 3 average: 83.00

Individual grades have been posted in Canvas.

Notes as we wrote them in class today.

Tue May 23
Seating for today please. Notes as written in class.

Here are the answers we collected last Thu in class (anonymous survey).

Here's the board from yesterday:

I'll post all answers to all questions in that set (and more) soon.

Also, remember: Homework 05 is in many regards very much like Lecture 08 (05/18).

The videos from YouTube that Jeremiah pointed in Canvas:

These are all that I could find, for a total of about 80 minutes, and in order of their upload.

Mon May 22
Here are solutions to Homework 04 (click link, see code).

Here are solutions to Homework 03 (click link, see code).

Here are solutions to Lab 07 (right click, save link as...).

Here are solutions to Lab 08 (right click, save link as...).

For those who tried to solve the first problem in Lab 08 directly:

; avg is the solution posted using sum and number 
; average : ManyString -> Number
; calculates the average word length with just one helped
; wishlist: number : ManyString -> Number
; this function (number) already provided
; same template as number and sum (but not avg!)
(define (average los)
  (cond ((bottom? los) (error "No data."))
        ((bottom? (many-rest los)) (string-length (many-first los)))
        ((many? los) (/ (+ (string-length (many-first los))
                        (* (number (many-rest los))
                           (average (many-rest los))))
                        (number los)))
        (else (error "Bad data."))))

; again avg is provided in the posted .rkt file
(check-expect (avg e02) (average e02)) 
(check-expect (avg e03) (average e03))
(check-expect (avg e04) (average e04))
(check-expect (avg e05) (average e05))
(check-expect (avg e06) (average e06))
(check-expect (avg e07) (average e07))
(check-expect (avg e08) (average e08))
average is the most direct solution and even it uses a helper (number).

A very similar problem is in the synopsis posted 10 days ago.

Sun May 21
Here's the seating for tomorrow, please.

Here are the answers to Lab 06.

Resources page, grades updated.

Sat May 20
The reading assignment for this coming week: Abstraction.

There will be plenty of opportunities to practice the structural recursion template.

Fri May 19
Exam 02 as administered this morning in class.

Solutions to Lab 03 to be posted soon (as we catch up with grading).

Thu May 18
Consider the following data:
(define jungle-patrol
  (cons (make-elephant "Babar")
    (cons (make-elephant "Tantor")
      (cons (make-elephant "Horton")

Here's an illustration according to Aining:

Notice that Horton is holding (that's a cons) onto empty's tail!

Jeremiah's Cheat Sheet for Exam 02 (right-click, save link as...).

Here's our seating for the day. Notes as we wrote them in class today.

Wed May 17
Here's our seating for the day.

Notes as we wrote them in class today.

Here's the Racket file from class today (right click link, then save link as...).

I've updated lecture notes 05/16 with Stepper snapshots to trace the function behavior.

Tue May 16
Here's our seating for the day.

Reading assignment for the week: Arbitrarily Large Data.

Notes as we wrote them in class today.

Sent to the class distribution list just now:

regarding: c211 updates
sent by: german, dan-adrian
when: tue 5/16/2017 9:22 pm

Homework 03 has been posted. It will be discussed in class tomorrow (you need to at 
least do the reading assignment for tomorrow to get started on it). Both Lab 07 and 
Homework 04 to follow shortly. Please read (look through) sections 5.1, 5.2, 5.3, 5.4 from 
Part I: Fixed-Size Data and 8. Lists from Part II: Arbitrary-Sized Data for tomorrow's lecture. 
Also review this program for tomorrow's class (we developed it in class today, I will ask you to 
recreate it in class (in less than five minutes) to earn your attendance points):

; A String is one of:
;   -- ""
;   -- (string-append Letter String)
; We defined Letter earlier.
; Examples: ...
; lengde : String -> Number
; does what string-length does
; (define (lengde word)
;   (cond ((string=? word "") ...)
;         (else ( ... (string-ith 0 word) ... (lengde (substring word 1)) ... ))))
(define (lengde word)
  (cond ((string=? word "") 0)
        (else (+ 1 (lengde (substring word 1))))))
(check-expect (lengde "") 0)
(check-expect (lengde "john") 4)
(check-expect (lengde "alexandra") 9)
(check-expect (lengde "nicholas") 8)

Let me know if you have any questions or need any help. 

Adrian German


Mon May 15
Some stats about the first exam:
Average: 84.94
Standard Deviation: 16.70
Highest Score: 99.71
Lowest Score: 30
Per problem averages were:
Problem 01: 97.50
Problem 02: 89.11
Problem 03: 90.54
Problem 04: 64.04
(60.71 / 61.96 / 55.00 / 79.64 / 78.21 / 52.71 / 60.00)
Problem 05: 83.54
Grades will be posted in Canvas later today.

Notes as we wrote them in class today.

Sun May 14
Here are the solutions to problems on the first exam.

Sat May 13
Schedule of office hours for the TAs:
Jeremiah Mondays 3-5pm LH125
Topher Thursdays 1-2pm BH107 (lab)
Ruifeng Wednesdays 1-2pm BH108 (lab)
Here's also the logistics info regarding lecture teams.

Access is restricted to those enrolled in the class per FERPA regulations.

Fri May 12
Exam today is over sections 1.1 through 1.7, and 2.1, 3.1, 3.2 in Fixed-Size Data.

Sent last night to the class distribution list:

regarding: c211 notes updated
sent by: german, dan-adrian
when: thu 5/11/2017 11:31 pm
to: c211 6w1 summer 2017 distribution list 

I wrote and posted the notes for today (available under May 11 in Class Notes):


There are two examples in it, with a variation on the second example towards the end. 

A link to a .rkt file from Jeremiah's lab is also included. I hope all of this is useful. 

We will see you in class at 10:20am tomorrow for the first exam. I'm sure you will do well.

In the meantime if you have any questions or need any help please let us know. 

Adrian German
Here's the text of the exam administered earlier today.

Thu May 11
Exam One in class tomorrow continues in lab.

Here's Exam One as administered last year.

Notes as we wrote them in class today.

Wed May 10
This class is about systematic design.

There is only one design recipe and it looks like this:

(a) choose a data definition/representation
(b) give examples (you need to build some data by hand)
(c) choose the name of your function
(d) write the signature of your function
(e) write the purpose statement of your function
(f) give some examples (you will write check-expect-like statements)
(g) now write the header of your function and the function template
(h) fill in the template by actually completing the function
(i) actually write the check-expects for testing your function
There are many data representation choices and templates but only one design recipe.

Here's a synopsis of templates originally prepared for H211 Fall 2015.

Notes as we wrote them in class today.

Tue May 09
Notes as we wrote them in class today.

Mon May 08
6W1 Summer Session starts tomorrow, here's our class.

Updated by © Adrian German for C211/A591