## CS 315: Example Questions for Final Exam

#### Trees:

- Why is it important that a search tree be balanced?
- What is the most significant difference between B-trees
and balanced binary trees?

#### Sparse Arrays:

- What is the motivation for having special techniques to store
sparse arrays?

#### Pattern Matching:

- Describe three kinds of problems that can be done using pattern
matching.
- Describe the rules for matching a pattern variable.

#### Java API's:

- Suppose that data items are stored in a
`HashMap`
and that the items need to be sorted. How would this be done
using the Java libraries?
- Suppose that we would like to sort a set of students, first by
age in years, and within the same age, by GPA. How would this be
done using the Java libraries?

#### Hashing:

- How does the Big O of hashing compare with that of AVL trees?
- Describe how hashing with buckets simplifies the code required.

#### Priority Queues:

- Describe three uses of priority queues.

#### Sorting:

- What is the Big O of Insertion Sort? Is it stable? In-place?
What would be an appropriate use of Insertion Sort, and why?
- Give an advantage and a disadvantage of Merge Sort of an array.

#### Graphs:

- Give examples of problems whose representations are graphs.
- Depth-first search of a tree is easily done using a recursive
function. How is search of a graph different?

#### MapReduce:

- How do the computer systems on which MapReduce runs differ
from ordinary computers?
- Describe how MapReduce provides fault tolerance.

#### Vocabulary:

Briefly and clearly define the following terms: ... terms chosen
from the vocabulary lists on both study guides.