Homework 03
Due: Friday, 10/21 at 11:59 pm
Download this assignment in pdf format or .tex source.
Exercise 1. Suppose you are given an unsorted array \(a\) of size \(n1\) where \(n = 2^B\) that contains all of the numbers \(0\) through \(n1\) (in an arbitrary order) except for a single missing value \(m\). The numbers are each represented in binary with \(B\) bits, so that \(a[i]\) stores the \(i\)th number, and \(a[i][j]\) is the \(j\)th bit of \(a[i]\). Use the divide and conquer strategy to devise an algorithm that finds the missing value \(m\) using \(O(n)\) bit comparison and swap operations. Use the Master Theorem to justify the running time of your procedure.
Hint. Note the similarity with the setup of RadixSort. While RadixSort uses \(O(B n)\) bit comparisons and swap operations, your algorithm must use only \(O(n)\) such operations.
Exercise 2. In class, we saw Dijkstra’s algorithm for the singlesource shortest path problem:
1
2
3
4
5
6
7
8
9
10
11
Dijkstra(V, E, u):
1. initialize d[u] = 0 and [v] = infinity for all v != u
2. maintain set S of finalized nodes, initially empty
3. while S != V do:
find node v in V  S with minimal d[v]
add v to S
for each neighbor x of v
update d[x] < min(d[x], d[v] + w(v, x))
endfor
endwhile
4. return d
For simplicity, we assumed that \(V = \\{1, 2, 3,\ldots,n\\}\) so that \(d\) is an array where \(d[x]\) stores the (weighted) distance from \(u\) to \(x\). This array, however, does not give the actual path from \(u\) to \(x\), but just the length of the shortest such path. Given a shortest path from \(u\) to \(x\), \(P = u e_1 v_1 e_2 v_2 \ldots v_{k1} e_k x\), we say that \(v_{k1}\) is \(x\)’s parent. That is, \(x\)’s parent is the next vertex from \(x\) along the shortest path from \(x\) to \(u\). Observe that \(x\)’s parent \(v\) is \(x\)’s neighbor satisfying \(d[x] = d[v] + w(v, x)\).

Write a modified version of
Dijkstra
calledDijkstraPath
that returns an array \(p\) such that for each vertex \(x\), \(p[x]\) stores \(x\)’s parent. Your algorithm should only differ fromDijkstra
in a few lines of (pseudo)code. 
Write a method
GetPath(p, u, x)
that given the array \(p\) returned byDijkstraPath
,GetPath(p, u, x)
returns the shortest path fromu
tox
. That is,GetPath(p, u, x)
should return an arraypath
of length \(k + 1\) wherepath[1] = u
,path[k + 1] = v
, and \(k\) is the number of hops on the shortest (weighted) path from \(u\) to \(x\) in \(G\). The running time ofGetPath(p, u, x)
should be \(O(k)\).