COMP 410, Fall 2012
Sample problems for Midterm Exam 1
(more to come, these are a start, will add at the end)
1) (a) Given an array A of integers, sorted into ascending order,
design an efficient algorithm for finding is there is any
array subscript i where A[i] == i. What is the worst case run
time of your algorithm (in "Big-Oh" notation)?
(b) Do the same for an array A of non-negative integers, sorted in
ascending order. What is the worst case run time of your algorithm
(in "Big-Oh" notation)?
2) Prove by induction (make sure to show the base case,
the inductive hypothesis, and all steps in the proof)
Sum (from k=1 to N) of k is less than N^2
for all N >= 2
3) (a) Show the result of inserting these integers (in this order) into
an initially empty AVL tree:
2, 1, 4, 5, 9, 3, 6, 7
Make sure to show the tree after each insertion. I can give partial
credit is you give good detail. You might consider showing the
patterns we used to define the various insertion situations that
are possible.
(b) Show the tree after doing delete 4 on the result from (a)
(c) Show the tree after doing delete 9 on the result from (b)
4) The height of a tree that is only one node (no children) is zero.
Given this, work these problems (BST is Binary Search Tree):
(a) In a BST with N nodes, the maximum height is what? (in terms of N)
(b) In a BST of N nodes, the minimum height is what?
(c) In an AVL tree of 12 nodes, the maximum height is what?
(d) In an AVL tree of 12 nodes, the minimum height is what?
5) Consider this algorithm:
Take a Complete Binary Tree T. We dont know anything about it except that
it meets the requirements to be a BST. Start at the root. Select
at random one of the children and go to that child; count that
path as length 1. Select at random one of the children of this child.
Go to that child and increase the path length to 2. Continue to
select random children and counting the path length until you hit a
leaf. Lets say when we are done the path length we found is K.
Using this number K give bounds on the number of nodes in this tree.
6) We have a tree with the following properties:
(a) It is a binary tree.
(b) For each node R, all values in the subtree
rooted at R's left child are smaller than the value of R;
all values stored in the subtree rooted at R's right subchild
are greater than R's value.
This tree is a (circle one or more):
Binary Search Tree,
AVL Tree,
Left-Right Topo Tree,
Binary Heap
Splay Tree,
not something we have studied
7) We have a tree with the following properties:
(a) It is a binary tree.
(b) For any two paths P1 and P2 that go from root to a leaf,
the AbsoluteValue(length(P1)-length(p2)) is either 0 or 1.
This tree is a (circle one or more):
Binary Search Tree,
AVL Tree,
Left-Right Topo Tree,
Binary Heap
Splay Tree,
not something we have studied
8) (a) Take an initially empty BST and show the tree after doing
these insertions in this order:
2, 1, 4, 5, 9, 3, 6, 7
Show your work, show the intermediate trees so I can give partial
credit in case your final tree is incorrect.
(b) Show the tree you get when you do delete(4) starting with the
result of (a)
(c) Show the tree you get when you do delete(9) starting with the
result of (b)
9) Take the axioms defining the STACK that we studied in class.
Let's add some new behavior to get a new type we will call
SWAPSTACK. We want to keep the operations we have (push, pop,
top, size, empty), but we want to add this operation:
swap: SWAPSTACK --> SWAPSTACK
It will take a stack, and swap the top two elements. This means
that if 12 is on top the initial stack, and 6 is the second element,
then the resulting stack will have 6 on top, and 12 as the second
element. Be careful to consider what swap does if you call it on
a stack that does not contain at least two elements.
10) Describe a data structure that will support the stack operations
push, pop, top, empty, and size, as well as these two additional
operations:
findMax
findMin
These will return the largest (smallest) value stored in the stack
regardless of where they are in the element order.
Your data structure must allow each operation to be performed in
worst-case constant time.
11) Consider the following data structure operations and their worst
case run times. Fill in the table with numbers to demonstrate
their relative efficiencies.
What I want is for you to replace the ? with a number that
gives the worst case run time of the algorithm on the problem
size at the top of the column. If you need details to help
explain your answer, you may add footnotes.
Use scientific notation to help with any larger numbers.
N: 4 1024 1,073,741,824 (2^30)
bubble sort list
of length N ? ? ?
insert in AVL tree
of N nodes ? ? ?
push on a stack
of size N ? ? ?
remove from queue
of length N ? ? ?
find in BST with ? ? ?
N nodes
in-order traversal on ? ? ?
a BST with N nodes
building a BST with ? ? ?
N nodes
locate item in ordered ? ? ?
list of length N
find in splay tree with ? ? ?
N nodes (remember
the splay op)
12) (a) Below are two hash tables. The left one will use linear probing
to resolve collisions. The right one will hash into lists to resolve
collisions. Fill in each table with the following input items in
the order given left to right:
alpha beta gamma delta epsilon zeta eta theta iota kappa lambda
Use this hash function:
take the position in the alphabet of the first third letters,
add them; then multiply by the length of the word; then mod
the result by 13.
Example: alpha a is 1, p is 16, sum 17. 17*5 is 85. 85 mod 13 is 7
so alpha hashes to slot 7.
an alphabet, with ordinal positions, for your viewing pleasure
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
linear hash into lists
probing
0: _________ 0: _____
1: _________ 1: _____
2: _________ 2: _____
3: _________ 3: _____
4: _________ 4: _____
5: _________ 5: _____
6: _________ 6: _____
7: _________ 7: _____
8: _________ 8: _____
9: _________ 9: _____
10: _________ 10: _____
11: _________ 11: _____
12: _________ 12: _____
(b) We ended up storing 11 items in the tables, and let's say we
expected to have 11 items for storage. Was the choice of 13 for
table size a good one for the linear probing table? If so, cool...
if not, what size would have been better?
(c) Same question for the hash-into-lists table... was 13 a good size?
If so, cool, ... if not, what size would have been better?
13) Consider this BST:
gamma
. .
. .
beta rho
. . . .
. . . .
alpha delta kappa theta
. . . . .
. . . . .
eta iota omicron sigma zeta
.
.
lambda
(a) list the node values in the order given by a pre-order traversal
gamma beta alpha delta eta rho kappa iota omicron lambda theta sigma zeta
(b) list the node values in the order given by an in-order traversal
alpha beta delta eta gamma iota kappa lambda omicron rho sigma theta zeta
(c) list the node values in the order given by a post-order traversal
alpha eta delta beta iota lambda omicron kappa sigma zeta theta rho gamma
14)(a) Show the result of inserting these integers (in this order) into
an initially empty Splay tree:
8, 1, 4, 2, 5, 15, 7, 3, 6
Make sure to show the tree after each insertion. I can give partial
credit if you give good detail. You might consider showing the
patterns we used to define the various insertion situations that
are possible.
(b) Show the tree after doing delete 4 on the result from (a)
(c) Show the tree after doing delete 7 on the result from (b)
(d) Show the tree after doing find 2 on the result from (c)
(e) Show the tree after doing find 6 on the result from (d)