Lesson 1

Question 1

‘’’
(define (square x))
(*x x ))
(square (+2 3))
‘’’

Answer 1

x is formal parameter, name for argument to the function
(* x x ) is the body which is part of the definition of the function
(+2 3) is the actual argument expression
actual argument value is 5

Question 2

What is a predicate?

Answer 2

Predicate is a function that returns true or false. Convention is the name ends with ?

Question 3

(define (pigl wd)
(if (pl.done? wd)
(word wd ‘ay)
(pigl (word (bf wd) (first wd)))))

(define (pl.done? wd)
(vowel? (first wd)))
(define (vowel? letter)
(member? letter ‘(a e i o u)))

what is the result of (pigl ‘scheme)?

Answer 3

emeschay

Question 4

What is abstraction?

Answer 4

High level language (eg: Scheme)
Low level language (eg: C)
Machine language / architecture
—
Logic gates
Transistors
Quantum physics

Question 5

What are logic gates?

Answer 5

Circuits that compute boolean functions (t/f). We can represent t/f values with one wire. Logic gates are built out of transistors like remote control switch.

Question 6

f(x) = 2x + 6
g(x) = 2(x+3)
Are they the same function?

Answer 6

They are the same functions but different procedures. Same function because output is the same given input.
Different procedures because different sequence of steps. Inside computer, we look at procedures.

Question 7

Why is functions important?

Answer 7

1. Functions are well understood, easy to do reasoning on software system that is built functionally. We can prove theorems on them.
2. Because of multi-core processors. We can run the program with parallelism if we write functionally since function does not care about what the rest of the program is doing.

Question 8

Is f(x) = 2x + b a function?

Answer 8

No, because b is a free variable, and we get different outputs given same inputs.

Question 9

(cond clause clause)
(test action)
(fn arg arg…) (fn arg arg…)
(cond ((equal? (remainder, 7) 0) ‘buzz)
((member? 7 n) ‘buzz)
(else n))

Answer 9

cond is a special form. It evaluates the test, if the test is true, it evaluates the action part and it finish. If the test returns false, it goes to the next clause and do the same thing.

Question 10

Normal order evaluation

Answer 10

Procedure - take argument expressions and substitute them into the body. Arguments are evaluated only when we find a primitive.

Question 11

Applicative order eager evaluation (hint: Scheme does this)

Answer 11

Evaluate subexpressions so we pass argument values into procedures. We substitute values for parameters in the body

Question 12

What has to happen in recursion?

Answer 12

Base case has to come first before recursion can take place.

Question 13

(def (zero z) (-z z))
(applic (zero (random 10)))
(zero (random 10))
(random 10) => 8
(- 8 8) => 0
(normal (zero(random 10)))
(- (random 10) (random 10))
(random 10) => 8
(random 10) => 1
(- 8 1) => 7
Why different answers?

Answer 13

Because random is a procedure that is not a function. If we write purely functionally programs, then we get the same answers.
If not functional, it matters what order things happen inside the computer. Functional programming protects you from figuring out what happens when inside the computer.

Question 14

First class data types can be ?

Answer 14

First Class Data Type can be
- the value of a variable
- an argument to a procedure
- the value returned by a procedure
- a member of an aggregate
- anonymous

Question 15

(define (evens nums)
(cond ((empty? nums) ‘())
((= (remainder (first nums) 2) 0)
(se (first nums) (evens (bf nums))))
(else (evens (bf nums))) ))
what is the output of (evens ‘(3 5 1 4 9 8 6 7))

Answer 15

(4 8 6)

Question 16

what is domain and what is range?

Answer 16

domain - what kinds of things it take as arguments
range - what kinds of things it returns as a result

Question 17

(define (ewords sent)
(cond (empty? sent) ‘())
((member? ‘e (first sent))
(se (first sent) (ewords (bf sent))) )
(else (ewords (bf sent))) ))
what does (ewords ‘(got to get you into my life)) return?

Answer 17

(get life)

Question 18

(define (pronouns sent)
(cond ((empty? sent) ‘())
((member? (first sent) ‘(I me you he she it him her we us they them))
((se (first sent) (pronouns (bf sent))) )
(else (pronouns (bf sent))) ))
what does (pronouns ‘(i only want to dance with you)) return?

Answer 18

(i you)

Question 19

(define (keep PRED sent)
(cond ((empty? sent) ‘())
((PRED (first sent))
((se (first sent) (keep PRED (bf sent)) )))
(else (keep PRED (bf sent))) ))

(keep (lambda wd)(member? ‘e wd))
‘(being for the benefit of mister kite))
1. what does this return?
2. what is keep an example of?

Answer 19

1. (being the benefit mister kite)
2. keep is a higher order procedure because it takes a procedure as an argument.

Question 20

what is a lambda expression?

Answer 20

lambda makes a procedure. lambda returns a procedure.

Question 21

what is higher order procedure?

Answer 21

it takes in a function as argument
OR
it returns a function

Question 22

Why do we want to generalize patterns?

Answer 22

to make programs shorter and to only write functions once. This is an example of procedure as data.

Question 23

What are first class data types?

Answer 23

Numbers
Character strings are first class in some languages but not all
Data aggregates are rarely first class.
Hardly any language give you procedures as first class. Python - lambda. Java - anonymized classes. Scheme.

Question 24

(define (compose f g) (lambda (x) (f (g x)))))
(define (twice f) (compose f f))
what does ((twice square) 3) return?

Answer 24

81

Question 25

(let* ((a 3)(b (+ a 5)))
(* a b))

is translated to:

(let ((a 3))
(let ((b (+ a 5)))
(* a b)))
Does this work? Can we access a inside (b (+ a 5))

Answer 25

Yes, value of a exists inside the body so we can use the value. It uses the binding of a to 3, so the order of bindings matter.
Let is an example of having procedures as a data type.

Question 26

Can you make a recursive procedure inside a let?

Answer 26

No. In order to make a recursive procedure, it needs access to its own name.

(let ((fact (lambda(n) (…) (fact(- n 1)))
(fact 5)
The body of let does have value from fact procedure. But the inner fact defined here (fact (- n 1)) gets evaluated before we provide a binding for the name fact so it will throw an error.

Question 27

((lambda (d -b 2a) (se ….))
(sqrt ….)
(- b)
(* 2a))
does this work? can we use d inside the sqrt expression?

Answer 27

No. The sqrt procedure, -b , *2a, gets evaluated before we call the lambda procedure so there is no d when we evaluate sqrt.

Question 28

what is the time complexity of this?
(define (square x) (* x x))
(define (squares set)
(if (empty? sent)
‘()
(se (square (first sent))
(squares (bf sent)) )))
(squares ‘(6 25, 3, 1, 9))

Answer 28

There are 6 class, 5 calls with non-empty sentences and 6th call with empty sentence.
empty sentence does 2 operations (if, empty). The non-empty sentences does 6 operations (first, bf, square, empty?, if, se)
Answer: 6N + 2 where N is the length of the input sentence
Constant factors in running time is not interesting, because when computers get faster, the run time will get cut in half.

Question 29

t(x) = O(x^2) is wrong
t(x) ∈ O(x^2) or
t(x) ∈ O(x ↦ x^2 ) this is even more accurate because it is a function f(x) maps to y

Answer 29

Big O notation
We look at big values of N, not small values.
Constant factors like / 2 can be removed (exception is in video games)

Question 30

Big θ

Answer 30

f∈θ(g) <-> f∈O(g) ∧ g∈O(f)

Question 31

Searching time complexity

Answer 31

θ(1)
θ(log N)
θ(N)

Question 32

Sorting time complexity

Answer 32

θ(N log N)
θ(N^2)

Question 33

Recursion - space efficiency

Answer 33

memory use is linear to the size of the problem
no work is being done until we get to the bottom of the recursive stack
remember to consider the memory space!

Question 34

θ(N^3) matrix multiply
Intractable - would never finish running for significant data sets
θ(2^N)
θ(N!)
θ(N^N)

Answer 34

Write approximate solutions that return in reasonable amount of time instead of intractable solutions

Question 35

what is a sentence?

Answer 35

list of words
it can accept words as well as list as arguments

Question 36

what is the difference between append and list?

Answer 36

append returns list of elements in the list
list returns list of all elements in the list

Question 37

What is the structure of pair?

Answer 37

cons - constructor of a pair
car - left half
cdr - right half

Question 38

What does (cons (3 4) (5 6)) return?

Answer 38

((3 4) 5 6) because cons take the first element and push it to the front of already existing list.

Question 39

What does (cons 3 (cons 4 (cons 5 ()))) return?

Answer 39

(3 4 5)

Question 40

What does (list (3 4) (5 6)) and (append (3 4) (5 6)) return?

Answer 40

((3 4) (5 6))
(3 4 5 6)

Question 41

What is the difference between data and procedures?

Answer 41

Things Actions
nouns verbs
know that know how to
DATA PROCEDURES

Question 42

is print functional?

Answer 42

no, because it changes the state of the world

Question 43

is read functional?

Answer 43

no because every time you call it with same input, you get different output

Question 44

what does flush do?

Answer 44

flush display characters on the string and waits for input. when we want to display characters, we need a newline character, but with flush we can do it with no newline character

Question 45

what is syntax vs semantics?

Answer 45

syntax - structure of language
semantics - meaning of individual words