CSci 1901: Practice Questions

Questions will be posted here to help you understand better the material. Try them. If you have difficulties in answering them, ask the TAs or me. We will not post answer keys for these.

Chapter 1

1. Evaluate the following expressions and write the result they return after the =>.
 `(define c (/ 13 3))` `(define (foo x y) (* x y))` `(+ c 3)` => `(- 2 (foo c 9))` => `(foo -2 c)` => `((if (> (foo 2 3) 10) + -) c 3)` => `((lambda (x) (foo x c)) 12)` => ```(let ((x (foo 2 4))) (+ x 5))``` => ```(let ((a (foo c 9))) (let ((b (- a 1))) (+ b a)))``` => `(let ((c 3)) c)` => `c` => ```((let ((x 2) (y 3)) (lambda (x) (+ x y))) 8)``` =>
2. Write a procedure (f n) to compute the following function by means of an iterative process:
 f(n)= 0 if n=0 1 if n=-1 1 if n=1 2 * f(n+1) if n <= -2 n * f(n-2) if n >= 2
It should work like this: STk> (f 2) ; 2*f(0) 0 STk> (f 3) ; 3*f(1) 3 STk> (f -3) ; 2*f(-2)=2*2*f(-1)= 2*2*1 4 STk> (f 5) ; 5*f(3)=5*3*f(1)=5*3*1 15
3. Write a procedure to compute (f n) by means of an iterative process, where
f(n) = 0 if n ≤ 0
f(n) = f(n-1) + 1/n otherwise
It should work like this:
```STk> (f 2)
1.5 ; f(2)=f(1)+1/2=f(0)+1/1+1/2=3/2
STk> (f 3)
1.8333  ; f(3)=f(2)+1/3=3/2+1/3
STk> (f -3)
0  ; n<=1
```
4. Write a procedure (sum-of-powers n p) to compute the sum of the integers from 1 to n raised to the power p. Assume that n and p are non negative integers. Use the primitive (expt a b) to compute a raised to the power b. It should work like this:
```STk> (sum-of-powers 3 2)
14   ; since 1**2 + 2**2 + 3**2 = 1 + 4 + 9 = 14
```
5. Write a procedure (sum-harmonic n) to compute the sum of the first n terms in an harmonic sequence. The terms in an harmonic sequence are 1, 1/2, 1/3, 1/4, etc Assume n is a positive integer. Use the primitive (/ n) to compute 1/n. It should work like this:
```STk> (sum-harmonic 3)
1.83333333333333  ; since 1 + 1/2 + 1/3 = 1.83333333333333
```
6. Write a procedure (my-quotient a b) that computes the quotient of the two positive integers a and b using repeated subtractions. Note: in this case do NOT use any of the primitive procedures to divide the two numbers. It should work like this:
```STk> (my-quotient 7 3) should return 2
STk> (my-quotient 9 3) should return 3
```
7. Write a predicate (find-digit? i n) to find if the digit i appears in the decimal representation of the positive integer n. It should work like this:
```STk> (find-digit? 3 15637)
#T  ; 3 appears in 15637
STk> (find-digit? 3 567)
#F  ; 3 does not appear in 567
```
8. Write a procedure (add-even n) to add the even digits in the decimal representation of the positive integer n. It should work like this:
```STk> (add-even 12456)
12  ; 2+4+6=12
0
```
9. Consider the following expressions
```   (define (foo y)
(let ((x (/ y 2)))
(/ (+ y x) (- y x))))
(define (f x) (+ (foo x) x))
```
What is the value of `(f 10)`?

Chapter 2

Lists

1. Write a procedure `(precedes el lst)` that returns a list of all the elements in the list that immediately precede `el` in the list. The order of the elements in the resulting list is not important. It should work like this: STk> (precedes 'a (a b r a c a d a b r a)) (r c d r) STk> (precedes 1 '(4 1 6 8 5 1 7 1)) (4 5 7)
2. Write a procedure `(el+pos lst)` that returns a list of each element in lst added to its position in the list. Assume positions in the list are numbered from 0, and that all the elements in the list are numbers. It should work like this:
```STk> (el+pos '(7 5 1 4))
(7 6 3 7)     ; 7=7+0, 6=5+1, 3=1+2, 7=4+3
```
3. Write a procedure, `remove-adj-dup`, to remove all adjacent duplicate elements in a list. If no adjacent elements are duplicate it should return the original list. It should work like this: STk> (remove-adj-duplicates '(a b b c b d d d) ) (a b c b d) STk> (remove-adj-duplicates '(a b c b d) ) (a b c b d)
4. Write a procedure `(split lst)` to split a list into 2 lists and to return a list of the two lists. The split is to be done so that the first element from `lst` will go into the first list, the second into the second, the next into the first list, and so on. It should work like this: STk> (split (list 1 2 3 4 5)) ((1 3 5) (2 4)) STk> (split (list 1)) ((1) ())
5. Write a procedure `(compress lst)` that takes as argument a list. The elements of the list are either symbols or lists containing multiple copies of the same symbol. The procedure should return a list where the repeated symbols are compressed, i.e. each sublist of repeated symbols is replaced by a sublist of the form ( <number> <symbol>), where number is a positive integer which indicates how many times the symbol occurred in the original sublist and symbol is the repeated symbol.
Do not use use any mutator (i.e. no `set!, set-car!, set-cdr!`) in your procedure. You are free to use as many auxiliary procedures as you like. You do not need to do any error checking on the input list. It should work like this:
```STk> (compress '(a (very very) big boat))
(a (2 very) big boat)
STk> (compress '((oh oh oh oh)))
((4 oh))
```

Sets

1. Write a predicate (same-set? set1 set2) to check if two sets are the same (i.e. they contain the same elements). Assume the sets are represented by unordered lists. It should work like this:
```STk> (same-set? (list 5 4 2) (list 2 4 5))
#t
STk> (same-set? (list 5 4 2 6) (list 2 4 5))
#f
```
2. Write a procedure (adjoin-set el set) to insert an element into a set represented by an ordered list. Write the procedure to take advantage of the ordering of the elements of the set to speedup the computation. It should work like this:
```STk> (adjoin-set 1 (list 2 3 7))
(1 2 3 7)
STk> (adjoin-set 5 (list 2 3 7))
(2 3 5 7)
STk> (adjoin-set 15 (list 2 3 7))
(2 3 7 15)
```
3. Write a procedure (insert-el el set) to insert an element in a set represented by an ordered list. If the element does not exist in the set, the procedure should return the same set. Write the procedure to take advantage of the ordering of the elements of the set to speedup the computation. It should work like this:
```STk> (insert-el 3 (list 2 5 7))
(2 3 5 7)
STk> (insert-el 5 (list 2 5 7))
(2 5 7)
```
4. Write a procedure (remove-el el set) to remove an element from a set represented by an ordered list. If the element does not exist in the set, the procedure should return the same set. Write the procedure to take advantage of the ordering of the elements of the set to speedup the computation. It should work like this:
```STk> (remove-el 3 (list 2 3 7))
(2 7)
STk> (remove-el 5 (list 2 3 7))
(2 3 7)
```

Trees

1. Write a procedure in Scheme to flatten a list of lists, i.e. to transform a tree into a list. It should work like this: ``` STk> (flatten '(a (b c (d e f) h))) (a b c d e f h) STk> (flatten ()) () ```
2. Write a procedure `(multiplicity el tree)` to return the number of occurrencs of an element in a tree. It should work like this: STk> (multiplicity 'x '((x (x)) x)) 3 STk> (multiplicity 'y '(a (b c))) 0 STk> (multiplicity 'a '(d (b (a)))) 1
3. Write a procedure `(greater-than n lst)` that counts how many elements in a tree are strictly greater than `n`. It should work like this: STk> (greater-than 3 '(1 -3 4) ) 1 STk> (greater-than -3 '(1 -3 4) ) 2 STk> (greater-than 8 '(1 (-2 7)) ) 0 STk> (greater-than -3 '((1 -2) 4) ) 3
4. Write a predicate `(samestructure tree1 tree2)` that checks whether two trees have the same structure. Two trees have the same structure if they contain exactly the same number of symbols and have all the parentheses in the same positions. The symbols can be different. It should work like this: STk> (samestructure '((x (x)) x) '((x (x)) x)) #t STk> (samestructure '(a (b c)) '(g (h K)) #t STk> (samestructure '(a (b c)) '(a b c)) #f
5. Write a procedure replace to replace every occurrence of an element in a tree with another element. The procedure should take three arguments, the element to be replaced, the replacement, and the tree in which to make the replacement. It should work like this:
```STk> (replace 'like 'dislike '(i (do not (like scheme))))
(i (do not (dislike scheme)))
STk> (replace 'f 'g '(h (+ (f x y) (f 1 x))))
(h (+ (g x y) (g 1 x)))
```
6. Write a predicate (find? el tree) that returns #t if the given element el is in tree. Assume that el is either a number or a symbol, but not a pair. It should work like this:
```STk> (find? 3 '(2 ((3 4) 7) 1))
#t
STk> (find? 'a '(v ((c (d 7) 5))))
#f
```
7. Write a procedure (extract pred tree) that returns a list of the elements in the tree tree that satisfy the predicate pred. It should work like this:
```STk> (extract number? '(2 ((3 4) 7) 1))
(2 3 4 7 1)
STk> (extract number? '(v ((c (d 7) 5))))
(7 5)
```
8. Write a procedure (deepen el tree) to deepen the element el in the tree tree. Deepening an element means to wrap a pair of parentheses around it. It should work like this:
```STk> (deepen 'scheme '((and (scheme fun) (scheme weird))))
((and ((scheme) fun) ((scheme) weird))))
STk> (deepen 'f '(h (+ (f x y) (f 1 x))))
(h (+ ((f) x y) ((f) 1 x))))
```

Chapter 3

Environments

1. Consider the following expressions
```   (define (foo y)
(let ((x (/ y 2)))
(/ (+ y x) (- y x))))
(define (f x) (+ (foo x) x))
(f 10)
```
What is the value of the last expression `(f 10)`?
Draw the environment diagram that results when the expressions are evaluated. Number the boxes to indicate the order in which they are generated.
2. Show the environment diagram created by the following calls. Specifically show the variables and their values into each frame, and connect each frame to its parent frame.
```(define (make-scale r) (lambda (x) (* x r)))
(define double make-scale)
(define a (double 42))
```

Mutators

1. Write a procedure `(extend! lst item)` to extend a list by attaching a new item at the end of the list. The procedure should modify the existing list.
2. Write a procedure `(replace! old new lst)` to destructively replace the first occurrence of `old` with `new` in the list. If the element does not appear in the list it should return the list unchanged. It should work like this:
```STk> (replace! 'pet 'dog '(the cutest pet))
(the cutest dog)
STk> (replace! 'pet 'dog '(the cutest cat))
(the cutest cat)
STk> (replace! 1 100 '(3 4 1 2 1))
(3 4 100 2 100)
STk> (replace! 1 100 (list 3 4 2 10))
(3 4 2 10)
```
3. Write a procedure `(insert-one! item lst)` to destructively insert `item` after the first element of `lst`. Assume the list always has at least one element. It should work like this:
```STk> (insert-one! 5 (list 1 2 3))
(1 5 2 3)
STk> (insert-one! 5 (list 1))
(1 5)
```

Abstract data types

1. You are given a queue implemented with the representation shown in the textbook. Write a procedure `delete-queue-rear!` that implements a new version of `delete-queue!` which operates at the other end of the queue, i.e deletes off the rear of the queue instead of the front. It should work like this:
```STk> (define q (make-queue))
q
STk> q
(())
STk> (insert-queue! q 'a)
((a) a)
STk> (insert-queue! q 'b)
((a b) b)
STk> (delete-queue-rear! q)
((a) a)
```
2. Write a procedure `(extract table key-list)` to find in a table the values of the keys that are included in the list `key-list` and return a list of them. Assume that `table` is a one-dimensional table, defined as in the textbook.
It should work like this: suppose you are given the table `offices` containing names of employees and their office numbers. The keys in `offices` are symbols representing names, the values are office numbers. Suppose you are also given a list `names` with names of people. `(extract offices names)` should return a list containing the office numbers of the names in `names` who are in the table `offices`. Use the selectors and mutators from the textbook to access the entries in the table.
3. Consider the table type as defined in the texbook on pages 265-268. Suppose you have a one-dimensional table `weekly-expenses`, that is indexed by items you bought during the week (assume they are symbols), and that contains for each item its price (assume it is an integer). Write a procedure `add-table` to compute the total amount of money you have spent to buy the items in weekly-expenses.
4. Write a procedure `(increase! amount updates oldtable)` to increase by `amount` the values of the keys in the table `oldtable` that appear in the list `updates`. The procedure `increase!` should increase the value in the table of all the entries whose key is in the list `updates` and ignore any key in `updates` which is not in `oldtable`
Use the selectors and mutators from the textbook to access the entries in the table.
It should work like this:
```STk> (define accounts '(*table* (john . 250) (anna . 325) (bob . 50)))
accounts
STk> (define bonus '(john bob))
STk> (increase! 25 bonus accounts)
(*table* (john . 275) (anna . 325) (bob . 75)))
```
5. Write a procedure in Scheme to count the number of actions in an agenda data structure, i.e. that counts the number of thunks in all the queues in the agenda data structure. [Hint: write a procedure queue-length to return the length of a queue and then use the selectors for the agenda]

Objects

1. Write a procedure `(make-comparator initial)` to construct an object that compares if the item passed to it is the same as the item passed to it the previous time. The argument of `make-comparator` is the initial value to compare to. The procedure should be written using message passing style. The object created by `make-comparator` should recognize the following messages:
 Message Argument Definition same? item if item is equal to the item passed the previous time it returns #t, otherwise it stores the item and returns #f last returns the last item passed to it reset! resets the comparator
For example:
```STk> (define item (make-comparator ()))
;;creates an object with initial value ()
STk> ((item 'same?) 'a):
#f ;; item a is saved in the object
STk> (item 'last)
a
STk> ((item 'same?) 'a)
#t  ;; no change to the object
STk> (item 'reset!)
()
```
2. Write a procedure `(make-gauge init)` to create a gauge object. A gauge object is an object that keeps a value and counts up and down from it. The object accepts the following messages:
 Message Definition show shows the value of the gauge up! increases the current value by 1 down! decreases the current value by 1
It should work like this:
```STk> (define the-g (make-gauge 0))
the-g
STk> (the-g 'up!)
1
STk> (the-g 'show)
1
```
3. Write a procedure `(make-counter init)` that returns a procedure which, when called, increases a counter by 1 and returns the counter value. The initial value of the counter is `init`. The procedure `make-counter` should create an object with local state, so that every time it is called it increases the counter by 1 and returns its value. Assume that `init` is a integer number. It should work like this: STk> (define c1 (make-counter 10)) c1 STk> (c1) 11 ; since 11 is 10+1 STk> (c1) 12 ; since 12 is 11+1
4. Write a procedure `(make-box init)` to create a box object. A box object is an object that keeps a value and accepts the following messages:
 Message Argument Definition show shows the value in the box update! replaces the current value with a new value reset! resets the original value

Python

1. Write in Python a function `every` that returns true if every element in a list satisfies a given predicate. This problem was assigned in the 1st midterm. It should work like this:
```>>> every(even,[1,3,7])
False
>>> every(even,[2,4])
True
```
2. Write in Python a function `check_interval` to count how many numbers in the range low to high are divisible by a number.
```>>> check_interval(3,7,2)
2   # in the range 3 to 7 2 numbers, 4 and 6, are divisible by 2
```
3. Write in Python a function thats adds each element of a list with the next element and returns a list of the results. The returned list should contain one less element than the original list. It should work like this:
```>>> add_pairs([1,2,3,4])
[3,5,7]
```
4. Write in Python a function that returns alternate elements from a list starting from the second element. [Hint: this is very simple in Python if you use list comprehensions. Look at the class notes for examples.] It should work like this:
```>>> every_other2([1,2,3,4,5,6,7,8])
[2, 4, 6, 8]
>>> every_other2([])
[]
>>> every_other2([1])
[]
```