When you need to do a repetitive task, like working through all elements in a list to find a prime or searching a map until you've found all of the gold, loops are a goto tool.
If we have two strictly increasing integer sequences:
\[\begin{align} &a_0,a_1, .... a_{n1}\\ &b_0,b_1,...,b_m1 \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 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?
Problem Loading...
Note Loading...
Set Loading...