### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

### Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.

You can change this under Settings & Account at any time.

# CS135 Exam Review Session

No description

by

Tweet## Eric Folland

on 14 March 2011#### Transcript of CS135 Exam Review Session

How to use listof properly

Types of recursion and how to determine the type

Local

Lambda

Abstraction and ALFs

Trees

Last office hours

Check your exam seat! CS 135 Exam Review Incorrect: Correct: (list-of-characters)

listof Character

(listof Characters)

(listof lists) (listof Character)

(listof (listof Character)) Pure Structural Examples: ;This example follows the list data definition

(define (pure-structural1 lst)

(cond

[(empty? lst) 0]

[(cons? lst) (add1 (pure-structural1 (rest lst)))]))

;This example follows from the unary definition of a natural number

(define (pure-structural2 n)

(cond

[(zero? n) empty]

[else (cons n (pure-structural2 (sub1 n)))])) Base case

Recursive call gets closer to the base case

Recursion follows the recursion of the data definition Pure Structural with an Accumulator Accumulators vs. "along for the ride" vs. "counters"

Same as Pure Structural, but rather than accumulating on the return result, accumulates on a parameter Examples: ;This example follows the list data definition

(define (pure-structural/acc1 lst items-so-far)

(cond

[(empty? lst) items-so-far]

[(cons? lst) (pure-structural1 (rest lst) (add1 items-so-far))]))

;This example follows from the unary definition of a natural number

(define (pure-structural/acc2 n list-so-far)

(cond

[(zero? n) empty]

[else (pure-structural2 (sub1 n) (cons n list-so-far))])) Generative Still has a base case

Termination argument vs. "one step closer to the base case"

Recursive step does not follow from the data definition Examples: ;This has a chance of terminating each call

(define (generative1 x)

(cond [(zero? x) empty]

[else (cons x (generative1 (random-0-to-9 x)))]))

;This will surely terminate, but is not based on the data definition

(define (generative2 lst)

(cond [(empty? lst) empty]

[else (generative2 (filter (lambda (x) (equal? x (first lst))) lst))])) Scope, binding occurrence

Stepping

When to use it over external helper functions/constants ;Scope example

(define x 5)

(define (f x)

(+ (local [(define x 7)] (+ x 3))

x))

(+ (f 3) (f x)) ;Local stepping example

(define (foo a)

(local [(define x (+ 1 2))

(define y 3)]

(+ x y a)))

(foo (+ 1 2))

;can't call a function until its arguments are simplest form

(foo 3)

;replace the function with its body, subbing in arguments

(local [(define x (+ 1 2))

(define y 3)]

(+ x y 3))

;local's first step is to take out the defines

;replace all instances of those constants with their new name

(define x_0 (+ 1 2))

(define y_0 3)

(+ x_0 y_0 3)

;simplify the first thing first

;also, exclude any defines that are in simplest form. they

; are still there, but not shown

(define x_0 3)

(+ x_0 y_0 3)

;substitute one constant at a time: first x_0

(+ 3 y_0 3)

;now y_0

(+ 3 3 3)

;pre-defined functions happen in one step

9 Local can also be used for readability. If it makes more sense to have a local helper function or local constant, then it should probably be used. Namespace

Efficiency

Readability When creating a very large program or working in a team, there can be a big list of functions. That's why it's important to "hide" helper functions inside of local.

On the other hand, if a helper function is useful for more than one function, it should be outside of local.

The same goes for constants. Something like pi might be useful for many functions, but something specific like sum-so-far should be local. As we've seen before, local can also be used to make a program more efficient, by storing the result of a recursive call in a local constant. This only needs to be done if you will then access that constant more than once afterward. Stepping

When to use lambda

Examples of how to use it ;if we look at a regular function and application

(define (foo x y)

(+ x y))

(foo 1 2)

;here, the first step is replace the function

;name with its body, subbing in all arguments

(+ 1 2)

;and finish

3 ;here is the same starting code, but using lambda.

;there are still 2 parameters, a function body, and 2

;arguments

((lambda (x y) (+ x y)) 1 2)

;the step is logically similar here: replace the

;lambda with the body of the function, subbing in

;all arguments, which are the 1 and 2

(+ 1 2)

;and finish

3 ;this is a similar example, except now foo is a

;constant that holds a function. this is really the

;same as a function, but here we'll have an extra step

(define foo (lambda (x y) (+ x y)))

(foo 1 2)

;now foo is a constant, so, like any constant, it takes

;a step to sub in

((lambda (x y) (+ x y)) 1 2)

;now we continue like the last example

(+ 1 2)

;and finish

3 Use lambda when the code is trivial. It is typically used in abstract list functions like quicksort, map, filter, foldr, foldl, or ones you make yourself.

Although it is possible to use (define foo (lambda (x y) (+ x y))), it is considered more readable to use (define (foo x y) (+ x y)), which is the same. ;when you need a function to produce a function:

(define (foo a)

(lambda (x) (char=? a x)))

;think about what this would do

;notice that this is different from

(define (foo a)

(char=? a __)) ;this wouldn't work

;when you use a function that consumes a function, and

;it's too simple to make it a helper function

(map (lambda (x) (* x 2)) (list 1 2 3 4))

There will be many more examples coming up. quicksort

build-list

map

filter

foldr quicksort requires you to give it a function that consumes two numbers it's trying to compare. Your function should produce true if the first should come before the second.

(define numbers (list 5 2 7 4 1 3))

Sort ascending:

(quicksort numbers <) --> (list 1 2 3 4 5 7)

Sort descending:

(quicksort numbers >) --> (list 7 5 4 3 2 1)

Put even first:

(quicksort numbers (lambda (num1 num2) (even? num1))) --> (list 4 2 5 7 1 3) build-list requires you to give it a function that consumes one number, which will hold the value of each number up to n as it gets called each time. Your function can produce anything, using the number it's given for calculations. Build list always consumes a number and produces a list with that many items.

(define numbers (list 5 2 7 4 1 3))

Make 0 to 9:

(build-list 10 (lambda (x) x)) OR (build-list 10 identity) --> (list 0 1 2 3 4 5 6 7 8 9)

Make 1 to 10:

(build-list 10 (lambda (x) (add1 x))) OR (build-list 10 add1) --> (list 1 2 3 4 5 6 7 8 9 10)

Make even 2 to 20:

(build-list 10 (lambda (x) (add1 (* 2 x)))) --> (list 2 4 6 8 10 12 14 16 18 20)

Make 0 to 4 as lists:

(build-list 10 (lambda (x) (list x))) OR (build-list 10 list) --> '((0) (1) (2) (3) (4)) map requires you to give it a function that consumes one item, which will be each item in the given list and it should return what you want that item to turn into. Unlike build-list, the item consumed doesn't have to be a number. Map always consumes a list and produces a list with the same number of items, but those items are all transformed into something else using the function you give it.

(define numbers (list 5 2 7 4 1 3))

Double each number:

(map (lambda (x) (* 2 x)) numbers) --> (list 10 4 14 8 2 6)

Add 1 to each number:

(map (lambda (x) (add1 x)) numbers) OR (map add1 numbers) --> (list 6 3 8 5 2 4)

Change them all into 'a:

(map (lambda (x) 'a) numbers) --> (list 'a 'a 'a 'a 'a 'a)

filter requires you to give it a function that consumes each item like map, but will produce true or false. True means keep the item and false means don't include it in the new list. filter always consumes a list and produces a list with equal or fewer items.

(define numbers (list 5 2 7 4 1 3))

Keep only even numbers:

(filter even? numbers) --> (list 2 4)

Keep only numbers greater than 4:

(filter (lambda (x) (> x 4)) numbers) --> (list 5 7)

Keep only symbols:

(filter symbol? numbers) --> empty foldr requires you to give it a function that consumes two items: the first of these is each item in the list and the second is the result of calling your function on the rest of the list. Your function should do something to combine the item onto the result of the rest. foldr always consumes a list but can produce anything. It will only produce a list if your function acts like cons. What type it produces depends on the function you give it.

(define numbers (list 5 2 7 4 1 3))

Count the number of items:

(foldr add1 0 numbers) --> 6

Sum the numbers:

(foldr + 0 numbers) --> 22

Make the exact same list:

(foldr cons empty numbers) --> (list 5 2 7 4 1 3)

Double each number:

(foldr (lambda (x y) (cons (* 2 x) y)) empty numbers) --> (list 10 4 14 8 2 6) Recursion for BST

Mutual recursion for a General Tree (Demonstrate on the board)

Searching

Adding a node

Removing a node (Demonstrate on the board)

Searching

Adding a node

Assignment 7 q3 and q4 Thursday

Friday 4-5pm Eric 9-10am Max

10am-12pm Eric

12-1pm Minghao

2pm-3:30 Prof Becker To look up your exam seat:

Go to the course web page --> Exams --> a link in the text that says "look up"

Be sure to read that exams page for more information.

Monday, December 20, 2010 12:30-3:00 PM in the PAC Relax and do your best! :) ;; zip: (listof Any) (listof Any) -> (listof (list Any Any))

(define (zip lst1 lst2)

(cond

[(and (empty? lst1) (empty? lst2)) empty]

[else (cons (list (first lst1) (first lst2))

(zip (rest lst1) (rest lst2)))]))

;; dot-product: (listof Num) (listof Num) -> Num

(define (dot-product lst1 lst2)

(cond

[(and (empty? lst1) (empty? lst2)) 0]

[else (+ (* (first lst1) (first lst2))

(dot-product (rest lst1) (rest lst2)))]))

;; map-combine: Z (W X -> Y) (Y Z -> Z) (listof W) (listof X) -> Z

(define (map-combine base func-elem func-lst lst1 lst2)

(cond

[(and (empty? lst1) (empty? lst2)) base]

[else (func-lst (func-elem (first lst1) (first lst2))

(map-combine base func-elem func-lst (rest lst1) (rest lst2)))]))

(define (my-zip lst1 lst2)

(map-combine empty list cons lst1 lst2))

(define (my-dot-product lst1 lst2)

(map-combine 0 * + lst1 lst2))

(check-expect (zip (list 1 2 3 4 5) (list 6 7 8 9 10))

(my-zip (list 1 2 3 4 5) (list 6 7 8 9 10)))

(check-expect (dot-product (list 1 3 4) (list 5 7 8))

(my-dot-product (list 1 3 4) (list 5 7 8))) Template:

(define-struct node (key val left right))

;; A binary search tree (Bst) is one of:

;; * empty

;; * (make-node Number String Bst Bst) Template:

(define-struct UTnode (val children))

;; An unbounded tree (Ut) is one of:

;; * empty

;; * (make-UTnode Any UtList)

;; A UtList is one of:

;; * empty

;; * (cons Ut UtList)

Full transcriptTypes of recursion and how to determine the type

Local

Lambda

Abstraction and ALFs

Trees

Last office hours

Check your exam seat! CS 135 Exam Review Incorrect: Correct: (list-of-characters)

listof Character

(listof Characters)

(listof lists) (listof Character)

(listof (listof Character)) Pure Structural Examples: ;This example follows the list data definition

(define (pure-structural1 lst)

(cond

[(empty? lst) 0]

[(cons? lst) (add1 (pure-structural1 (rest lst)))]))

;This example follows from the unary definition of a natural number

(define (pure-structural2 n)

(cond

[(zero? n) empty]

[else (cons n (pure-structural2 (sub1 n)))])) Base case

Recursive call gets closer to the base case

Recursion follows the recursion of the data definition Pure Structural with an Accumulator Accumulators vs. "along for the ride" vs. "counters"

Same as Pure Structural, but rather than accumulating on the return result, accumulates on a parameter Examples: ;This example follows the list data definition

(define (pure-structural/acc1 lst items-so-far)

(cond

[(empty? lst) items-so-far]

[(cons? lst) (pure-structural1 (rest lst) (add1 items-so-far))]))

;This example follows from the unary definition of a natural number

(define (pure-structural/acc2 n list-so-far)

(cond

[(zero? n) empty]

[else (pure-structural2 (sub1 n) (cons n list-so-far))])) Generative Still has a base case

Termination argument vs. "one step closer to the base case"

Recursive step does not follow from the data definition Examples: ;This has a chance of terminating each call

(define (generative1 x)

(cond [(zero? x) empty]

[else (cons x (generative1 (random-0-to-9 x)))]))

;This will surely terminate, but is not based on the data definition

(define (generative2 lst)

(cond [(empty? lst) empty]

[else (generative2 (filter (lambda (x) (equal? x (first lst))) lst))])) Scope, binding occurrence

Stepping

When to use it over external helper functions/constants ;Scope example

(define x 5)

(define (f x)

(+ (local [(define x 7)] (+ x 3))

x))

(+ (f 3) (f x)) ;Local stepping example

(define (foo a)

(local [(define x (+ 1 2))

(define y 3)]

(+ x y a)))

(foo (+ 1 2))

;can't call a function until its arguments are simplest form

(foo 3)

;replace the function with its body, subbing in arguments

(local [(define x (+ 1 2))

(define y 3)]

(+ x y 3))

;local's first step is to take out the defines

;replace all instances of those constants with their new name

(define x_0 (+ 1 2))

(define y_0 3)

(+ x_0 y_0 3)

;simplify the first thing first

;also, exclude any defines that are in simplest form. they

; are still there, but not shown

(define x_0 3)

(+ x_0 y_0 3)

;substitute one constant at a time: first x_0

(+ 3 y_0 3)

;now y_0

(+ 3 3 3)

;pre-defined functions happen in one step

9 Local can also be used for readability. If it makes more sense to have a local helper function or local constant, then it should probably be used. Namespace

Efficiency

Readability When creating a very large program or working in a team, there can be a big list of functions. That's why it's important to "hide" helper functions inside of local.

On the other hand, if a helper function is useful for more than one function, it should be outside of local.

The same goes for constants. Something like pi might be useful for many functions, but something specific like sum-so-far should be local. As we've seen before, local can also be used to make a program more efficient, by storing the result of a recursive call in a local constant. This only needs to be done if you will then access that constant more than once afterward. Stepping

When to use lambda

Examples of how to use it ;if we look at a regular function and application

(define (foo x y)

(+ x y))

(foo 1 2)

;here, the first step is replace the function

;name with its body, subbing in all arguments

(+ 1 2)

;and finish

3 ;here is the same starting code, but using lambda.

;there are still 2 parameters, a function body, and 2

;arguments

((lambda (x y) (+ x y)) 1 2)

;the step is logically similar here: replace the

;lambda with the body of the function, subbing in

;all arguments, which are the 1 and 2

(+ 1 2)

;and finish

3 ;this is a similar example, except now foo is a

;constant that holds a function. this is really the

;same as a function, but here we'll have an extra step

(define foo (lambda (x y) (+ x y)))

(foo 1 2)

;now foo is a constant, so, like any constant, it takes

;a step to sub in

((lambda (x y) (+ x y)) 1 2)

;now we continue like the last example

(+ 1 2)

;and finish

3 Use lambda when the code is trivial. It is typically used in abstract list functions like quicksort, map, filter, foldr, foldl, or ones you make yourself.

Although it is possible to use (define foo (lambda (x y) (+ x y))), it is considered more readable to use (define (foo x y) (+ x y)), which is the same. ;when you need a function to produce a function:

(define (foo a)

(lambda (x) (char=? a x)))

;think about what this would do

;notice that this is different from

(define (foo a)

(char=? a __)) ;this wouldn't work

;when you use a function that consumes a function, and

;it's too simple to make it a helper function

(map (lambda (x) (* x 2)) (list 1 2 3 4))

There will be many more examples coming up. quicksort

build-list

map

filter

foldr quicksort requires you to give it a function that consumes two numbers it's trying to compare. Your function should produce true if the first should come before the second.

(define numbers (list 5 2 7 4 1 3))

Sort ascending:

(quicksort numbers <) --> (list 1 2 3 4 5 7)

Sort descending:

(quicksort numbers >) --> (list 7 5 4 3 2 1)

Put even first:

(quicksort numbers (lambda (num1 num2) (even? num1))) --> (list 4 2 5 7 1 3) build-list requires you to give it a function that consumes one number, which will hold the value of each number up to n as it gets called each time. Your function can produce anything, using the number it's given for calculations. Build list always consumes a number and produces a list with that many items.

(define numbers (list 5 2 7 4 1 3))

Make 0 to 9:

(build-list 10 (lambda (x) x)) OR (build-list 10 identity) --> (list 0 1 2 3 4 5 6 7 8 9)

Make 1 to 10:

(build-list 10 (lambda (x) (add1 x))) OR (build-list 10 add1) --> (list 1 2 3 4 5 6 7 8 9 10)

Make even 2 to 20:

(build-list 10 (lambda (x) (add1 (* 2 x)))) --> (list 2 4 6 8 10 12 14 16 18 20)

Make 0 to 4 as lists:

(build-list 10 (lambda (x) (list x))) OR (build-list 10 list) --> '((0) (1) (2) (3) (4)) map requires you to give it a function that consumes one item, which will be each item in the given list and it should return what you want that item to turn into. Unlike build-list, the item consumed doesn't have to be a number. Map always consumes a list and produces a list with the same number of items, but those items are all transformed into something else using the function you give it.

(define numbers (list 5 2 7 4 1 3))

Double each number:

(map (lambda (x) (* 2 x)) numbers) --> (list 10 4 14 8 2 6)

Add 1 to each number:

(map (lambda (x) (add1 x)) numbers) OR (map add1 numbers) --> (list 6 3 8 5 2 4)

Change them all into 'a:

(map (lambda (x) 'a) numbers) --> (list 'a 'a 'a 'a 'a 'a)

filter requires you to give it a function that consumes each item like map, but will produce true or false. True means keep the item and false means don't include it in the new list. filter always consumes a list and produces a list with equal or fewer items.

(define numbers (list 5 2 7 4 1 3))

Keep only even numbers:

(filter even? numbers) --> (list 2 4)

Keep only numbers greater than 4:

(filter (lambda (x) (> x 4)) numbers) --> (list 5 7)

Keep only symbols:

(filter symbol? numbers) --> empty foldr requires you to give it a function that consumes two items: the first of these is each item in the list and the second is the result of calling your function on the rest of the list. Your function should do something to combine the item onto the result of the rest. foldr always consumes a list but can produce anything. It will only produce a list if your function acts like cons. What type it produces depends on the function you give it.

(define numbers (list 5 2 7 4 1 3))

Count the number of items:

(foldr add1 0 numbers) --> 6

Sum the numbers:

(foldr + 0 numbers) --> 22

Make the exact same list:

(foldr cons empty numbers) --> (list 5 2 7 4 1 3)

Double each number:

(foldr (lambda (x y) (cons (* 2 x) y)) empty numbers) --> (list 10 4 14 8 2 6) Recursion for BST

Mutual recursion for a General Tree (Demonstrate on the board)

Searching

Adding a node

Removing a node (Demonstrate on the board)

Searching

Adding a node

Assignment 7 q3 and q4 Thursday

Friday 4-5pm Eric 9-10am Max

10am-12pm Eric

12-1pm Minghao

2pm-3:30 Prof Becker To look up your exam seat:

Go to the course web page --> Exams --> a link in the text that says "look up"

Be sure to read that exams page for more information.

Monday, December 20, 2010 12:30-3:00 PM in the PAC Relax and do your best! :) ;; zip: (listof Any) (listof Any) -> (listof (list Any Any))

(define (zip lst1 lst2)

(cond

[(and (empty? lst1) (empty? lst2)) empty]

[else (cons (list (first lst1) (first lst2))

(zip (rest lst1) (rest lst2)))]))

;; dot-product: (listof Num) (listof Num) -> Num

(define (dot-product lst1 lst2)

(cond

[(and (empty? lst1) (empty? lst2)) 0]

[else (+ (* (first lst1) (first lst2))

(dot-product (rest lst1) (rest lst2)))]))

;; map-combine: Z (W X -> Y) (Y Z -> Z) (listof W) (listof X) -> Z

(define (map-combine base func-elem func-lst lst1 lst2)

(cond

[(and (empty? lst1) (empty? lst2)) base]

[else (func-lst (func-elem (first lst1) (first lst2))

(map-combine base func-elem func-lst (rest lst1) (rest lst2)))]))

(define (my-zip lst1 lst2)

(map-combine empty list cons lst1 lst2))

(define (my-dot-product lst1 lst2)

(map-combine 0 * + lst1 lst2))

(check-expect (zip (list 1 2 3 4 5) (list 6 7 8 9 10))

(my-zip (list 1 2 3 4 5) (list 6 7 8 9 10)))

(check-expect (dot-product (list 1 3 4) (list 5 7 8))

(my-dot-product (list 1 3 4) (list 5 7 8))) Template:

(define-struct node (key val left right))

;; A binary search tree (Bst) is one of:

;; * empty

;; * (make-node Number String Bst Bst) Template:

(define-struct UTnode (val children))

;; An unbounded tree (Ut) is one of:

;; * empty

;; * (make-UTnode Any UtList)

;; A UtList is one of:

;; * empty

;; * (cons Ut UtList)