Final Exam Solutions
CS 213 Fall 2003

*********
Problem 1
*********
1. V = 2^{n+1} - 1

2. V = 2^{2 - 2^{k-1}}

Note: 2^n denotes 2 to the power n

*********
Problem 2
*********
A. x->b->j.h[3]
B. x->h[1]
C. x->k->i

*********
Problem 3
*********
N=7

*********
Problem 4
*********
summer
spring
fall
winter

*********
Problem 5
*********
Part 1
mhm
mmm
mmh
---
hhm
mmh
mhh

Part 2
hhh
hhh
hhh
---
hhh
hhh
hhh

*********
Problem 6
*********
1. A B 
2. C D
3. D
4. C 

*********
Problem 7
*********
1. Could be either 3, 4, or 5
2. 3
3. 3
4. Could be either 3 or 4

*********
Problem 8
*********
1. largest value = 2
2. largest value = 2 
3. largest value = 4

*********
Problem 9
*********
A, D, and H

**********
Problem 10
**********
Before child exits
8 letters read
1 number read

Immediately before parent exits:
3 letters read since child exited
3 numbers read since child exited

**********
Problem 11
**********
Part 1: Possible output sequences:
34
43
39
93
36
63

Part 2: Possible output sequences:
1 
2