P1
Consider linearSearch and binarySearch from the Unit 1 notes.
The analysis in Section 8 shows that the worst case running time
in terms of number of operations for linearSearch on an array of
size $n$ (let's call
this $T_{ls,\text{worst}}(n)$) is
\[
T_{ls,\text{worst}}(n) = 2n + 1 \text{ operations}
\]
and the the worst case running time
in terms of number of operations for binarySearch on an array of
size $n$ (let's call
this $T_{bs,\text{worst}}(n)$) is
\[
T_{bs,\text{worst}}(n) = 5 \lg n + 4 \text{ operations}
\]
whereas the best case for each is
\[
T_{ls,\text{best}}(n) = 3 \text{ operations}
\]
for linearSearch and
\[
T_{bs,\text{best}}(n) = 5 \lg n + 4 \text{ operations}
\]
for binarySearch. Given that, here are some T/F questions to
see whether you understand the meanings of $O$, $\Theta$ and
$\Omega$ and how they're used to describe running time
functions:
- $T_{ls,\text{worst}}(n) \in \Theta(n)$
- $T_{ls,\text{worst}}(n) \in \Omega(1)$
- $T_{bs,\text{worst}}(n) \in O(n)$
- $T_{bs,\text{worst}}(n) \in \Omega(\lg n)$
- $T_{ls,\text{best}}(n) \in \Omega(n)$
- $T_{ls,\text{best}}(n) \in \Theta(1)$
- $T_{ls,\text{best}}(n) \in O(n)$
- $T_{bs,\text{best}}(n) \in \Omega(n)$
- $T_{bs,\text{best}}(n) \in O(\lg n)$
- $T_{bs,\text{best}}(n) \in O(n)$
P2
Algorithm: findFirstMissing
Input: $A$ and $B$, both sorted arrays of $n$ ints
Output: $j$, the least index such that $B[j]$ is not an
element of $A$, or 'NOT FOUND' if no such element of $B$ exists
j = -1, k = 0
while k ≠ NOTFOUND and j < n-1 do
j = j + 1
k = search(A,0,n-1,B[j]) ← we assume "search" is an algorithm for the search problem, with
if k = NOTFOUND the tweak that search(A,left,right,x) searches A[left],...,A[right]
return j i.e. we don't always start at index 0. We could equally easily use
else linearSearch, binarySearch or gallopSearch.
return NOTFOUND
I recommend tracing through this algorithm on sample
arrays like:
A: 3 5 6 11 15 16 17 20 where n = 8
B 3 5 11 15 17 18 20 21
Here's your problem: give a loop invariant for the while
loop that would allow you to prove that this algorithm is correct.
P3
A (directed) forest is a graph that consists of one or more disjoint
(directed) trees. A node $s$ in a forest is said to have a
unique distination if $s$ and all of its descendents have a
single, unique child until you get to a node with no children,
which is the "destination".
Consider the problem Unique Destination that takes a forest on
$n$ nodes, $\{0,\ldots,n-1\}$, and
a starting node $s$ and returns TRUE if $s$ has a unique
destination, and FALSE otherwise. The forest is repesented by
an array $P$ of length $n$ where $P[i] = j$ means that node
$i$'s parent is node $j$, when $j \neq -1$, and $i$ is a root
node if $P[i] = -1$. See the image to the right to see an
example drawn out.
The following algorithm solves the Unique
Destination. Analyze its best and worst case running
time. Note: The outer while loop does indeed terminate, as
long as the input really is a forest (i.e. no loops). If it
were to go on too long, you would eventually hit a node you'd
already visted, which would mean there was a loop.
Algorithm: uniqueDest(P,n,s)
Inputs: P an array of n integers such that P[i] = j means that the
parent of node i is node j if j ≠ -1, and i has no parent otherwise
s the starting node
Output: TRUE/FALSE a solution to the Unique Destination problem
next = s, count = 1
while count == 1 do
curr = next
count = 0, i = 0
while i < n do ← in this loop we count the number of children of curr and set next to the most recently seen child
if P[i] == curr
count = count + 1
next = i
i = i + 1
if count == 0
return TRUE
else
return FALSE
P4
One might note that from P3 that in the inner loop we don't
really need the exact number of children of node "curr". We
just need to know whether there are 0, 1 or more than one. So
we could cut out of that inner while loop early by changing it to:
while i < n and count < 2 do
How would that change the best and worst case running time functions?