# Topic 7 Exercises

## Greedy Algorithms

### #3

### #4
### #5
**Algorithm:**
- place one base station 4km from the left side of the road (the beginning)
- now all of the houses left of the station are guaranteed to be covered, and houses within 4km to the right are too
- repeat the process in a similar manner for the length of the road: place a station 4km right of the first uncovered house

**Explanation:**
- consider another optimal solution which places the bases at positions {p~opt1~,p~opt2~,...,p~opti~}, and our solution which places them at positions {p~1~,p~2~,...,p~i~}
- because the first base station is placed as far to the right as possible (while still making sure all houses left of it are covered), for the first base, the other solution's first base, p1, can do no better than our first base (ie. p~opt1~ <= p~1~).
- for each subsequent base, the same logic follows, proving that for any number of bases, our base positions are all at or before those of the other algorithm, so our algorithm covers at least as many houses in total.

### #6

## Dynamic Programming Algorithms

### #4
**Algorithm:**

At a high level, the algorithm will consider the quality of every successive suffix along with the recursively computed highest quality segmentation of the rest of the string. That is, consider a function $f(i)$ which returns the segmentation with the highest sum of quality scores in the first $i$ characters of $y$. The last segment has to end at $y$~i-1~ and could begin anywhere to the left all the way to $y$~0~. Call the beginning position of the final segment $j$. Hence, the algorithm will check the quality created by every segment starting with each $j$ combined with the quality of the segmentation produced recursively by $f(j-1)$ (the beginning of the string other than the final segment). Thus, in order to calculate the segmentation of $n$ characters, run $f(n+1)$ on the string. The algorithm will either need to store the qualities from all of the recursively created subsegments and the j values which created the optimum in memory or create a dependency table in order to retrieve these values as the recursion moves back up/segments start re-adding suffixes.

**Analysis:**

This algorithm will run in $O(n^2)$ time since for each succesive suffix, which there could be a max of $n$, it will have to check every possible $j$ value of which there are a max of $n$. The algorithm will have a $O(n)$ space complexity as a recursive stack is needed.