CS 306 Quiz 3

CS 306, Computer Algorithms II

Quiz 3, 8 November 2007

Fail early is a useful heuristic for exhaustive-search algorithms. Fail early arranges the data for the algorithm so that failures occur earlier in the search rather than later. The idea is to keep the exhaustive-search algorithm from spending a lot of time on solutions that will eventually be rejected.
Explain how to apply the fail-early heuristic to an exhaustive-search algorithm for the seating-arrangement programming assignment.
Arrange the guests in increasing order of interests and friends. The list starts off with the guests having the fewest interests and friends, which makes them the hardest guests to seat.
Mergesort repeatedly splits array segments into two parts as it sorts. Explain the effects on mergesort's asymptotic estimate if instead it splits each array segment into three parts.
Splitting segments into to more pieces raises the logarithm base, which has the effect of flattening out quicksort's performance curve. As a practical matter, the change has no effect on mergesort's asymptotic estimate.
Is the following implementation of binary search correct?
```
int find(a, l, r, x)

  // Return the index i in the array segment a[l..r] at which a[i] = x or -1
  // if there's no such index.

  if l == r
    if a[l] == x 
      return l 
    else
      return -1

  m = (l + r)/2
  if x ≤ a[m]
    return find(a, l, m, x)
  else
    return find(a, m, r, x)
```
If it is, present a correctness argument; if it isn't, explain why. Assume division is standard integer division, which rounds toward 0 and that arrays are indexed starting from 0.
It isn't correct. If a[m] is the only array element equal to x, the algorithm won't find it. For example
```
find([3, 4], 0, 1, 4)
```
returns 0.
N customers are lined up at a check-out stand that can check-out one customer at a time. It takes t_i minutes to check out customer i. Describe an algorithm that arranges the n customers in line such that the average waiting time for all customers is minimized. Your algorithm should be efficient (that is, it should be tractable). Give an argument that your algorithm works.
Customer c's waiting time is the sum of the check-out times for the customers preceding customer c in line:
w_c = sum(i = 0 to c - 1, t_i)
The average wait time for all customers is the sum of each customer's wait time divided by the number of customers:
sum(i = 0 to n - 1, w_i)/n
Because t₀ appears n times in the average wait time, it should be the smallest wait time. If some other wait time t_j were strictly less than t₀, the average wait time could be reduced (by (t₀ - t_j)/n) by swapping t₀ and t_j. Any arrangement of customers in line that produces the smallest average wait time will have t₀, or a customer wait time equivalent to t₀ first.
Once t₀ is squared away, similar arguments can be made for t₁, t₂, and so on. This means the smallest average wait time occurs when the customers are ordered by increasing wait time, which can be done by a greedy algorithm (in the form of a ascending sort).