Due 1:00 PM, Wednesday, 04 April 2018

CPSC 101b  Homework #7  Algorithms

REMINDER:  When discussing an assignment with other students, you may write on
a board or a piece of paper, but you may not retain any written or electronic
record of the discussion.  Moreover, you must engage in a full hour of mind-
numbing activity (e.g., watching back-to-back episodes of Gilligan's Island)
before you work on the assignment again.  This ensures that you can reconstruct
what you learned from the discussion, by yourself, using your own brain.  The
same rule applies to nonstudents and on-line sources.


1. Consider the following table of the distances between six pairs of cities in
   the Netherlands:

     .              A       B       C       D       E       F
     A(rnhem)       -      184     222     177     216     231
     B(reada)      184      -       45     123     128     200
     C(ulemborg)   222      45      -      129     121     203
     D(elft)       177     123     129      -       46      84
     E(indhoven)   216     128     121      46      -       83
     F(lushing)    231     200     203      84      83      -

     Note: Any resemblance to reality is purely coincidental.

   a. (1 point) Use the greedy algorithm to find a minimum spanning tree for
      this collection of cities.  What is the cost of this tree?

   b. (6 points) Starting from each of the six cities, use the greedy algorithm
      to find a tour of the six cities and give the length of that tour.


2. A customer of Wells Fargo Bank may make multiple withdrawals each day, but
   the bank determines the order in which they are posted to her account.

   a. (3 points) If the customer has overdraft protection, a fee of $39 is
   deducted from the account whenever a withdrawal reduces the balance below
   $0.  Describe a bank-friendly greedy algorithm to order the daily
   withdrawals so as to maximize the number of overdraft fees charged.  (Wells
   Fargo was sued for using such an algorithm.) Explain why your algorithm is
   greedy.  Do you think there is a better algorithm (i.e., one that could
   yield a larger number of overdrafts)?

   b. (3 points) If the customer declines overdraft protection, requests to
   withdraw funds are rejected when they would reduce the balance below $0.
   Describe a greedy algorithm for deciding which withdrawals to accept so as
   to maximize the amount withdrawn.  Explain why your algorithm is greedy.  Do
   you think there is a better algorithm (i.e., one that could yield a lower
   balance)?


3. (5 points) You and some friends are starting a company and have identified
   a set of tasks that you need to complete before you can open for business.
   The tasks can be performed in any order.  Moreover, you are equally talented
   and thus would all take the same amount of time to finish a given task.
   However, each task is inherently sequential, so that putting two or more
   of you to work on it would make it take longer (since you would have to
   coordinate your efforts); but they can be done concurrently by different
   people.

   Give a greedy algorithm for assigning tasks to N people.  Assume that the
   times for one person to complete the tasks are t(1), t(2), ..., t(N).  What
   assignments does your algorithm generate for each of the following problems:

   a) N = 5;  t(*) = {11  11,  4,  5,  6,  4, 12,  7}
   b) N = 4;  t(*) = { 5,  6,  8, 14,  5,  8,  9,  7}
   c) N = 4;  t(*) = { 9,  6, 10, 10,  6,  7,  9,  6,  8}
   d) N = 3;  t(*) = { 6, 13, 15,  6, 15,  7, 18, 10}

   In each case give the time at which all tasks are complete.  Explain why
   your algorithm is greedy.


4. (5 points) Give a divide-and-conquer algorithm to find both the smallest and
   the second smallest of N numbers x(1), x(2), ..., x(N).  Explain why your
   algorithm works as well as how.  You must explicitly identify the divide
   step, the subproblems that must be solved (which must be of this same form),
   the base case(s), and the conquer step.


5. (4 points) Suppose that you want to rank the 8 players on a tennis team from
   strongest to weakest.  As usual, assume that for any players A, B, and C:
   - if player A beats player B once, then player A can always beat player B;
   - if player A beats player B, and player B beats player C, then player A
       could beat player C if they played.
   Give a divide-and-conquer algorithm whereby you can rank the players in at
   most 20 matches.  You must explicitly identify the divide step, the
   subproblems that must be solved (which must be of this same form), the base
   case(s), and the conquer step.


6. (1 point) How many hours did it take you complete the first five problems?

Optional Supplementary Reading from Algorithms Unplugged (see class web page
  for free download from within the yale.edu domain):
    Chapter 33 (minimum spanning trees)
    Chapter 40 (travelling salesman problem)
    Chapter 38 (bin packing)
    Chapter 3  (mergeSort and quickSort)

							     CPSC-101b-03/28/18