If we have two strictly increasing integer sequences:
$\begin{aligned} &a_0,a_1, .... a_{n1}\\ &b_0,b_1,...,b_m1 \end{aligned}$
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:
$\begin{aligned} a&=\{a_0,a_1,\ldots,a_{78}\}\\ b&=\{b_0,b_1,\ldots,b_{44} \} \end{aligned}$
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 $a$ and $b$.
Input $x + y$ 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 pseudocode 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 $N$ nodes.
If the recursive version runs in $O(f(N))$ and the iterative function runs in $O(g(N))$, what is $f(n)/g(n)$?
A certain sorting function is described in pseudo code below. Given a multiset $a_0$ it returns the multiset sorted in increasing order.
1 2 3 4 5 6 7 8 9 10 

swap(array,x,y)
swaps the element at index $x$ element in array
with the item at index $y$.
Suppose the function is given an array $A$ of length $n$ that is a worstcase input, i.e. swap
is called the maximum possible number of times, how many times is swap
called?