Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/Discuss this assignment. /Solutions are available.

# 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:

{{{FrustrationSort(A):

• i = 1

while i < length(A):

• if A[i] > A[i+1]:

• swap A[i] and A[i+1] i = 1
else
• i = i+1

}}}

1. Prove the best upper bound you can on the asymptotic worst-case running time of frustration sort. (Hint: Count inversions.)
2. 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.

2014-06-17 11:58