# Topic 3 Exercises
## Problem 1
To efficiently combine these sorted lists, it is best to break down the problem into smaller problems by combining only two sorted lists at the same time. This way there is only one comparison of elements at one time which is constant, instead of comparing k elements across k lists. So first take the k lists and combine two of them at a time so that you have k/2 lists of length 2n. Can do this by looking at the first element in both lists, adding the smaller element to the merged list, and removing that element from that list and repeating this until all 2n elements are in the merged list. This step is 2n comparisons for k/2 merged lists so we have O(nk) work. The next step is to repeat this process by merging the k/2 lists into k/4 lists of length 4n. By the same method there are 4n comparisons for k/4 lists, which is again O(kn). This method is then repeated until there are k/k = 1 lists of length nk, which clearly takes log k steps. Therefore we have O(nk) log k times, giving this algorithm the running time O(nk log k).

## Problem 2

To solve this problem, we will use partitioning to sort both the nuts and bolts by size so then each nut and bolt matches. First, take a bolt, and partition all the nuts smaller than it into one subset and the nuts larger into another, with the match at index i. Then, take the nut that matched and partition all the bolts smaller into one sub collection and all the bolts larger into another. Now, take a bolt from the smaller collection and test it with all the nuts in the smaller collection, once again partitioning those smaller to one collection and those larger into another collection. Take the nut that matches and apply the paritioning scheme to the smaller bolt colection. Do the same things with the larger nut and bolt collections. Continue on in this manner, partitioning smaller and smaller subcollections until each collection is just one and has found its match. Now all the matches are found and both collections are sorted given their size.

This algorithm works because each time the collections are split it by size, continually sorting both sets into smaller and smaller groups ending up with perfectly sorted sets.

Runtime: The number of bolt tests preformed will be $O(n log(n))$ since the groups are constantly split up into halves leaving $log(n)$ partitioning steps. Then at each step, checking each nut and bolt is done in linear $O(n)$ time.

## Problem 3
An efficient way of approaching this problem is doing a sort of binary search between the two lists. Can do this by first considering the first k/2 elements in the m length list and in the n length list and seeing if those are the k smallest elements. This would be the case if the largest element we considered in the m length list is smaller than the smallest element not considered in the n length list AND if the largest element we considered in the n length is smaller than the smallest element not considered in the m length list. If this is the case, then we would return the larger of the two largest elements considered in the m and n length lists and be done. If this is not the case, we would want to consider different elements from each list and re-test for the above cases. These are the cases that give the elements we should consider in each list:
* If the largest element in the m length list is larger than the smallest element not considered in the n length list $\Rightarrow$ Consider the first k/4 elements in the m length list and the first 3k/4 elements in the n length list and re-test
* If the largest element in the n length list is larger than the smallest element not considered in the m length list $\Rightarrow$ Consider the first k/4 elements in the n length list and the first 3k/4 elements in the m length list and re-test(vice versa of case above)
* Do either one of the operations above if both are the case

If the tests are not satisfied after considering the different elements above, then we will perform the same operations again, but instead of moving the considered indices by k/2 in either direction (so that we are still considering just k elements), we will move by k/4, then k/8, k/16, etc. until the tests are satisfied. Again, once they are satisfied, we will return the larger of the two elements that are the largest considered in each list. Clearly, we cannot continue this process for more than O(log k) steps, (since then the indices we are considering won't be moving anymore). Since at each of these steps we are doing a constant number of comparisons, we can give this algorithm a runtime of O(log k).

## Problem 4
This algorithm can be completed in the O(n log n) time. First, merge sort the n lines by increasing slope (which is the part that takes O(n log n) time). Then loop through the sorted list once, comparing three adjacent lines every time. Starting at the beginning of the list, the first line is clearly visible because it has the "least" slope. Then find the x-value of its intersection with the third line. If the y-value of the second line is not greater than the y-value of the intersection, then that second line is not visible, and can be removed from the list. If the y-value is greater, then it is possibly visible, and should be kept in the list. This process is then repeated for every line in between the first and last lines in the list (the two of which are visible). Once all the way through the list, return the list. This single loop through the list has constant work at each step so it gives O(n) time. Thus, the O(n log n) term dominates and that is this algorithm's running time.