Assignment 11: DP and big-O    [100 Points]
Due Monday, December 10 at 11:59pm

Problem 1: Change, Inc.

30 points

You have been hired by Change, Inc., a pioneer in the business of making change. Our motto is "Making positive change throughout the world!". Strictly speaking, the change is only "non-negative" since 0 change is possible, but this was a nuance that the PR folks chose to ignore.

Your job is to write software Change, Inc. that will make change in any given currency system using the smallest number of coins/bills. The currency system might have very odd denominations - for example, Gringotts, a potential customer, uses currency whose values are 1, 29, and 493 knuts, respectively - so the software should not impose limits on what denominations it can handle. This software will be embedded in cash registers and used to inform tellers how to make change optimally - or will simply automate the dispensing of change via robotic change-makers.

You may assume that you have "unlimited" quantities of each coin/bill, and that you may use any combination - including repeats - in making change for a given quantity. Also, you may assume that 1 is always present in the list of denominations -- this ensures that it's always possible to make change for any (nonnegative) target!

Your boss, Professor I. Lai, believes that a simple recursive algorithm for this problem will be fast enough for use in the company's cash registers. Although you are skeptical, Prof. Lai is the boss - at least for the moment.

Thus, first task, therefore, is to test the viability of a purely recursive approach. To that end, Dr. Lai has requested both a Prolog predicate and a Racket function that find the shortest-length list of "coins" that sum to a provided target value.

In the end, you'll create three implementations, one in each of Racket, Prolog, and Java. The first two will use recursion (and will remind you about those languages, we hope!) The Java implementation will use dynamic programming -- and run much more efficiently!

• Racket:  

  In the change.rkt file, you should write a function named min-change that takes two inputs: first, a target value for which to make change and, second, a list of coins/bill denominations in the currency system listed from smallest to largest. The function should return the shortest-length list of coins (really denominations) required to make change for the target value. If there are more than one shortest-length lists, any one of them is OK.

  Because this is using recursion, you can assume that no target will ever be greater than 42 -- the nice thing about this is that you can return a list of 42 1s in order to indicate a "bad" result (one that's no worse than any valid result). This will help for some of the base cases.

  Approach: Here, you should employ the use-it-or-lose-it technique!

  Here are two sample inputs and outputs - note that the result depends on the "currency system" being used. Also, the order in which the coins are listed in the end result does not matter -- any reordering would be OK here:

  Racket> (min-change 42 '(1 5 10 25 50))
  (1 1 5 10 25)
  
  
  Racket> (min-change 42 '(1 5 21 35))
  (21 21)
  
  
  Racket> (min-change 1 '(1 5 21 35))
  (1)
  
  
  Racket> (min-change 0 '(1 5 21 35))
  ()
  

  
  
  

  Hints and Reminders:

  • In our solutions, we found it useful to create a helper function named (make-ones n) that returned a list of n 1s. Here's how it would run:

    (make-ones 7)
    (1 1 1 1 1 1 1)
    

  
  
  • The reason make-ones is useful is that (make-ones 42) can be the return value from any "invalid" min-change call, e.g., when the target is negative or there are no denominations at all! This works because we're limiting the target value to 42 or less.
  
  

  Submit this code in the file named change.rkt (within the overall archive)




• Prolog:  

  Worried that only one implementation will constrain his business, Dr. Lai wants to keep as many options open as possible -- in particular, he is pro-Prolog, and would like a Prolog predicate
  
  min_change( Target, Denoms, ResultingChange )
  
  that will bind a minimum-length result to the variable ResultingChange, given bindings to Target (a nonnegative integer) and Denoms, a list of the available denominations.

  Write a version of this min_change predicate in the file change.pl. Recall that You you will want to decompose this problem into arbitrary change-making and then will need some additional checks to ensure a result is one of minimum-length.

  Hints/reminders:
  

  • the input Target will be zero or positive - you will want to check this constraint each time, to stop Prolog from recursing with negative values of Target!
  
  
  • Because constraints like Target > 0 will ensure that Prolog never recurses with a negative value for Target, you won't need to have an artificially large list to bind for base cases, as had to be used in the Racket version.
  
  
  • a good place to start is to make a change predicate that computes all possible lists of values, taken from Denoms, that sum to Target. This simpler predicate would not impose that the result be the shortest such list. Since "creating all possibilities" is what Prolog does best, this is a reasonable first step.
  
  
  • once your change predicate works, then you could add other predicates that will help ensure that min_change only finds a shortest change list. This is similar to the midterm exam's "preferred path of destruction" question.
  
  
  • remember that is is used for arithmetic, not = (this would have saved an hour for our solution...)
  
  
  • five rules are all you'll need total:
    • three rules for the basic change-making (with no "shortest" constraint)
    • two rules to enforce the "shortest" constraint on top of that

  Run small tests!

  Prolog is even less efficient than Racket, so don't try to run tests that are too large. Here are some of the tests that ran in enough time for us - though the one with a target of 18 took about 5-10 seconds. It's also OK to have multiple answers of the same (minimum) length - even multiple identical answers, as Prolog likes to do:

  ?- min_change( 6, [1,5], MC ).
  MC = [1, 5] ;
  false.
  
  ?- min_change( 8, [1,5], MC ).
  MC = [1, 1, 1, 5] ;
  false.
  
  ?- min_change( 8, [1,3,5], MC ).
  MC = [3, 5] ;
  false.
  
  ?- min_change( 18, [1,5,9,10,12], MC ).
  MC = [9, 9] ;
  false.
  
  ?- min_change( 0, [1,5,42], MC ).
  MC = [] ;
  false.
  

  Submit this code within change.pl, again within the overall hw11.zip archive.




• Java:  

  After the run-time results emerge from these all-recursive min-change-counters, Dr. Lai is fired and replaced by the brilliant Dr. Dee Nomination. Dr. D, as she's called, suggests that dynamic programming is likely to solve the problem much more efficiently. Your next task, therefore, is to re-implement the recursive algorithm that you developed in the previous parts using dynamic programming. This time, you should use Java now rather than Racket: Java's arrays or ArrayLists - your choice - will be useful for this re-implementation.

  Your program should be called change.java. When run, it should ask the user for the name of a file with the currency system. That file will have the following format: The first line contains a single number, which is the number of coins and/or bills in the system. The next line will contain the values of each coin/bill in that system, from 1 upwards. 1 will always be included (this ensures that there is always an answer). Here is an example of currency amounts (admittedly fictional, but computationally interesting) -- these are in the plain-text file ch1.txt:

  6
  1 5 9 10 12 20
  

  Here, the first line is the number of currency-amounts to follow (6); then those currency amounts appear afterwards.

  Your program should print out a minimum-length list of denominations that sum up to the target value. The design of the internals of the program are up to you, with the knapsack and the miss examples to help provide pieces and/or ideas. Here is an example of some possible printouts for the coins1.txt input file. We include the debugging printout of our DP table and "last coin" table for the first run, in case it's helpful:

  > java change_sols
  Enter a filename:  coins1.txt
  Now trying to open coins1.txt
  Read the number of coins = 6
  
  How much change would you like?  18
  OK, searching for change for 18
  
  Minimum # of coins = 2
  The coins are 9 9 
  
  The DP table was
  [0, 1, 2, 3, 4, 1, 2, 3, 4, 1, 1, 2, 1, 2, 2, 2, 3, 2, 2]
  
  The "Last Coin" table was
  [0, 1, 1, 1, 1, 5, 1, 1, 1, 9, 10, 1, 12, 1, 5, 5, 1, 5, 9]
  
  
  
  
  
  > java change_sols
  Enter a filename:  coins1.txt
  Now trying to open coins1.txt
  Read the number of coins = 6
  
  How much change would you like? 42
  OK, searching for change for 42
  
  Minimum # of coins = 3
  The coins are 10 12 20 
  
  
  
  > java change_sols
  Enter a filename:  coins1.txt
  Now trying to open coins1.txt
  Read the number of coins = 6
  
  How much change would you like?  99
  OK, searching for change for 99
  
  Minimum # of coins = 6
  The coins are 9 10 20 20 20 20 
  

  Test your Java program on some fairly large amounts of change (up to about 1000) in at least two different currency systems. This version should be a HUGELY dramatic improvement -- in terms of how fast it computes -- over your recursive solutions in Racket and Prolog.

  Submit this program in change.java, again within hw11.zip

Part 2: The Floyd-Warshall all-pairs shortest-paths algorithm

You've been hired away from Change, Inc. to work for Google and their new stealth-mode version of their mapping service, named GoogleCpam, and which they claim will "completely reverse" the maps experience! GoogleSpam allows users to estimate the shortest distance among any pair of possible spam-locaitons (nodes) in a map (graph).

In particular, you've been asked to implement the main "smarts" of GoogleSpam, i.e., the Floyd-Warshall all-pairs-shortest-paths algorithm. It reads in a graph from a file as an adjacency matrix, computes the shortest paths between every pair of vertices, and then allow a user to make queries against those results.

map files In the hw11.zip archive, there are a number of different map files, named map0.txt, map1.txt, up to map4.txt. Each contains an adjacency matrix that indicates the edge weights from each node to each node. There are zeros in the top row and top column of each file because all of the cities are indexed from 1, not from 0. The extra zeros are padding so that you can read all of the data from the file directly into your data structure and still start indexing the cities/vertices from 1.

Note that, within the map files, no edge from one vertex to another is represented as -1. This is typically represented as some sort of "infinity" value, and the starter code has a data member INF for that purpose. INF is equal to Integer.Max_VALUE. Be careful, however, Java will allow to add or otherwise use INF as an int, and will simply wrap. Thus, INF + INF yields -2! (You'll need conditionals to make sure to avoid this.)

The cities are indexed from 1, not from 0!    Although 1-indexing is not the norm in computer science, it's very useful here, because it means that the 0-index slice of the Floyd-Warshall table can be the original adjacency matrix. Then the 1-index slice of the Floyd-Warshall table can hold all of the shortest paths using the first vertex (with index 1) as possible intermediate node. The 2-index slice of the FW table can then hold all of the shortest paths using also the next vertex (with index 2) as a possible intermediate node, and so on... . Notice that this means that the nth slice of the FW table will hold all of the shortest-path lengths when the algorithm is complete. Note, too, that you will have to make each dimension of size n+1, where n is the number of cities, in order to support indexing from 1 to n!

Here is a brief overview/picture of the included map files:

• map0.txt contains the following data:

  3
  0 0 0 0
  0 0 1 -1
  0 -1 0 1
  0 1 -1 0
  

  and is represented by the following picture:
  


• map1.txt contains the following data:

  4
  0 0 0 0 0
  0 0 4 2 -1
  0 -1 0 1 -1
  0 -1 -1 0 8
  0 16 -1 -1 0 
  

  and is represented by the following picture:
  


• map2.txt contains the following data:

  4
  0 0 0 0 0
  0 0 14 -1 -1
  0 -1 0 14 50
  0 -1 -1 0 14
  0 10 -1 -1 0 
  

  and is represented by the following picture:
  


• map3.txt contains the following data:

  30
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
  0 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  0 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  0 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  0 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  0 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  0 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1
  0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
  

  Although we don't have an image, this is a ring of 30 vertices, each attached to the next-highest number by an edge of weight 1, and with vertex 30 attached to vertex 1 also with an edge of weight 1.


• map4.txt contains another 30-vertex graph:

  30
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  0 0 12 -1 16 -1 -1 -1 -1 -1 -1 -1 100 -1 119 -1 -1 -1 -1 -1 -1 42 -1 -1 -1 -1 -1 51 -1 -1 -1
  0 -1 0 1 -1 -1 -1 -1 -1 -1 -1 99 -1 201 -1 -1 -1 -1 -1 -1 -1 41 -1 -1 -1 -1 -1 -1 16 -1 119
  0 51 -1 0 1 -1 9 -1 -1 25 -1 -1 76 -1 -1 -1 45 -1 -1 38 31 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  0 -1 -1 26 0 1 -1 26 -1 -1 -1 29 -1 -1 30 -1 87 -1 -1 -1 -1 -1 -1 -1 41 -1 -1 -1 -1 -1 -1
  0 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
  0 30 -1 17 -1 -1 0 1 -1 -1 42 -1 -1 42 -1 -1 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 31 -1 33 -1 -1 0 1 -1 -1 -1 -1 -1 -1 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 28 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 36 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 39 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 79 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 54 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 23 -1 -1 -1 -1 -1 34 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 52 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 19 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1
  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1
  0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
  

  It is also a ring like map3.txt, but with some "shortcuts" and "longcuts" scattered between various nodes.

starter file

Example results

• map0_results.txt
• map1_results.txt
• map2_results.txt
• map3_results.txt
• map4_results.txt

Warnings/Reminders

Submit your solution in the file called fw.java within the hw11.zip archive.

Part 3: Big-O running times...

30 points

For these questions, you will be analyzing the running time of algorithms. We will be interested in worst-case analysis. You will need to express the worst-case running time using big-O notation. In addition to your answers, be sure to show your reasoning for each of the problems in the hw11pr3.txt file (just as ASCII text).

Submitting these answers    Include your answers to these problems in the hw11pr3.txt file, which will be within the overall hw11.zip file you submit.

• What is the big-O running time of this portion of code, in terms of n? Explain your analysis clearly and carefully. (Notice how i is increasing!)

          for (int i=1 ; i≤n ; i *= 2)
             for (int j=0 ; j<i ; ++j)
                // constant time work here
          

• What is the big-O running time of this portion of code, in terms of n? Explain your analysis clearly and carefully. (Notice how j is increasing!)

          for (int i=1 ; i≤n ; ++i)
             for (int j=1 ; j<i ; j *= 2)
                // constant time work here
          

• Stooge Sort!
  
  Larry, Mo, and Curly have designed a new StoogeSort sorting algorithm that works as follows on an array of N elements:
  • If the input list has 0 or 1 elements, it's already sorted - just return it.
  • If it has 2 or more elements:
    • recursively use StoogeSort to sort the first N-1 elements, leaving the final element untouched at the back of the list
    • afterwards, recursively use StoogeSort to sort the last N-1 elements, leaving the first element untouched at the front of the list
    • finally, after both these steps, compare the first two elements of the resulting list. If they're out of order, swap them; if they're in order, don't do anything.
  Remarkably, StoogeSort actually sorts! But the stooges are not sure of its run-time.

  So, for this algorithm, write a recurrence relation that captures its running time in terms of the number of comparisons made. Then, "unwind it" in order to find the running time of this sorting algorithm:

            T(1) = 0      # no comparisons if the list is 1 element long (or 0)
            T(N) = something
          

  Use the "unwinding" technique we developed in class to determine the big-O running time for this function, in terms of the input size, N.

Extra credit possibilities

Floyd-Warshall paths

This assignment's first totally optional - but challenging! - extra credit is worth up to +10 points for an extension of the Floyd-Warshall algorithm so that you can print the shortest paths themselves, not only the lengths of the shortest paths in your implementation of that problem. You can simply include those paths -- as the example outputs show -- with the rest of your FW implementation.

Improved StoogeSort!

The second optional - but also challenging! - extra-credit problem worth up to +5 points is to write a recurrence relation and solve it for the Stooge's improved StoogeSort. Improved StoogeSort does the following:

• Same base cases as ordinary StoogeSort
• If the list has many elements,
  • recursively sort the first two-thirds (leaving the last third untouched in its place)
  • recursively sort the last two-thirds (leaving the new first third untouched in its place)
  • again recursively sort the first two-thirds (again, leaving the last third untouched in its place)

Place your answer in hw3pr11.txt along with the other part 3 solutions. (Note that if you find the result irrational, you may have gotten it!)