CS 60, Assignment 12

Computer Science 60
Principles of Computer Science
Fall 2011

Assignment 12: Computability and complexity [150 Points]
Due Friday, December 9 at 5:00pm

This week's homework is a combination of several ideas we've been examining in the computability and complexity portion of CS 60. There are a couple of uncomputability proofs, some algorithms analysis, and a programming review (in Java and Racket) that includes both the use-it-or-lose-it technique and dynamic programming, an approach that speeds up such implementations -- sometimes remarkably so!

A note about partners: This week problem 1 should be done individually, though as always you can discuss your general approach with anyone else, especially the grutors and profs. For problem 2 you should again feel free to discuss your approach, but you must write up both proofs individually. Problem 3 may be done individually or with a partner (and you would only need to submit one version between the two of you).

Problem 1: (Un)computing at Nanosoft

30 points; to be done individually

You have been hired by Nanosoft. Your boss, Gill Bates, drops by your spacious cubicle sipping a refreshing and stimulating Jolt Cola ("All the sugar, and twice the caffeine!").

Gill begins by reminding you that a decider is a program that takes an input and eventually halts and accepts (says "True" to its inputs) or rejects (says "False" to its input). For example, a decider for the prime numbers would take a number, perhaps encoded in binary, as input and would eventually halt saying True (it's prime) or False (it's not prime). For the purposes of this problem, the terms "program," "function," and "turing machine" are used interchangeably.

"OK, so here's your first task," says Gill. "We have decided to change our interview process -- we're going to ask all of our job candidates to see if they can write a decider which takes as input a string of 0's and determines whether the number of 0's present is a power of 2."

You sigh, realizing that this would have made for a much less stressful interview than you had had, what with the complete rewrite of the company's recent operating system you'd been asked to build... .

"Here's what I need from you," continues Gill. "I need a program which we'll call a Power of Two Decider Tester (POTDT) in order to evaluate our interviewees' solutions. The POTDT takes as input a program. The POTDT then decides whether P is a legitimate decider for strings whose length is a power of 2. That is, the POTDT eventually halts and says True if the program it received was a correct power-of-two-decider; otherwise the POTDT halts and says False. I need this POTDT program written by tomorrow at 6 AM."

Prove to Gill that this cannot be done, not by 6 AM and not EVER! That is, prove that the POTDT is uncomputable.

As a guide to writing up uncomputability proofs, Here is a link to example write-ups of the proofs we did in class, that the functions "zinph", "ainph", and "autograde" are uncomputable.

Note that you can call a previously-created program in your proof simply by saying "we then run the Turing Machine from hw11pr9..." (this will help!)

"Drat!" says Gill upon hearing the news. "OK, then, in that case, I'd like you to write a program called a Regularity Checker (RC). The Regularity Checker takes as input a one-input function g (e.g., a Python function or Turing Machine) and the regularity checker needs to determine whether or not the set of strings accepted by g is a regular language. The RC must always halt with an answer of True (g accepts a regular language) or False (g does not accept a regular language)." Prove to Gill that this too is impossible.

Note that if a function/program/turing machine runs forever on an input, that input is considered REJECTED for the purposes of defining the language that the function accepts.

Hint: Often, the exact same construction works for both this and the previous problem, though the reason that it works is a bit different in each case.

Note: the idea in both of these problems is similar to the examples we did in which we reached a contradiction by creating a halt-checker out of the program that we hope to prove uncomputable. In this case, you'll want to create a halt-checker from a POTDT and a RC. Keep in mind that you can build any function/program/machine you like in order to coax the POTDT and RC into deciding whether a function f halts on an input inp.

For this reason, simply citing Rice's theorem isn't allowed for this problem!
Submitting these proofs Submit both of your proofs in a plain-text file named part1.txt.

Part 2: Big-O running times...

30 points; to be done individually

For these questions, you will be analyzing the running time of algorithms. We will be interested in worst-case analysis. (The best case is often uninteresting and the average case can be quite difficult to quantify.) You will need to express the worst-case running time using big-O notation. Be sure to show all of your reasoning in each written problem.

Submitting these answers Include your answers to these problems in a plain-text part2.txt file.

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
Consider a directed graph represented as a prolog list of edges, with each edge a [source, destination] pair. For example, G = [ [a,b], [b,a] ] is a two-node graph, with each node connected to the other.

The reachability problem asks whether it is possible to get from one node to another particular node within a given graph. The following is one possible prolog solution, named reach to this reachability problem:

reach(A,A,_). % any node is reachable from itself % below we ask you to explain what this next line is "saying" reach(A,B,[[X,Y] | R]) :- reach(A,B,R) ; (reach(A,X,R), reach(Y,B,R)). For example, here are two representative runs: ?- reach( b, a, [[a,b],[b,c],[c,d],[d,e],[e,f],[f,g],[g,a]]). Yes ?- reach( b, h, [[a,b],[b,c],[c,d],[d,e],[e,f],[f,g],[g,a]]). No Note that we are not concerned with generating any variable/value bindings here, we are only concerned with checking reachability for a fully-bound set of inputs.

Briefly explain in English what the second reach rule is "saying". Then, write a recurrence relation for T(n), the running time of the above reach function in terms of n, the number of edges in the graph G. Then, use the recurrence-unwinding strategy to "unroll" this recurrence relation in order to find a big-O running time of this version of reachability. Count each logical operation ; (or) and , (and) as one step. Show all of your work!

Part 3: Dynamic programming and memoization...

90 points; may be done in a pair or individually

Part 1: Change, Inc.

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. 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.

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 (for now). Your first task, therefore, is to quickly test the viability of a purely recursive approach. To that end, write a Racket function called change that takes two inputs: A list of coins/bills in the currency system (always from smallest to largest) followed by the amount of change to be made. The function simply returns the least number of coins required (but not the actual set of coins to disburse).

Approach: Here, you should employ the use-it-or-lose-it technique! That is, handle the base cases first. Then, consider the results of using (recursively) each of the possible coins in the list... you'll want the minimum of all of these!

Here are two sample inputs and outputs - note that the result depends on the "currency system" being used:

Racket> (change '(1 5 10 25 50) 42)
5
Racket> (change '(1 5 21 35) 42)
2

Note: Recall that Racket has built-in value called +inf.0 that is larger than any integer. In addition, in order to convert from floating-point (inexact) values to integer (exact) values, Racket has a built-in function inexact->exact, e.g.,

Racket> (inexact->exact 42.0)
42

Submit your code in a file named change.rkt.

Part 2: More Change

After the run-time results from the all-recursive change-counter, Dr. Lai has been replaced by the brilliant Dr. Dee Nomination. Dr. D, as she's called, suggests that dynamic programming is likely to solve the problem. Your next task, therefore, is to re-implement the recursive algorithm that you developed in Part 1 using dynamic programming. This time, you should use Java now rather than Racket: Java's arrays will be useful for this re-implementation.

Your program should be called change.java. When run, it will 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 lines will contain the values of Each coin/bill in that system, from 1 upwards. Here is an example of currency amounts (admittedly fictional, but computationally interesting) -- save these lines into a plain-text file named ex1.txt:

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

Feel free to create other currency-amount files, too... . In all cases, you may assume that there will be a "penny" and that they will be in sorted order.

A place to start for file-handling?! Feel free to adapt the code below to start your program - please use this class name, change, to help the graders! You'll see examples of how to use Scanner and nextInt -- they are are pretty much all you'll need here, along with a loop of some sort...

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;

class change
{
  public static void main( String[] args )
  {
    // get keyboard input Object
    Scanner kbd = new Scanner(System.in);
    // get input from keyboard
    System.out.print( "Enter a filename: " );
    String filename = kbd.nextLine();
    // trim off any whitespace
    filename = filename.trim();
    System.out.println("Now trying to open " + filename);
    
    // get file input Object via the file:
    Scanner file = null;
    try { // in case the file's not there
      file = new Scanner(new File(filename));
    } catch (FileNotFoundException e) {
      System.out.println("File " + filename + " not found.");
      System.out.println( e );
    }
    // get integer at the start of the file:
    int num_coins = file.nextInt();
    System.out.println("Read the # of coins = " + num_coins);
    
    // create an array, coins, to hold the coins:
    int[] coins = new int[num_coins];
    
    // here, you'll need to loop in order to read each coin in...
    
    // It's useful for debugging to be able to print an array 
    System.out.println("The array, coins, is " + Arrays.toString( coins ));
    
    // It's also useful to be able to get more input from the keyboard:
    System.out.println("Input an integer and I'll add 1: ");
    int amt = kbd.nextInt(); // it will crash if it's not an int!
    System.out.println("You entered " + amt + ", one less than " + (amt+1));
  }
}

Approach You should take a "bottom-up," dynamic programming approach to solving this instance of the change problem. That is, you should solve the problem for each (integer) amount of change starting at 0 and increasing by 1 up to the user's desired amount. You should keep a table (an array) of these subproblems -- along with an array of the "last coin needed," as we discussed in class on Monday. This approach is much faster, O(N) instead of exponential, than the pure-recursion based approach suggested in Racket, above.

Here is some sample input and output, indicating should happen when you run your program. Note that you may print the coins to be given in any order, not necessarily largest denomination first.

Note As the two examples below indicate, in addition to solving the problem by finding the fewest coins, you should also print out the dynamic programming table and the "last coin needed" table, as discussed in class on Monday.

> java change
Enter a filename:  [[user types]] ex1.txt
Now trying to open ex1.txt
Read the number of coins = 6
How much change would you like?  [[user types]] 22
OK, searching for change for 22
Minimum # of coins = 2
The coins are 10 12 

The DP table was
[0, 1, 2, 3, 4, 1, 2, 3, 4, 1, 1, 2, 1, 2, 2, 2, 3, 2, 2, 2, 1, 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, 9, 20, 1, 10]



> java change
Enter a filename:  [[user types]] ex1.txt
Now trying to open ex1.txt
Read the number of coins = 6
How much change would you like?  [[user types]] 21
OK, searching for change for 21
Minimum # of coins = 2
The coins are 1 20 

The DP table was
[0, 1, 2, 3, 4, 1, 2, 3, 4, 1, 1, 2, 1, 2, 2, 2, 3, 2, 2, 2, 1, 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, 9, 20, 1]

Test your program on some fairly large amounts of change (up to about 1000) in at least two different currency systems. If this version is not a HUGELY dramatic improvement -- in terms of how fast it computes -- over your recursive solution from the Racket solution, check your code again!

Submit your program in change.java.

Part 3: The Floyd-Warshall Algorithm!

You've been hired away from Change, Inc. to work for Google and their newest stealth-mode version of their mapping service, which "completely reverses" the online mapping experience, called GoogleSpam. 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 all-pairs-shortest-paths algorithm. It reads in a graph from a file and then allow a user to make a query against that graph. (Admittedly, a more complete version might allow more queries, but once you know the shortest path to spam, what more is there to ask?)

Try it first... A .class file is provided in the fw.zip folder. To run the example fw class from the command line, you should be able to use the command java fw from that directory. To run it from Dr. Java, these steps have worked for us:

Open the map0.txt file in Dr. Java -- to see it you will need to choose All files from the file-types dropdown menu. This map0.txt file isn't really needed, but doing this puts Dr. Java in the right directory. Also, it's a good idea to remind you of this small graph's structure. The -1 values in the file represent "no path" or, equivalently, "infinite distance."
Next, click on the "Interactions Pane" at the bottom of Dr. Java
At the > shell prompt, type java fw, which should start the program.
The program should prompt you for a filename: type map0.txt .
The program will print out the four "layers" of the Floyd-Warshall algorithm's dynamic programming table. It will also print out the previous vertex table. (All of these "tables" are 2d arrays.) You can compare your code's results to these as part of development... .
Then, the program will ask for a source and destination vertex as a shortest-path query. As a first trial, type 3 as the source vertex and 2 as the destination vertex. You should see the program print that the minimum path length in this case is 2 and that the path traversed is 3 --> 1 --> 2. The full output is below.

You can print a 2d array with the following function (actually, this converts it to a String, but then you can print it):

  public static String toStr( int[][] A, int n ) {
     String s = "";
     for (int row=0 ; row<n ; ++row) {
       s += Arrays.toString(A[row]) + "\n";
     }
     return s;

Even if you create a 3d array, such as this: int[][][] fw = new int[numcities+1][numcities][numcities]; it's better to print slices of them, e.g., toStr(fw[0]), toStr(fw[1]), and so on... .
That's it! You might want to run it again using map1.txt or map2.txt, which are larger graphs that will test the FW algorithm more thoroughly.

Here is the output of the run described above:

> java fw
Enter a filename:  [[user input]] map0.txt
Now trying to open map0.txt
Read the number of cities = 3

The FW tables:

fw[0] is 
[0, 1, -1]
[-1, 0, 1]
[1, -1, 0]

fw[1] is 
[0, 1, -1]
[-1, 0, 1]
[1, 2, 0]

fw[2] is 
[0, 1, 2]
[-1, 0, 1]
[1, 2, 0]

fw[3] is 
[0, 1, 2]
[2, 0, 1]
[1, 2, 0]

The "previous vertices":

pv is 
[0, 0, 1]
[2, 1, 1]
[2, 0, 2]

From what city (1-3)?  [[user types]] 3
  To what city (1-3)?  [[user types]] 2
From city # 3
  to city# 2
  the minimum cost is 2

And the path is
 3 --> 1 --> 2

Warning When querying for a shortest path, this program -- and your program -- should count vertices starting from 1, instead of the traditional start from 0. Indexing from 1 is helpful in this case, because it means you can use the 0 index for other purposes, such as the original graph's adjacency matrix. But be sure to make the arrays you use large enough!

Details on the implementation In a class named fw you should implement the Floyd-Warshall Algorithm for finding the shortest path between every pair of vertices in a graph. Your program should be written in Java. Here are the requirements for your program:

Your filename should be called fw.java, and its class should be named fw. Thus, the compiled program will be invoked by typing java fw.
The program should work as in the example above, i.e., it should begin by asking the user for the name of a file that contains an adjacency matrix representation of a graph. In particular, the file will always be in the following format:
3 0 1 -1 -1 0 1 1 -1 0 Here, the first line of the file contains a positive integer, n, indicating the number of vertices in the graph. This is followed by n lines of data, each of which contains n integers. The integer in row src and (column) position dst indicates the length of the edge from vertex src to vertex dst in the graph. If there is no edge from vertex src to vertex dst then the length of this edge is "infinity" which is represented by the value -1. Note, too, that the length of the edge from vertex src to dst may be different from the length of the edge from vertex dst to src, due to traffic, magic, or other unusual road conditions.
Since different OSes use different combinations of characaters to indicate newlines, we've pasted the contents of all three map files at the bottom of this page. If our provided files don't work on your system, feel free to copy-and-paste the text from below into a new file (using Dr. Java or another text editor).
As a starting point for file-handling, you may want to extend the file-handling example in the change-making problem, above. (We simply renamed change to fw and altered the code from there... .)
Your program should work like the sample program. In particular, it should print out the intermediate arrays of shortest path lengths that it finds as a result of running the Floyd-Warshall algorithm. It should also print the 2d array of "previous vertex" values, in which each entry, PV[src][dst], holds the final intermediate vertex along the shortest path from src to dst, i.e., the last one before dst. If there is a direct path from src to dst, then this PV[src][dst] value should contain the value of src. If there is no path from src to dst, then this PV[src][dst] value should be -1.
Finally, the program should query the user for a source/destination pair and then print out the minimum path length from that source src to destination dst, followed by the path needed to get from src to dst in that shortest distance.

Here are a few tips:

At first, implement the program just to compute the lengths of the shortest paths between all vertices, not worrying about reconstructing (printing) the actual paths. Once you've got the program computing the matrix of shortest paths -- and it matches the matrices printed by the example program, you can go back and modify the program to print out the actual shortest paths. (More on reconstructing the shortest paths below.)
As you'll recall from our discussion of the Floyd-Warshall algorithm, vertices should be numbered from 1 upwards rather than from 0. Here's why. The algorithm builds a series of tables of path lengths from every src to every dst. The kth table represents, "the shortest path-length from all src vertices to all dst vertices going through no intermediate vertex numbered higher than k. By starting at 1, the zeroth table then goes through no intermediate vertices at all, which means it's simply the original graph. By starting vertex-counting at 1, we avoid having to have a special case for the original graph.
How will we reconstruct and print the actual shortest paths when the user makes a query? In order to do this, you will want to keep a second table (named PV above, short for "previous vertex"), which holds in PV[src][dst] the intermediate vertex immediately before dst when traversing the shortest path from src to dst. This entry could start as src for all entries (src,dst) for which there is a valid direct edge, and it could start at -1 for those cells that do not have a direct edge. Then, the entries of this table could be updated appropriately as the Floyd-Warshall algorithm progresses!
Once the algorithm finishes and you need a path from src to dst, you can use this table to get the vertex immediately before dst on that path. Then, you can use the table again to get the vertex immediately before that one - and so on!

Please submit your solution in a file called fw.java.

Extra credit?

There is also an extra-credit assignment, worth up to +50 points, available on Wed. 12/7, and due anytime before Saturday, Dec. 17. It is linked under "Assignment 13."

The maps

In case it's useful to copy-and-paste the maps (the different newline characters sometimes cause problems), feel free to do so from these printouts:

map0.txt

map1.txt

30
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
-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
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
-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
-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
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 
-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 
-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 -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 -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 
-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 
-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 
-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 
-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 -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 
-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 -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 
-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 -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 
-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 
-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 -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 -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 -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 -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 -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 -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 -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 -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 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0

map2.txt

30
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
-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
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
-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
-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
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 
-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 
-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 -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 -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 
-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 
-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 
-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 
-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 -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 
-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 -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 
-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 -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 
-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 
-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 -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 -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 -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 -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 -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 -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 -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 -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 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0

Computer Science 60 Principles of Computer Science Fall 2011

Assignment 12: Computability and complexity [150 Points] Due Friday, December 9 at 5:00pm