If we have two strictly increasing integer sequences:
The following program finds the number of integers common to both sets. That is the cardinality of the set.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
If it is given the following two sets as input:
your task is to find the value of the variables in the while
loop's conditional statement. Specifically find the value of x
and y
so that the program runs smoothly given the arrays and .
Input as your answer.
A binary search tree or BST is a binary tree where each node has a key such that the key in any node is larger than the key of its left child, and less than any node to the right.
Consider the function exists(tree, value)
, it verifies if a node with a certain value exists. It can be implemented both iteratively and recursively in pseudo-code as follows:
Iterative version
1 2 3 4 5 6 7 8 9 10 |
|
Recursive version
1 2 3 4 5 6 7 8 9 10 11 |
|
Consider the worst case performance of both methods. Suppose they are only run on a perfectly balanced tree(every non leaf node has two children. Every leaf has no children) with nodes.
If the recursive version runs in and the iterative function runs in , what is ?
A certain sorting function is described in pseudo code below. Given a multi-set it returns the multi-set sorted in increasing order.
1 2 3 4 5 6 7 8 9 10 |
|
swap(array,x,y)
swaps the element at index element in array
with the item at index .
Suppose the function is given an array of length that is a worst-case input, i.e. swap
is called the maximum possible number of times, how many times is swap
called?