[SOLVED] Scheme CSE 1729 Introduction to Principles of Programming May, 2019

CSE 1729Introduction to Principles of Programming May, 2019
FINAL EXAM 3 A
Instructions
Name:
Questions
1. Write a Scheme function :
2. Write Scheme expressions using only variants of cXr to get the given outputs. These should be single simple Scheme expressions and not functions or lambdas.
Where cXr is any combination of car and cdr functions.
a Given
define x a b c
write a simple Scheme cXr expression to get c.
b Given
define x 1 2 3 4 5
write a simple cXr Scheme expression to get 3.
c Given
define x b a z c d
write a simple cXr Scheme expression to get z.
Given
define x 1 2 3 4 5
write a simple cXr Scheme expression to get 5.
d Given
define x a b c
write a simple cXr Scheme expression to get a.
Closed book, closed notes, no computers, no cell phones. Assume all code snippets work in Scheme, unless stated otherwise. All numbered problems are of the same value.
1

e Given
define x 1 2 4 5
write a simple cXr Scheme expression to get 4.
f Given
define x a b c
write a simple cXr Scheme expression to get b.
g Given
define x a
write a simple cXr Scheme expression to get a.
h Given
define x 1 2 3
write a simple cXr Scheme expression to get 3.
3. Given the Scheme procedures,
define x 25define c1
begin set! x define c2
begin set! x define c3
begin set! x
x 5 display x display
x 2 display x display
x 10 display x display
What is the output of the following?begin c1 c2 c3
4. Given the Scheme procedures,
define x 5define c1
begin set! x define c2
begin set! x define c3
x 5 display x display
x 2 display x display
begin set! x
What is the output of the following?
x 10 display x display
2

begin c1 c2 c3
5. Given the four integer values: 10, 20, 30, 40. Build a minheap, using our heap representation.
6. Given the four integer values: 5, 8, 7, 11. Build a minheap, using our heap representation.
7. Dene a resursive Scheme procedure rac with one formal parameter lst. So, rac lst returns the last element of lst.
For example:
rac 1 2 3 3
rac a
a
8. Dene a resursive Scheme procedure reverse with one formal parameter lst. So, reverse lst returns the lst in reverse order.
For example:
reverse 1 2 3
3

3 2 1 reverse a a
9. Write a recursive Scheme procedure powersof2 that takes an integer n and returns the list 124816322n.
Examples,
powersof2 4 1 2 4 8 16
powersof2 6 1 2 4 8 16 32 64
10. Write a recursive Scheme procedure genlist that takes three arguments. Two integer argu ments: start and end and a function argument f. The function genlist returns a list of the values f start, f start1,, f end.
For example,
genlist 1 10 lambda xx x 1 4 9 16 25 36 49 64 81 100
4

11. Write a recursive Scheme produre harmonicsum that takes positive integer actual parameter n and returns the harmonic sum,
1111. 23n
12. Using a listrepresentation of a set: Write a recursive Scheme procedure adjoinset that takes two arguments: x and a set S. This procedure determines if x is in the set S. If x is in S, then adjoinset returns t, otherwise it returns f.
13. Write a recursive Scheme procedure stream2list that takes two two arguments: a stream str and an integer n. The procedure stream2list returns a list of the rst n elements of the stream str.
For example suppose we dene: require srfi 41
define intsfrom k streamcons k
5

Then
intsfromk 1
define intstream intsfrom 1stream2list intstream 0

stream2list intstream 2
1 2
stream2list intstream 10 1 2 3 4 5 6 7 8 9 10
14. Given the standard dentions for streams, write a Scheme procedure: appendstreamsstr1 str2 that returns a stream containing all of the elements of str1 followed by all of the elements of str2.
definesyntax consstream syntaxrules
consstream head tail cons head delay tail
define streamcar x car x
define streamcdr x force cdr x
define streamnull? null?
6

15. Draw boxandpointer diagrams for a a b c
b a b c
16. Draw boxandpointer diagrams for a a b
b a b c
17. Bonus Question Dene a recusive Scheme function, named rdc, which takes a list lst as an argument. Then rdc lst returns all but the last element of lst.
Your answer must be recursive and it must not use Schemes reverse procedure. Tail recursion might help.
For example,
rdc 1 2 3 4 1 2 3
rdc
7

rdc a
rdc a b a
8