This class will be recorded! Its use is limited to members of the class. Please do not share with others.
Approximate overview
Info:
Activities
Mini Projects
Readings
Quizzes
Other
Do we have to know merge sort for SoLA 4?
No, but it may be on SoLA 5. (Probably an approximate trace.)
Why is new-merge-sort n*log_2(n) rather than n+log_2(n)?
Merging all the elements together to make it shorter takes between n/2 and n steps for n elements.
Once with lists of length 1
’((79) (56) (84) (32) (49) (93) (38) (73) (38) (49) (41) (26) (80) (86) (10) (21))
Once with lists of length 2
’((56 79) (32 84) (49 93) (38 73) (38 49) (26 41) (80 86) (10 21)) ; 16 steps
Once with lists of length 4
’((32 56 79 84) (38 49 73 93) (26 38 41 49) (10 21 80 86)) ; 16 steps
….
Once with lists of length n/2
So we do it log_2(n) times. Each time cost n, so the total is n*log_2(n).
Do we have to calculate this on our own?
You should be able to run experiments. (Using counters or print.)
You should be able to hypothesize as to why things are slower/faster.
But precise analysis is not necessary.
Why is this faster?
Old merge sort and new merge sort are about equivalent.
New merge sort is easier to analyze.
Original merge sort is prettier.
Can we analyze divide-and-conquer algorithms by “we divide logn times, it takes ? work each time we divide”.
Sure, for now.
Why do we use kernel?
It’s the traditional name for
helperorgo.
It’s a traditional name for a recursive helper.
Why did we have to check insert-number?
Edge cases!
Get students to find errors in Sam’s code.
What’s going on with the funky let in kernel?
(let kernel ([param1 val1] [param2 val2] ...) ...)“named let”
is shorthand for
`(let ([kernel (lambda (param1 param2 …) ..)]) (kernel val1 val2 ..))
I think it’s fixed in the lab.
Can we talk about tracing tree recursion?
Tomorrow.
You know the drill. However, you won’t need Racket, just your notes from yesterday.
“Quiz for Class 32: Sorting”
Sort alphabetically.
Even though I said “You don’t need to do careful analysis”, we’re going to try an example or two.
;;; (list-append l1 l2) -> list?
;;; l1, l2 : list?
;;; Returns the list formed by placing the elements of l2 after the elements
;;; of l1, preserving the order of the elements of l1 and l2.
(define list-append
(lambda (l1 l2)
(write (list 'list-append l1 l2)) (newline)
(cond
[(null? l1)
l2]
[else
(cons (car l1)
(list-append (cdr l1) l2))])))
;;; (list-reverse l) -> list?
;;; l : list?
;;; Returns l with the elements in the opposite order.
(define list-reverse-1
(lambda (l)
(match l
['()
null]
[(cons x tail)
(list-append (list-reverse-1 tail) (list x))])))
(list-append l1 l2) gets called how many times?
(list-append '(5 4 3 2) '(1))'(2 3 4 5) into '(5 4 3 2), we’ll need (list-append '(5 4 3) '(2))'(3 4 5) into '(5 4 3), we’ll need (list-append '(5 4) '(3))'(4 5) into '(5 4), we’ll need (list-append '(5) '(4))'(5) into '(5), we’ll need (list-append '() '(5))'() into '(), we do nothing.(list-append '() '(5)) : 1(list-append '(5) '(4)) : 2(list-append '(5 4) '(3)) : 3(list-append '(5 4 3) '(2)) : 4(list-append '(5 4 3 2) '(1)) : 5n, we’ll spend 1 + 2 + 3 + 4 + … + n.
(termial n).Computing (termial n) quickly.
There’s a formula. Let’s figure it out.
1 + 2 + 3 + 4 + ... + n-2 + n-1 + n = x
n + n-1 + n-2 + n-3 + + 3 + 2 + 1 = x (addition is comm.)
------------------------------------------- -
n+1+ n+1 + n+1 + ..................... + n+1 = 2x
(n+1)*n = 2x
x = n*(n+1)/2
1 + 2 + 3 .... + 100 = 100*101/2 = 50*101 = 5050.
Why did we do this?
Here’s a sample list.
(define cat (list "c" "a" "t"))
+---+---+ +---+---+ +---+---+
cat --> | * | -----> | * | *----> | * | / |
+-|-+---+ +-|-+---+ +-|-+---+
v v v
"c" "a" "t"
Here’s an attempt to “change” that list (build a new list)
(define hat (cons "h" (cdr cat)))
"h"
^
+-|-+---+
hat --> | * | *--------+
+---+---+ |
v
(cdr cat)
+---+---+ +---+---+ +---+---+
cat --> | * | -----> | * | *----> | * | / |
+-|-+---+ +-|-+---+ +-|-+---+
v v v
"c" "a" "t"
Important issues
cons creates a new listlist still builds a series of cons cells (pairs)letIncorrect comment from some students: “The let introduces a temporary
change to a vector.”
Consider the following code.
;;; (vector-swap! vec i j) -> vec
;;; vector : vector?
;;; i : integer?
;;; j : integer?
;;; Swap the elements at indices i and j of vec, returning the
;;; now-modified vector.
;;; Pre: 0 <= i < (vector-length vec)
;;; Pre: 0 <= j < (vector-length vec)
(define vector-swap!
(lambda (vec i j)
(let ([tmp (vector-ref vec i)])
(vector-set! vec i (vector-ref vec j))
(vector-set! vec j tmp)
vec)))
;;; (vector-something! vec i) -> any?
;;; vec : vector?
;;; i : integer?
;;; Swap elements at positions 0 and i, returning the old value
;;; at position i.
;;; Pre: 0 <= i < (vector-length vec)
(define vector-something!
(lambda (vec i)
(let ([newvec (vector-swap! vec 0 i)])
; Temporary: Verify that the vector changed
(write newvec) (newline)
(vector-ref vec 0))))
What do we expect for the following?
> (define sample (vector "c" "a" "t")
> (vector-something! sample 1)
Output: #("a" "c" "t")
Result: "a"
> sample
; possibly #um or #("a" "c" "t") or #("c" "a" "t")
#("a" "c" "t")
From the last SoLA
Elided
Sam’s predictions
(helper '(7 6 12 4 10 8 5 1) '())
(helper '(6 12 4 10 8 5 1) '(7))
(helper '(12 4 10 8 5 1) '(6 7))
(helper '(4 10 8 5 1) '(6 7 12))
(helper '(10 8 5 1) '(4 6 7 12))
The actual thing
> (numbers-insertion-sort '(7 6 12 4 10 8 5 1))
(helper (7 6 12 4 10 8 5 1) ())
(helper (6 12 4 10 8 5 1) (7))
(helper (12 4 10 8 5 1) (6 7))
(helper (4 10 8 5 1) (6 7 12))
(helper (10 8 5 1) (4 6 7 12))
(helper (8 5 1) (4 6 7 10 12))
(helper (5 1) (4 6 7 8 10 12))
(helper (1) (4 5 6 7 8 10 12))
(helper () (1 4 5 6 7 8 10 12))
Why was alphabetically-first so slow for lists arranged last to first?
;;; (alphabetically-first string) -> string
;;; strings: both (listof string?) nonempty?
;;; Find the alphabetically first string in the list.
(define alphabetically-first-1
(lambda (strings)
; (counter-increment! AFC 'alphabetically-first-1)
(cond
[(null? (cdr strings))
(car strings)]
[(string-ci<=? (car strings) (alphabetically-first-1 (cdr strings)))
(car strings)]
[else
(alphabetically-first-1 (cdr strings))])))
(define alphabetically-first-2
(lambda (strings)
; (counter-increment! AFC 'alphabetically-first-2)
(if (null? (cdr strings))
(car strings)
(first-of-two (car strings)
(alphabetically-first-2 (cdr strings))))))
;;; (first-of-two str1 str2) -> string?
;;; str1 : string?
;;; str2 : string?
;;; Find the alphabetically first of str1 and str2.
(define first-of-two
(lambda (str1 str2)
(if (string-ci<=? str1 str2)
str1
str2)))
Aka: Making your brain hurt a little bit more.
Our normal pattern for tree recursion.
(define tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))
For tree-size,
(define tree-size
(lambda (tree)
(if (empty-tree? tree)
0
(+ 1
(tree-size (btl tree))
(tree-size (btr tree))))))
For tree-sum
(lambda (x) x)(define tree-sum
(lambda (tree)
(if (empty-tree? tree)
0
(+ (btt tree)
(tree-sum (btl tree))
(tree-sum (btr tree))))))
For tree->list
(define tree->list
(lambda (tree)
(if (empty-tree? tree)
null
(append (list (btt tree))
(tree->list (btl tree))
(tree->list (btr tree))))))
Side note: append is the built-in procedure, list-append is what we’ve written.
For tree-increment, which adds 1 to each value in a tree of numbers.
(btn-increment (btn 1 (leaf 5) (leaf 6))) -> (btn 2 (leaf 6) (leaf 7))
(btn-increment empty-tree) -> empty-tree
(define tree-increment
(lambda (tree)
(if (empty-tree? tree)
empty-tree
(btn (+ 1 (btt tree))
(tree-increment (btl tree))
(tree-increment (btr tree))))))
Note; btn is a shorthand for binary-tree, it stands for binary-tree-new or binary-tree-node.
Hmm … we’re doing a lot of boring, repetitive work. Isn’t that what computers are good for?
;;; (make-tree-proc base-case combine process) -> procedure?
;;; base-case : value
;;; combine : procedure?
;;; process : procedure?
;;; Create a procedure for processing trees using the standard template
(define make-tree-proc
(lambda (base-case combine process)
(letrec [(tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))]
tree-proc)))
Does this really work?
Let’s see.
> (define tree-size (make-tree-proc 0
+
(lambda (x) 1)))
> tree-size
#<procedure:tree-proc>
> (tree-size empty-tree)
0
> (tree-size (btn 4 (btn 5 (leaf 6) (leaf 7))
empty-tree))
4
> (define tree-sum (make-tree-proc 0 + (lambda (x) x)))
> (tree-sum (btn 4 (btn 5 (leaf 6) (leaf 7))
empty-tree))
22
> (define tree->list (make-tree-proc null append list))
> (tree->list (btn 4 (btn 5 (leaf 6) (leaf 7))
empty-tree))
'(4 5 6 7)
> (define tree-increment (make-tree-proc empty-tree btn (section + 1 <>)))
> (tree-increment (btn 4 (btn 5 (leaf 6) (leaf 7))
empty-tree))
'(5 (6 (7 ◬ ◬) (8 ◬ ◬)) ◬)
Normally, we use lambda to define procedures. (Except when we use
o or section.) For tree procs, we normally have (lambda (tree) ...).
make-tree-proc includes the lambda for us, and returns the procedure with that lambda implied.
I did say your brain would hurt.
We’ve written a procedure that makes procedures.
Let’s trace the construction of tree-size.
(make-tree-proc 0 + (lambda (x) 1)))
; Grab the body of make-tree-proc
; (letrec [(tree-proc
; (lambda (tree)
; (if (empty-tree? tree)
; base-case
; (combine (process (btt tree))
; (tree-proc (btl tree))
; (tree-proc (btr tree))))))]
; tree-proc)))
; Substitute 0 for base-case, + for combine, (lambda (x) 1 for process
---> (letrec [(tree-proc
(lambda (tree)
(if (empty-tree? tree)
0
(+ ((lambda (x) 1) (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))]
tree-proc)))
; We normally write 1 instead of the ugly
; `((lambda (x) 1) (btt tree))`, but `make-tree-proc` forces us
; to do something with the root. `(lambda (x) 1)` is
; "throw away my parameter and return 1"
;
; We've defined tree-proc has we'd expect tree-size to look.
; The procedure returns tree-proc; we're *not* calling the
; new procedure we defined, we're just returning it.
(define adder
(lambda (n)
(let [(addn (lambda (x) (+ n x)))]
; addn is a procedure that takes one input, x, and adds
; n to x
addn))) ; We've returned a procedure that takes one parameter
> (define add5 (adder 5))
> add5
#<procedure:addn>
> (add5 11)
16
> (add5 10)
15
> (add5 1213)
1218
Not held.