# Assignment 1

## Due Jan 27 on line

1. Here is a recursive definition of a function defined over the non-negative integers designed to check your preparation for this course:
f(i, j) = 0 when j = 0
f(i, j) = i + f(i, j–1) otherwise

What is this function?
a) f(i, j) = i + j
b) f(i, j) = i × j   –   the correct answer
c) f(i, j) = ij
d) f(i, j) = i ÷ j
e) f(i, j) = ij

2. Another question to check your preparation: If a set has n elements, how many subsets of the set are possible?
a) n2
b) n!
c) 2n   –   the correct answer
d) log n
e) n × (n – 1)

3. Given a binary tree, if you recursively traverse the tree, processing each item in the tree after you process both subtrees, this is called:
a) Pre-order traversal
b) In-order traversal
c) Post-order traversal   –   the correct answer
d) Depth-first traversal

4. Suppose you have a set of items and a relationship between items that may be either present or absent. This can be modeled as a
a) Digraph
b) Graph   –   the correct answer (see below)
c) Tree
```     ~dwjones/2820log xxxx