# Topic 3: Sorting and Selection

## Problem 1
Describe and analyze (correctness and runtime) an efficient algorithm for the following task: Given $k$ sorted arrays, each of length $n$, combine them into a single sorted array of all $kn$ items.

### Solution:

We create $k$ different queues where each queue consists of one of the $n$ length arrays. We then create an empty $n \cdot k$ length array to fill up. We then compare the top element of each of the $k$ queues, and then pop the smallest element from this comparison and put it in into the array. Since we have $k$ queues and each queue has one top element, finding the minimum from the top level elements will involve $k$ comparisons, assuming all of the queues are filled. We then repeat this until each queue is flushed of all of its elements. If all of the queues are flushed at the end, the runtime of the algorithm is $O(k^{2}n)$. The space complexity is $O(k)$ to store the pointers.

## Problem 2
You have a bag of $n$ nuts and $n$ bolts of close but different sizes. In this bag, each nut matches exactly one bolt. Your goal is to pair up each nut with its correct matching bolt.

You cannot look at a nut or bolt and assess its size, however you can perform a test: try to attach a single bolt and nut, and you'll find that the attachment is either perfect, too loose (the nut is bigger than the bolt), or doesn't fit (the nut is smaller than the bolt).

Design and analyze (in terms of correctness and runtime) an efficient algorithm to pair up the nuts and bolts. The runtime should be evaluated in terms of the number of nut-bolt tests you perform.

### Solution:

array bolts[n]
array nuts[n]
new array nutsSmallerThanBolti
new array nutsLargerThanBolti
for (each i in bolts, each j in nuts; i++, j++)
{
    if (bolts[i] != nuts[j])
        sortBolt(bolts[i], nuts[n])
    else
    {
        if (bolts[i] < bolts[i+1])
            sortBolt(bolts[i], nutsLargerThanBolti)
        else if (bolts[i] > bolts[i+1])
            sortBolt(bolts[i], nutsSmallerThanBolti)
    }
}
helper function sortBolt(bolt, nutsArray)
{
    for (each j in nutsArray)
    {
        if (bolt > nutsArray[j])
            add nuts[j] to nutsSmallerThanBolti
        else if (bolt < nutsArray[j])
            add nuts[j] to nutsLargerThanBolti
    }
}

Analysis:
Worst case run time = $n^2$
Best case run time = $n \log n$

## Problem 3
You are given two sorted lists of size $m$ and $n$ and a parameter $k \leq m+n$.

Describe and analyze an efficient algorithm to compute the $k$th smallest element in the union of the two lists.

### Solution:

Description: We look at the index $\frac{k}{2}$ in both of the lists. This way the combined sublists to the left of these indices contain at most the k smallest elements. Thus, we can guarantee that the value of the kth smallest element will be *at most* one of the indices we have selected. This happens if $m[\frac{k}{2}] = n[\frac{k}{2}]$, in which case we take one of them and are done. If $m[\frac{k}{2}] \neq n[\frac{k}{2}]$, we take the left part (indices 0 to $\frac{k}{2}$) of the array where the element at index $\frac{k}{2}$ is smaller and discard it. We know we can do this because there is at least one element in the other array (the one at index $\frac{k}{2}$) which is bigger than all of them, which means that these elements are within at most the $\frac{k}{2} + (\frac{k}{2} - 1) = k-1$ smallest elements, and therefore none of them can be the nth smallest element. Similarly, we can discard the right part (indices $\frac{k}{2}$ to $m$ or $n$) of the array where the element at index $\frac{k}{2}$ is bigger (since there were $\frac{k}{2}$ elements smaller than the right side in both of the arrays, there is a total of at least $k$ smaller elements, which means that the kth smallest element is not in there). Now we have two smaller arrays left, and we do the same for $\frac{k}{4}$, and then continue until $\frac{k}{2^{log_2k}}$.

Analysis: Since we shave off half of the remaining elements on each iteration, the efficiency of this algorithm will be $O(log(k))$.

## Problem 4
You are given $n$ nonvertical lines in the plane: line $L_{i}$ is described by the equation $y=L_{i}(x)=m_{i}x+b_{i}$, and you are given the slope $m_{i}$ and $y$-intercept $b_{i}$. Assume that no three lines intersect at a point.

We say that line $L_{i}$ is uppermost at some $x$-coordinate $x_{0}$ if its $y$-value is greater than the $y$-value of all other lines at $x_{0}$; that is, $L_{i}$ is uppermost at $x_{0}$ if $L_{i}(x_{0}) \geq L_{j}(𝑥_{0})$ for all $j$. We say that line $L_{i}$ is visible if it is uppermost at some $x$ coordinate.

(In other words: imagine you are standing at $y=\infty$ and are "looking down" at all the lines; you can see the visible ones, while the others are hidden by other lines closer to you.)

Describe and analyze an efficient algorithm to determine which lines are visible.

### Solution:

For the positive side --- We sort the lines based on their $m$ values. We then find the line with the highest $b$. At $x=0$, this is the line that will be visible. We set this line's gradient as the current gradient, $m_{cur}$. We then look through the sorted list of $m$ values for lines with $m$ > $m_{cur}$. We then calculate the intersection of those lines with the current line. We choose the line with the earliest intersection to be the current line at their intersection point, $x_{1}$. Thus, from $x=0$ to $x=x_{1}$, the line with the greatest $b$ will be visible so we save this in a separate array. We then set $m_{cur}$ to be the $m$ of the new line after the intersection point, set this to the current visible line, and we repeat this procedure to find a line with $m > m_{cur}$. For the negative side, we repeat this procedure but we look at $m < m_{cur}$. The runtime of this algorithm will be $O(n^2)$ at the worst case, where every line besides the one with the highest $b$ has an $m$ greater than it, and $O(nlog(n))$ in the best case.