AS ALGO 2

Problem 1

$$\begin{array}{rl}& \text{SortPoints}(A[\mathrm{1..}n]):\\ & buckets\leftarrow \text{repeat }n[]\\ & \text{for }a\in A:\\ & buckets[\lfloor a^{2}n\rfloor ]\leftarrow a\\ & \text{for }bucket\in buckets\\ & \text{InsertionSort}(bucket)\\ & \text{return }\text{concat}(buckets)\end{array}$$

The concentric circles of radii $0,\sqrt{1/n},\sqrt{2/n},\dots ,\sqrt{1}$ are such that $\pi r_{i+1}^2-\pi r_i^2=1/n$ for all $0\le i\le n-1$, and thus may delimit the buckets. Since the expected size of each bucket is $1$ due the uniform distribution hypothesis, each call to $\text{InsertionSort}$ takes constant time on average, and it follows that $\text{SortPoints}$ runs in $O(n)$ time.

---

Problem 2

Let the hash values of the $n$ keys be independent and uniform in $\{1,\dots ,m\}$. The probability that all $n$ are distinct is

$p(n,m)=\frac{m(m-1)\cdots (m-n+1)}{m^n}={\prod }_{i=0}^{n-1}\left(1-\frac{i}{m}\right).$
Using the bound $1-x\le e^{-x}$ gives

$$\begin{array}{r}p(n,m)=\prod _{i=0}^{n-1}(1-\frac{i}{m})\le \prod _{i=0}^{n-1}\exp (-\frac{i}{m})=\exp (-\sum _{i=0}^{n-1}\frac{i}{m})=\exp (-\frac{n(n-1)}{2m}),\end{array}$$

as required.

The exponent is approximately $(-n^2/(2m))$. If $n=\omega (\sqrt{m})$ then $\frac{n^2}{2m}\to \infty$ and $p(n,m)\to 0$ rapidly. Thus once $n$ passes order $\sqrt{m}$ the probability of avoiding any collision drops quickly to zero.

---

Problem 3

Edges have three properties: $e.1$ and $e.2$ are the vertices that $e$ connects, and $e.w$ is the weight of $e$. The edge connecting $x$ and $y$ (that is, $e$ such that $e.1=x$ and $e.2=y$ or vice versa) may be denoted by $e_{x,y}$. Suppose $T$ is a minimum spanning tree of $G$ and we decrease the weight of an edge not in $T$. $\text{FindMST}$ takes as input $T$ and the modified edge $e$.

$$\begin{array}{rlr}& \text{FindMST}(T,e):& \\ & P\leftarrow \text{concatenate}([e],\text{FindPath}(T,e.1,e.2))& \\ & & \\ & maxWeightEdge\leftarrow e& \\ & & \\ & \text{for }p\in P:& \\ & \text{if }p.w>maxWeightEdge.w:maxWeightEdge\leftarrow p& \\ & & \\ & \text{return }P+e-maxWeightEdge& \\ & & \\ & & \\ & & \\ & \text{FindPath}(T,x,y):& \\ & E\leftarrow \text{Stack}()& \\ & E.\text{push}(x)& \\ & \text{for }v\in V(T):v.\text{path}\leftarrow [],v.\text{visited}\leftarrow \text{False}& \\ & x.\text{visited}\leftarrow \text{True}& \\ & \text{While }E:& \\ & v\leftarrow E.\text{pop}()& \\ & \text{for }w\in N(v)\text{ such that }w.\text{visited}=\text{False}:& \\ & w.\text{path}\leftarrow v.\text{path}.\text{append}(e_{v,w})& \\ & \text{if }w=y:\text{return }w.\text{path}& \\ & E.\text{push}(w)& \\ & w.\text{visited}\leftarrow \text{True}& \end{array}$$

The algorithm works by finding the unique cycle $C$ in $T+e$, and deleting the maximum weighted edge $m$ to obtain a new tree $T^{\prime }$.

Suppose $T^{\prime }$ is not a minimum spanning tree in the new graph. There must exist another minimum spanning tree $T^{\prime \prime }$ with $w(T^{\prime \prime })<w(T^{\prime })=w(T)+e.w-m.w$. $T^{\prime \prime }$ must contain $e$, since if it didn’t, it would contradict the minimality of $T$ with the original weights.

Consider $T^{\prime \prime }-e$. It has two connected components. There must exist edges in $C$ which are not in $T^{\prime \prime }$, since $T^{\prime \prime }$ is a tree. Further, there must exist an edge $k$ in $C\setminus E(T^{\prime \prime })$ which connects the two connected components of $T^{\prime \prime }$: If all the edges of $C$ connected vertices in the same connected component, it would imply $e.1$ and $e.2$ lie in the same connected component - a contradiction. Thus, $T^{\prime \prime }-e+k$ is a spanning tree. Now,

$$w(T^{\prime \prime }-e+k)=w(T^{\prime \prime })-e.w+k.w⩽w(T^{\prime \prime })-e.w+m.w<w(T).$$

Since $T^{\prime \prime }-e+k$ does not contain $e$, this contradicts the minimality of $T$.

$\text{FindPath}$ runs in $O(V+E)$ time. Since $T$ is a tree, this reduces to $O(n+n-1)=O(n)$ for a tree with $n$ nodes. The maximum length of the cycle $P$ in $\text{FindMST}$ is $n$ for a graph $G$ with $n$ nodes. Thus, $\text{FindMST}$ runs in $O(n)$ time.

---

Problem 4

Suppose for every cut $(A,B)$ of the graph $G$, there exists a unique minimum weight crossing edge $e$. Suppose $T$ is a minimum weight spanning tree which does not contain $e$. Consider the graph $T+e$. Since $T$ is a tree, $T+e$ must have exactly one cycle $C$ containing $e$. Clearly, $C$ must also have an $A,B$ crossing edge which is not $e$. Call this edge $e^{\prime }$. Let $T^{\prime }=T+e-e^{\prime }$. $T^{\prime }$ does not contain any cycles, since $C$ contained $e^{\prime }$. If $e^{\prime }$ connected the vertices $x$ and $y$, $C$ provides a path between $x$ and $y$ through $e$. Thus, $T^{\prime }$ is connected. Since $e$ is the minimum weight $A,B$ crossing edge, $T^{\prime }$ has lower weight than $T$, a contradiction. Thus, for every cut $A,B$, a minimum weight spanning tree must contain the minimum weight $A,B$ crossing edge.

Suppose $G$ has $n$ vertices. Pick a point $x_1\in V(G)$ and consider the cut $\{x_1\},V(G)\setminus \{x_1\}$. Let $e_1=(x_1,x_2)$ be the minimum weight crossing edge. Any minimum weight spanning tree must contain $e_1$. Next, consider the cut $\{x_1,x_2\},V(G)\setminus \{x_1,x_2\}$. Let $e_2$ be the minimum weight crossing edge, which again must be contained in any minimum weight spanning tree. Proceeding in this manner, we obtain $n-1$ edges $e_1,\dots ,e_{n-1}$ which must be in every minimum weight spanning tree. Since any spanning tree of $G$ has exactly $n-1$ edges, this shows that the minimum weight spanning tree of $G$ is uniquely determined.

The converse is not true. Consider the following graph:

It has a unique minimum spanning tree, namely, the entire graph, but the cut displayed does not permit a unique minimum weight crossing edge.

---

Problem 5

$$\begin{array}{rl}& \text{FastMultiply}(x,y,n):\\ & \text{if }n=1:\text{return }x\cdot y\\ & m\leftarrow \lfloor n/2\rfloor \\ & a\leftarrow \lfloor x/2^m\rfloor \\ & b\leftarrow x\mathrm{mod}{2}^m\\ & c\leftarrow \lfloor y/2^m\rfloor \\ & d\leftarrow y\mathrm{mod}{2}^m\\ & e\leftarrow \text{FastMultiply}(a,c,m)\\ & f\leftarrow \text{FastMultiply}(b,d,m)\\ & g\leftarrow \text{FastMultiply}(a-b,c-d,m)\\ & \text{return }{2}^{2m}e+2^m(e+f-g)+f\end{array}$$

$\text{FastMultiply}$ uses the identity

$$(2^{m}a+b)(2^m+d)=2^{2m}ac+2^m(ac+bd-(a-b)(c-d))+bd.$$

Multiplication by powers of $2$ can be accomplished by bitshifting in $O(n)$ time. Thus, we have the following recurrence:

$$T(n)=3T(\lfloor n/2\rfloor )+O(n).$$

By the master theorem, $T(n)=O(n^{{\log }_{2}3})\approx O(n^{1.58})$.

---

Problem 6

Let $A$ be a fixed point on the circle. We will represent points on the circle by their clockwise angle from $A$, in the range $[0,2\pi )$. A chord on the circle connecting points $p$ and $q$ is denoted by $(p,q)$. The chords are supplied as a list $L=[(a_1,b_1),(a_2,b_2),\dots ,(a_n,b_n)]$. The list is preprocessed such that $a_i<b_i$ for each $i$ and $a_1<a_2<\cdots <a_n$, which can be done in $O(n\log n)$ time. For a chord $(p,q)$, we distinguish between its start point $p$ and its end point $q$.

$\text{FindIntersections}(L)$ accepts a preprocessed list of chords $L=[(a_1,b_1),(a_2,b_2),\dots ,(a_n,b_n)]$ and returns $(count,S)$, where $count$ is the number of intersections between the chords listed in $L$ and $S$ is $L$ sorted by its second coordinate.

$$\begin{array}{rl}& \text{FindIntersections}(L):\\ & \\ & \text{if }|L|=1:\text{return }(0,\text{map}(\text{snd},L))\\ & \\ & (L_1,L_2)\leftarrow \text{Split}(L,|L|/2)\\ & (n_1,S_1)\leftarrow \text{FindIntersections}(L_1)\\ & (n_2,S_2)\leftarrow \text{FindIntersections}(L_2)\\ & M\leftarrow \text{Merge}(\text{map}(\text{fst},L_2),S_1,S_2)\\ & \\ & count\leftarrow 0,depth\leftarrow 0\\ & \text{for }m\in M:\\ & \text{if }m\in \text{map}(\text{fst},L_2):depth=depth+1\\ & \text{else if }m\in S_2:depth\leftarrow depth-1\\ & \text{else if }m\in S_1:count\leftarrow count+depth\\ & \text{return }(n_1+n_2+count,\text{Merge}(S_1,S_2))\end{array}$$

$\text{map}(\text{fst}(L_2))$ projects the tuples in $L_2$ to their start points: $\text{map}(\text{fst},[(a_1,b_1),(a_2,b_2),\dots ,(a_n,b_n)])=[a_1,a_2,\dots ,a_n]$.

Analysis

$\text{FindIntersections}(L)$ makes two recursive calls with inputs of size $|L|/2$, and spends $O(n)$ time doing non-recursive work: merging is $O(n)$, and the membership tests in the for loop can be achieved in $O(1)$ time by flagging the elements of $S_1$, $S_2$, and $\text{map}(\text{fst}(L_2))$ with markers prior to merging. Thus, the algorithm runs in $O(n\log n)$ time.

Correctness

The algorithm is trivially correct for $n=1$. For $k>1$, suppose the algorithm is correct for all $n<k$. Then, the algorithm correctly computes $n_1$ and $n_2$, which are the number of pairs of intersecting chords such that both of them lie in $L_1$ and $L_2$ respectively. It remains to compute the number of intersecting pairs where one chord lies in $L_1$ and the other lies in $L_2$. Suppose $(a,b)\in L_1$ and $(c,d)\in L_2$ are two such chords. Given our preprocessing of $L$, this happens iff $a<c<b<d$. Thus, for each $(c,d)\in L_2$, it suffices to count the number of chords in $L_1$ which have their end point between $c$ and $d$. Equivalently, for each $(a,b)\in L_1$, we can count the number of $(c,d)\in L_2$ such that $c<b<d$. This is exactly what the for loop does.