1. Frustration sort
The frustration sort algorithm starts at the beginning of an array, runs along it until it finds a pair of elements A[i] and A[i+1] that are out of order, swaps them, and then gives up and goes back to the beginning again. It terminates only if it makes it all the way through the array without finding an out-of-order pair. Below is pseudocode for frustration sort:
- i = 1
while i < length(A):
if A[i] > A[i+1]:
- swap A[i] and A[i+1] i = 1
- i = i+1
- Prove the best upper bound you can on the asymptotic worst-case running time of frustration sort. (Hint: Count inversions.)
- Prove the best lower bound you can on the asymptotic worst-case running time of frustration sort. (Hint: Find a bad case you can analyze easily.)
2. Triathlon routing
The Triathlon Package Delivery Service ("we have the sweatiest deliverymen") guarantees that its customers' packages will be delivered by swimming, followed by bicycling, followed by running. For planning deliveries, the Triathletes have a map of North America in the form of a directed graph, where each node represents some location and each edge represents a way to get from one location to another. The edges of the graph are labeled as swimmable, bikable, or runnable; a given edge may have any combination of these attributes (or may even be completely impassible). A permissible delivery route is a path through the graph consisting of zero or more swimmable edges, followed by zero or more bikable edges, followed by zero or more runnable edges.
The Triathletes would like you to devise an algorithm that computes for any given starting location the set of all locations that can be reached by a permissible delivery route. Give the best algorithm you can for this problem, and compute its worst-case asymptotic running time as a function of the number of vertices and edges in the graph.