If we have two strictly increasing integer sequences:
\[\begin{align} &a_0,a_1, .... a_{n-1}\\ &b_0,b_1,...,b_m-1 \end{align}\]
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{align} a&=\{a_0,a_1,\ldots,a_{78}\}\\ b&=\{b_0,b_1,\ldots,b_{44} \} \end{align}\]
your task is to find the value of the variables in thewhileloop's conditional statement. Specifically find the value ofxandyso that the program runs smoothly given the arrays \(a\) and \(b\).
Input \(x + y\) as your answer.
A binary search tree orBSTis 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.
考虑到功能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 aperfectly 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 multi-set \(a_0\) 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 \(x\) element inarraywith the item at index \(y\).
Suppose the function is given an array \(A\) of length \(n\) that is a worst-case input, i.e.swapis called the maximum possible number of times, how many times isswapcalled?