Assignment 12: Uncomputability and algorithm efficiency!

What to submit

In the first two parts of this assignment there is no programming - for those you should write up your answers (proofs or analyses) in a plain-text file and submit it as hw12.txt. The final part asks you to create a short program in each of Prolog, Java, and Scheme - those you should submit in files named hw12.pl, hw12.java, and hw12.scm.

The problems

(40 points - this may be done individually or in a pair)

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 "yes" to its inputs) or rejects (says "no" 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 "yes" (it's prime) or "no" (it's not prime).

• "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'd had, what with the complete rewrite of the company's recent operating system you'd had 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). 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 yes if the program it received was a correct submission for this competition and otherwise the POTDT halts and says no. 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! You may use diagrams to help explain your proof, but your proof must be clear, precise, and rigorous. Your submission on this and the following problem will be graded on clarity and precision of explanation.
  
  Here is a link to an example write-up of the proof we did in class, that the blank-tape halting problem is undecidable.
  
  
• "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 program P (e.g., a Turing Machine) and it needs to determine whether or not the set of strings accepted by P is a regular language. The RC must always halt with an answer of yes or no!" Prove to Gill that this too is impossible. Again, you may use pictures to help you explain your proof, but your proof must be clear, precise, and rigorous.
  
  Note that if a turing machine runs forever on an input, that input is considered REJECTED for the purposes of defining the language that the TM accepts. This might help!
  

Problem 2: Algorithm analysis

(20 points - may be done individually or in a pair)

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 is often quite difficult to quantify.) You will need to express the worst-case running time using big-O notation. Finally, make sure to show all of your work in each written problem. Explain your reasoning carefully.

Submitting these answers    Include your answers to these problems in your plain-text hw12.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: languages review...

(40 points - may be done individually or in a pair)

For this problem, you'll submit programs that solve the "best investing strategy problem" in each of the programming languages we have used this term: Prolog, Java, and Scheme. You may remember this problem from CS 5: here the goal is to review each of the languages we have used (not to challenge your algorithmic-design skills). However, see the extra-credit for an extension of this problem that might offer a greater algorithmic challenge - and other big-O fun, as well! We will also review these languages in the final week of CS 60 (with some additional algorithm-design challenges involved!)

The problem is one you may remember from CS 5: given a list of stock prices, one per day, find the maximum profit you can obtain with a single buy and a single sell transaction. If you could buy and sell on any of the days, then you could buy at the lowest price and sell at the highest one. Here, that is not permitted: you may only sell on a day that is on or after the day you buy. Because you can sell the same day that you buy, the smallest profit you might earn is 0.

As an example, consider the prices represented by this list:

[60, 100, 17, 33, 21, 20, 43, 59, 55, 18, 2]

60 100 17 33 21 20 43 59 55 18 2

In a comment in each of your files, state the big-O running time of your solution in terms of the number of prices N in the list. In a sentence or two, justify your running time claim - however, you do not have to create a recurrence relation or formally analyze your code.

Each of these programs should find the maximum profit possible for a list of prices - while respecting the constraint that the sell day is the same or later than the buy day. Here are some details for each of the three languages:

• Prolog    In a file named hw12.pl, create a predicate named maxProfit( PriceList, BestProfit ) that takes in a list PriceList of at least two prices and that binds BestProfit to the value of the maximum obtainable profit according to that list of prices. PriceList will always be bound - it does not have to be generated! (I found it helpful to write a couple of helper predicates - feel free to do this!) Be sure to comment all of your predicates - even maxProfit; place a header comment with your name, the filename, and the purpose (Hwk 12, problem 3) at the top of the file.



• Scheme    In a file named hw12.scm, create a function named (max-profit pricelist) that returns the maximum obtainable profit according to that list of prices, pricelist. You may assume that pricelist has at least two elements (though you may also create base cases that don't make that assumption). Here, too, I found helper functions useful - be sure to comment all of the functions you create and to put a header comment at the top of your file!



• Java    In a file named hw12.java, create a class named hw12 that has a main method which
  1. Prompts the user for the number of stock prices.
  2. Then takes in those prices and stores them in an array.
  Afterwards, the main method should compute the maximum obtainable profit - and the best buy day and sell day - and then print out all three of those pieces of information (you may break ties arbitrarily). Helper functions are welcome; you may use data members or you may simply use local variables to store data.
  
  For example, here is a possible format for a run of the program:

  > java hw12
  Enter the number of prices:  11
  Now, enter the prices: 60 100 17 33 21 20 43 59 55 18 2
  
  Your strategy:
  Buy on day 2 and sell on day 7 ...
   ... for a maximum profit of 42 !
    

  and here is some starting code for obtaining input from the command-line:

  import java.util.Scanner;
  
  class hw12
  {
    public static void main(String[] args)
    {
      Scanner s = new Scanner(System.in);
  
      System.out.print("Enter the number of prices: ");
      int num_prices = s.nextInt();
      
      int[] prices = new int[ num_prices ];
    }
  }
    

  Again, be sure your methods are commented and that the file also has a suitable header comment.

Extra Credit Options

• Speed!    +5 points of extra credit is available for a big-O(N) algorithm for the Java version of the maximum-profit problem, above... (The "default" algorithm is not usually big-O(N).
  
  If you use a O(N) algorithm, be sure to add a comment explaining how you did so - and to be sure the graders don't miss it!



• The donut-sharing problem    For up to +10 additional points, write a java program in a file named DonutSharing.java whose DonutSharing class has a main method that prompts the user for a single, positive integer (the length of the list of integers to come) and then accepts that list of integers - similar to the price-analysis program in hw12.java. In this case, each of the integers in the list represents the "tastiness" of a particular donut.
  
  The goal of this program is to determine how evenly the list of donuts can be divided, based on total tastiness. That is, the list must be separated into two disjoint sets (whose union is the whole list) such that the sums of the two sets are as close to each other as possible.
  
  Your Java program's task is to find this smallest achievable difference in tastiness scores when the list is divided into two parts. You simply need to print out that value (you don't need to print the "halves" of the list).
  
  For example, two runs of the program might look like this:

  What is the size of your list: 3
  Enter the donuts:  1 15 20
  * The minimum possible difference is 4
  
  What is the size of your list: 8
  Enter the donuts:  2 7 6 7 13 6 6 13
  * The minimum possible difference is 2
  
  What is the size of your list: 8
  Enter the donuts:  1 7 6 9 12 6 6 13
  * The minimum possible difference is 0
  

  Half-credit is available for any solution that works for small lists (up to 10-12 integers). Full credit, however, is available for implemented algorithms that work on lists of hundreds or thousands of integers... it is possible!
  
  In a comment at the top of your file, you should state the big-O run-time you expect for your algorithm and a sentence or two explanation (it need not be formal) of your reasoning.