```
COMP 410 (updated Fall 2015)

Sample problems for Midterm Exam 1

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)?

Here we have numbers that can be negative and positive, and they
are sorted.  We binary search on the array, looking for A[i]==i
we can use the fact that they are sorted to decide which half to
throw away each test.  This approach works if we allow duplicates,
or if all elements are unique values.
O(log N) for N elements in the array

(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)?

We have two situations. First assume there are no duplicates.
We now have sorted unique integers and the smallest possible
element is 0.  So we check to see if A[0]==0.  If so, then there
is some A[i]==i (at least 0, possibly more but we did not need
to find them all... we just need to answer "is there some i".
If A[0] is not 0 then there can be no other A[i]==i.
O(1) worst case complexity.

Second situation: if there are duplicates allowed
Here we have 0 as the lowest possible element, but we can also
have sequences of the same element in places in the array.
Now, checking simply for A[0]==0 is not enough... for example,
if all elements in the array are 7, then A[0] is not 0, but A[7]
is 7.  So we are back to doing binary search to find the answer.
O(log N) wirst case.

2) (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)

Can't easily draw it here.
You can use one of the animations to check your work

3) 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?
here is one example: 12 nodes, height 4, meets AVL conditions

19
.      .
.            .
7                 31
.  .               .   .
.    .            .       .
3       11         17         43
.                  .          .  .
.                  .          .    .
2                  14         34    55
.
.
77

(d) In an AVL tree of 12 nodes, the minimum height is what?
This is the same as the height of a complete binary tree
with 12 nodes.

4) Consider this algorithm:
Take a complete binary tree T.  We dont know anything about it
except that it meets the requirements to be a complete binary
tree.  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 (node
with no children).  This means that if you come to a node with
one child, you will take the path to that child.

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.

TBD

5) 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):
Binary Search Tree,
AVL Tree,
Left-Right Topo Tree,
Binary Heap
Splay Tree,
not something we have studied

BST, AVL, SPlay all work here

6) 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):
Binary Search Tree,
AVL Tree,
Left-Right Topo Tree,
Binary Heap
Splay Tree,
not something we have studied

binary heap (but we are not doing binary heaps on this exam);
a binary heap is structurally a complete binary tree, which
has the specified property.  None of the other structures
given will always have the property.
BTW, there is no such thing as a left-right topo tree (not
that I know or anyway).

7) (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)

Can't easily draw it here.
You can use one of the animations to check your work

8) 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.

None of the axioms for a normal stack will change.
The "swap" operation is not canonical, so all we need to do
is add axioms for how swap does on new, and how it does on push.

one way:
swap(new) = new
swap(push(new,e)) = push(new,e)
swap(push(push(S,e),f)) = push(push(S,f),e)

another way:
swap(new) = new
swap(push(S,e)) = if empty(S) then push(S,e)
else push(push(pop(S),e),top(S))

9) 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.

Use a normal stack (we can use an array) and add to it two more
stacks: one for min, one for max.  When we push an item we not
only change the top pointer, we check to see if the item pushed
is larger than the item pointed to by the top of the max stack
(smaller than the top of the min stack).  If it is we push the
array subscript of the item pushed onto the max stack (push the
item location onto the min stack).  When we pop, we check to see
if we are popping the item that is max (top max stack); also check
min.  If we are then pop the max stack (min stack).
All stack ops are contant time so the getMax is as well (since it
is a top operation on a stack).

We cannot do this simply with min and max pointers like we do top.
If we pop the item that is currrent max, say, we have to find the
next max by scanning the stack, which is O(N) for stack size N.

10) 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

Use scientific notation to help with any larger numbers.

N:                        4     1024      1,073,741,824 (2^30)

bubble sort list
of length N            ?     ?          ?
O(N^2)                    16    2^20       2^60

insert in AVL tree
of N nodes             ?     ?          ?
O(log N)                  2     10         30

push on a stack
of size N              ?     ?          ?
O(1)                      1     1          1

remove from queue
of length N            ?     ?          ?
O(1)                      1     1          1

find in BST with          ?     ?          ?
N nodes
O(N) worst case           4     1024       2^30

in-order traversal on     ?     ?          ?
a BST with N nodes
O(N)                      4     1024       2^30

building a BST with       ?     ?          ?
N nodes
O(N^2)                    16    2^20       2^60

locate item in ordered    ?     ?          ?
list of length N
O(log N) binary search    2     10         30

find in splay tree with   ?     ?          ?
N nodes (remember
the splay op)
2N which is O(N)          4     1024       2^30
(worst)
O(log N) amortized        2     10         30

11) 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

12)(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)

ANS: use animation tool

13) a) Take the following numbers and show the Binary Heap that
results from build it by 13 inserts (in the order shown)
(draw it as a tree)

12, 3, 17, 45, 0, 1, 14, 9, 55, 73, 5, 21, 34

b) Take the same numbers and show the heap that results from
O(N) direct build method (draw as a tree)

c) Show the array that represents the heap tree from part (b)

ANS: use the java script code we did in class to get the two forms
of heap array

14) Give a tight big-Oh run-time analysis in terms of N for each
of the following code fragments.

a)   public static long A (int N) {
if (N <= 1) return 1;
return N * (N-1) * A (N - 1);
}
ANS: O(N)

b)   sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
sum++;
ANS: O(N^2)

c)   sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i*i; j++)
for (k=0; k < j*j; k++)
sum++;
ANS: O(N^7)

15) a) For the following minimum binary heap (drawn as a complete
binary tree) fill the items into the array below in the correct
positions for the way a binary heap is normally represented with
an array.

4
.     .
.          .
.               .
11                     6
.   .                  .   .
.       .               .      .
.         .             .         .
13          21          8          23
.  .        .  .        .  .
.    .      .    .      .    .
27    14    29    33    12    19

_______________________________________________________________
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

_______________________________________________________________
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
|   |  4| 11|  6| 13| 21|  8| 23| 27| 14| 29| 33| 12| 19|   |   |
array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

b) Using this array representation, show the subscript
calculations needed to find the children of the node
with value "13"
ANS: 13 is at subscript 4
the children of 13 are at 2*4=8, and 2*4+1=9

c) Using this array representation, show the subscript
calculations needed to find the parent of the node
with value "33"
ANS: 33 is at subscript 11
the parent of 33 is at floor(11/2) = 5

16) For the heap in problem (15), show the heap that results after
doing a single removeMin operation.  Show the steps involved in
rearranging the heap elements so that the new minimum ends up at
the root.  Show the head both in the binary tree representation
and in the array implementation.

ANS: use the javascript code we did in class

17) For the following items in the order given, construct
a minimum binary heap.  Use the O(N) "build" algorithm we studied.
Show the steps in your work.

6, 3, 29, 21, 7, 2, 19, 24, 8, 4, 61, 16, 9

ANS: use the javascript code we did in class

18) a) Do the same as problem (16) for the heap built in problem (17).

b) Starting with the heap built in (17) show the heap that results
from doing insert(11). Show both the tree and the array.

ANS: use the javascript code we did in class

```