Lesson 2

Question 1

What is parse tree?

Answer 1

Any compiler or interpreter builds a parse tree out of what expressions you type to do the compilation or interpretation

Question 2

What are the uses of trees?

Answer 2

1. To represent a hierarchy
2. Binary search tree
3. Parse tree

Question 3

What is the difference between nodes and trees?

Answer 3

Node and trees are synonyms

Question 4

What is the runtime of doing work in a tree?

Answer 4

Θ(N) where N is the size of the tree. If we have to look at every item.

Question 5

What is the base case in this code?
(define (treemap fn tree)
(make-tree (fn (datum tree))
(map (lambda (child) (treemap fn child))
(children tree) )))

Answer 5

Base case is inside the map. If this is an empty list, return the empty list.
Vertical base case: leaf of the node because children of tree is empty
Horizontal base case: when we run out of siblings in the children of the node

Question 6

What is a tree data stucture?

Answer 6

Abstract data type

Question 7

Runtime of binary search tree

Answer 7

Θ(lg N)

Question 8

When to use mutual recursion?

Answer 8

Use mutual recursion when dealing with 2 dimensional data structure. Use trick of using map to handle one of the dimensions.

Question 9

(define (deep-map fn lol)
(if (list? lol)
(map (lambda (element) (deep-map fn element)) lol)
(fn lol)))
lol can have arbitrary depths.
What does this code do?

Answer 9

if it is a leaf node, do something about the datum. if it is a branch node, do something about the list of children.

Question 10

List of lists can be represented as a tree. True or false?
eg ((Matt, Lee), (John, Lennon), (Alan, Turing))

Answer 10

True. Lol is another 2 dimensional data structure which can be represented as a tree.

Question 11

what is a deep list?

Answer 11

A deep list is a list of lists where the leaf nodes are datum with no children and the branch nodes have children but no datum.

Question 12

how is binary search tree special trees?

Answer 12

They have 2 children. Trees can have n children.

Question 13

DFS

Answer 13

(define (depth-first-search tree)
(print (datum tree))
(for-each depth-first-search (children tree)))

Question 14

BFS

Answer 14

(define (breadth-first-search tree)
(bfs-iter (list tree)))
(define (bfs iter queue)
(if (null? queue)
‘done
(let ((task (car queue)))
(print (datum task))
(bfs-iter (append (cdr queue) (children task))))))

what does list tree do?
it makes the tree into a queue. Queue is just a list.

Question 15

BFS application

Answer 15

searching for answers, we want to find the quickest way to leaf of the node bc then you win the chess game
eg: chess game, we want to find solution. each node make one decision, each possible move will be a child node. we run BFS in a fixed amount of time because there are too many solutions that it would take forever.

minimal possible path to the leaf.

Question 16

Inorder
Preorder
Postorder

Answer 16

Inorder
Left, Datum, Right
Preorder
Datum, Left, Right
Postorder
Left, Right, Datum

Question 17

How does primitive procedures work?

Answer 17

primitive procedures are built into interpreter. it is machine language code that has been compiled into native language of the computer hardware.
primitive procedures does magic

Question 18

Primitive vs lambda procedures

Answer 18

sdk procedure is a scheme-1 primitive. lambda procedures are scheme-1 non-primitives. for lambda expressions, we evaluate its body after substitutions

Question 19

Answer 19

self-evaluating atoms: numbers, strings
symbols: car, if - symbols represent a variable. global variables - primitive procedures
lists:
if the first element of expression is a keyword, the expression is a special form
if the first element is not a keyword, it is a procedure call. (fn args)

Question 20

how many bits in an integer?

Answer 20

signed 32 bits

Question 21

how many bits in a long?

Answer 21

signed 64 bits

Question 22

how many bits in a short?

Answer 22

signed 16 bits

Question 23

how many bits in a char?

Answer 23

unsigned 16 bits

Question 24

how many bits in a byte?

Answer 24

signed 8 bits

Question 25

how many bits in a boolean?

Answer 25

unsigned 8 bits

Question 26

1.

how many bits in a float?

Answer 26

32 bits

Question 27

how many bits in a double?

Answer 27

64 bits

Question 28

what does compiler do?

Answer 28

translate source code from a high-level programming language to a lower-level language like object code. A compiler creates a machine code that runs on a processor with a specific Instruction Set Architecture (ISA), which is processor-dependent
compile before we run the program

Question 29

1.

compiler vs interpreter

Answer 29

Compiler: A compiler translates code from a high-level programming language (like Python, JavaScript or Go) into machine code before the program runs. Interpreter: An interpreter translates code written in a high-level programming language into machine code line-by-line as the code runs
Compiled languages are converted directly into machine code that the processor can execute. As a result, they tend to be faster and more efficient to execute than interpreted languages.

The compiled bytecode is interpreted to run in a virtual machine that is optimized to speak directly to the hardware.

Question 30

Why don’t we use compiler in Python?

Answer 30

Python does not need a compiler because it relies on an application (called an interpreter) that compiles and runs the code without storing the machine code being created in a form that you can easily access or distribute.

Question 31

Is javascript a interpreted or compiled language?

Answer 31

JavaScript is an interpreted language, not a compiled language. A program such as C++ or Java needs to be compiled before it is run. The source code is passed through a program called a compiler, which translates it into bytecode that the machine understands and can execute.

Question 32

what is data directed programming?

Answer 32

Basically, it’s a different way of organizing your code. Instead of using big cond expressions to handle all different behavior, you treat the code itself as data, and use that data to drive your program.
Our primary exposure to DDP in 61A is by using tagged data and generic operations to organize our code. When we want to perform an operation, we look up the implementation in a table (the “get/put table”) to find the version of the operation appropriate for the type.

There are three parts to this system. First, we need an abstraction for “tagged data”, with constructor attach-tag and selectors type-tag and contents. SICP chooses to implement these with cons, car, and cdr, respectively.

Next, we need a two-dimensional table (one where you can look things up by type and operation). We’ll learn how these tables are constructed in Chapter 3, but for now we’ll use one that comes with our CS61A library. Accessing this table is done through a pair of procedures called put and get.

> (put ‘square ‘perimeter (lambda (side) (* 4 side)))
okay
(get ‘square ‘perimeter)
#[closure args=(side) 61a61a]
((get ‘square ‘perimeter) 5)
20
(get ‘triangle ‘perimeter) ; not in table
#f
We could just use this, but often we define a convenient procedure for using generic operators called operate. This isn’t in the library, but it’s pretty easy to put in yourself. (It’s also in the lecture notes.)

(define (operate op arg)
(let ((fn (get (type-tag arg) op)))
(if fn
(fn (contents arg))
(error “Bad operation “ op “ for data “ arg) )))

Question 33

we don’t want to change old code that is working to add new code. True or false

Answer 33

True

Question 34

(define (count sent)
(define (iter sent count-so-far)
(if (empty? sent)
count-so-far
(iter (bf sent) (+ 1 count-so-far)) ))
(iter sent 0) )
Is this recursive or iterative?

Answer 34

Iterative. Notice how the call to the helper procedure ITER is the last thing that happens in COUNT. This is called a tail call. Moreover, each recursive call in ITER is also a tail call; this is often called being tail-recursive.

You might think we have the same problem as before: doesn’t COUNT still have to wait for ITER to finish before returning its result? Scheme, however, is smart enough to realize that all COUNT is going to do with the value it gets from ITER is return it, and so just tells ITER to return its result to whoever called COUNT. That means that COUNT doesn’t have to sit around waiting for ITER, and can give its memory back right away.

If a procedure calls another procedure that isn’t iterative, does the first procedure still count as iterative? Not really—the space required to run the first procedure has to include the space for the second. Moral of the story: if every recursive call in a procedure is a tail call, and everything the procedure calls is iterative, that procedure is iterative as well!

Question 35

(define (alternating-pos sent)
(cond ((empty? sent) #t)
((< 0 (first sent))
(alternating-neg (bf sent)) )
(else #f) ))

(define (alternating-neg sent)
(cond ((empty? sent) #t)
((> 0 (first sent))
(alternating-pos (bf sent)) )
(else #f) ))

Answer 35

Iterative

Even though we have mutual recursion here, every call is still a tail call, which means every call can give up its space once it gets to the mutually recursive step. Thus the total space required is still fixed, and the process is iterative.

Question 36

1. Can a function that has multiple calls to itself generate an iterative process?
2. Can a function that has only one call to itself generate a recursive process (not iterative?)
3. Can a function that has no calls to itself generate a recursive process?

Answer 36

1. Sure! The catch is that all of them have to be tail calls. How can that work? If each recursive call is in a different IF or COND clause.
2. Sure. Our usual implementation of COUNT only has one call to itself, and is not iterative.
3. Sure. This was the case with SQUARES, above.
   (define (every fn sent)
   (if (empty? sent)
   ‘()
   (se (fn (first sent)
   (every fn (bf sent)) )))
   (define (squares sent)
   (every (lambda (x) (* x x)) sent) )

Question 37

What is the runtime of
(define (two-to-the n)
(if (= n 0)
1
(else (+ (two-to-the (- n 1)) (two-to-the (- n 1)))) ))

Answer 37

Recursive, O(2^n) O(2-to-the-nth-power)

The procedure is O(2^n), because:

There are two recursive calls per call to TWO-TO-THE, except in the base case.
The recursion only stops when n is 0.
n is reduced by 1 with each recursive call.
Thus, there are n levels of recursion, and 2-to-the-k calls on the kth level. This comes out to O(2^n).
If there had been three recursive calls, it would have been O(3^n). If n had gone down by two each time, it would have been O(2^(n/2)). You get the idea.

Question 38

What is the runtime of highest and selection-sort?
`
; Sorts the numbers in NUMS
(define (selection-sort nums)
; Selects the highest number in NUMS that’s less than LIMIT
(define (select-highest nums highest-so-far)
(cond ((empty? nums) highest-so-far)
((> highest-so-far (first nums))
(select-highest (bf nums) highest-so-far) )
(else (select-highest (bf nums) (first nums))) ))
; Uses SELECT-HIGHEST to add the next highest number in UNSORTED to SORTED
(define (helper unsorted sorted)
(if (empty? unsorted)
sorted
(let ((highest (select-highest (bf unsorted) (first unsorted))))
(helper (remove highest unsorted) (se highest sorted)) )))
(helper nums ‘()) )
`

Answer 38

1. SELECT-HIGHEST: Iterative, O(n)
2. HELPER: Iterative, O(n²)
   There is at most one recursive call per call to HELPER.
   A single call to HELPER has two O(n) calls.
   The recursion ends when UNSORTED is empty.
   UNSORTED gets one element shorter with each recursive call.
   So there are N recursive calls to HELPER, each of which has O(n) operations in it. So HELPER (and thus SELECTION-SORT) is O(n²).