Assignment 14: Turing Machines, Algorithms, and a Coding Challenge!
Due Tuesday, April 27 by 11:59 PM.

Note the one-day extension on this final assignment. You may use a CS 60 dollar, as well (if you have one left), submitting it by Wednesday, 4/28 by 11:59 pm.

Submitting

There are several types of problems on this assignment -- because the cs60submitall command only submits files with particular extensions, please name your text files with a .txt extension and make sure your JFLAP turing machine has a .jff extension. As on previous assignments, your iscal, prolog, rex, and java programs should have .isc, .pl, .rex, and .java extensions.

The problems

• #1 -- [20 points: Turing Machines]
  
  Consider the language

    L = { w | w contains only 0's and the length of w is a power of 2 }.
    

  That is, the language contains all strings of 0's whose length is a power of 2.
  
  
  • You proved in the last assignment that this language is not accepted by a DFA, but it is accepted by a Turing Machine! Use JFLAP to construct a Turing Machine that accepts this language. You can assume that the inputs to the turing machine will be strings of 0's and no other character. (But they will not all have length equal to a power of 2!) I highly recommend spending some time thinking about this problem and sketching a solution on paper before using JFLAP. If you design the Turing Machine carefully, you can build it using surprisingly few states. (It's actually possible to use only three states, but it's tricky -- see the extra credit!) Save your turing machine as part1 (JFLAP will add the .jff extension.)

    Here are some important points about constructing Turing Machines in JFLAP:
    
    

  • When you start JFLAP (by typing java JFLAP) you should select 1-tape Turing Machine from the JFLAP window. You may want to check out the instructions in the Help menu.
  • Notice that blank symbols are represented by a small square -- sometimes you have to tab through the transition fields once or twice before JFLAP will let you enter a field.
  • Your machine need not have transitions for the input symbol 1. You can assume that the input will be all 0's.
  • Remember that Turing Machines can write any symbols they like on the tape. Your Turing Machine will need to write symbols other than 0!
  • JFLAP allows you to specify multiple states as accepting states and doesn't have an explicit rejecting state. Your machine should have exactly one accepting state. In order to have a rejecting state, simply make a state that doesn't have any transition rules coming out of it. If you end up in this state, JFLAP will reject the input.



• #2 -- [20 points: undecidability]
  
  Professor I. Lai claims to have written a program called a "Regularity Checker" which does the following: The Regularity Checker takes as input a program P (where P is a decider program or predicate, meaning that it just answers "yes" or "no" to its input). If the set of strings accepted by P happens to be a regular language, then the Regularity Checker says "yes". If the set of strings accepted by P is not a regular language then the Regularity Checker says "no".

  Why would a Regularity Checker be a good thing to have? Well, if it turns out that our program P accepts a regular language, then we know that it can be run on a computer with a finite amount of memory (a DFA)!

  Unfortunately, a Regularity Checker does not exist. Your job is to prove it. You may use diagrams to help explain your proof, but your proof must be clear and precise. You may submit your proof as part2.txt or you may submit it on paper under the office door of Profs. Ran or Zach (Olin 1245, 1265) by the deadline.




• #3 -- [20 points: big-O running times]
  
  For this problem, you may either type up your solutions for these next four subproblems A - D into a file named part3.txt and submit it in the usual way, OR you may write out the solutions and hand them in to Ran or Zach (or under their doors) by the due date/time. These four subquestions investigate the big-O running-time analysis of iterative (looping) and recursive code. To receive full credit on these problems, you need to show the work that justifies your big-O running time. In addition, you should provide the tightest (best) possible big-O bounds on the running time. After all, since big-O states merely an upper bound, all of these subproblems are O(n!).
  
  A     What is the big-O running time of this portion of code, in terms of N? (Notice how i is increasing!)

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

  
  
  B     What is the big-O running time of this portion of code, in terms of N? (Notice how j is increasing!)

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

  
  
  C     Whiling away time during a particularly slow CS 60 lecture, you discover a new, recursive algorithm for solving the Traveling Salesman Problem. You determine that the running time for your new algorithm on inputs of size N is given by the recurrence relation

          T(1) = 0
          T(N) = 1 + 4*T(N/2) 
          

  Find the big-O running time of your algorithm. Should you start to plan how you'll spend the $1,000,000 prize for showing P=NP, or do you still have more work to do before collecting it?
  
  
  D     One of the solutions to the reachability problem in rex uses the following definition for reachable(A,B,G), where A and B are nodes and G is a graph expressed as a list of edges:

          reachable(A,A,G)  => 1;
          reachable(A,B,[]) => 0;
  	      reachable(A,B,[[x,y]|R]) =>  reachable(A,B,R) ||
                                      (reachable(A,x,R) && reachable(y,B,R);
          

  Write a recurrence relation for T(N), the running time of the above reachable function in terms of N, the number of edges in the graph G. Then, "unroll" this recurrence relation in order to find a big-O estimate of the running time of this version of reachability. Count each logical operation (|| and &&) as one step.



• #4 -- [20 points: ISCAL, Prolog, and Rex revisited]
  
  Time Travel Securities, Inc. has sponsored a Harvey Mudd CS clinic to help it with its business plan. Their basic business is as follows:
  
  
  1. a customer tracks a stock's value each day over a span of time,
  2. at the end of that time, the customer travels back in time to the best day in the past at which to buy the stock. The customer buys as much of the stock as they can afford and waits...
  3. until the day, later in time, that is the best day to sell the stock. (Customers can make some additional money in sports betting as they wait.)
  4. After selling the stock at the profit-maximizing price, the customer returns to the present and enjoys their newfound wealth.
  
  
  Your task is to find the maximum profit that a customer can make (per share) with this strategy, given a list of daily stick prices. Notice that because you have to sell after you buy, the maximum time-travel profit is NOT simply the list max minus the list min! Even with a time machine, we can't sell before we buy (SEC regulations)... . However, we will assume that customers may sell on the same day they buy, so that the maximum profit can not be less than 0. In addition, your implementations should report a max profit of 0 when given an empty list of prices.
  
  To give Time Travel Securities as much flexibility in their security-analysis systems, co-founders Hadas and Dodds have requested a program that will solve this problem in three different languages: iscal, prolog, rex.
  
  ISCAL
  
  In the directory /cs/cs60/assignments/assignment14/, you will find a skeleton ISCAL file named timetrav.isc. This file demonstrates an ISCAL program that takes in a list of stock prices (positive integers), stores the list in memory (!), and then prints out the value of the first element of the list. The end of the input list is signaled by a 0.
  
  Starting from this file, create a version of timetrav.isc that outputs the maximum per-share profit available to Time Travel Securities customers... .
  
  Prolog
  
  In a file named timetrav.pl, write a prolog predicate timetrav(L,M) that is true when M is the maximum time-travel profit, given the list of daily prices in L. For full credit, your predicate needs to work when M is a variable (though not when L is a variable, certainly!).
  
  Rex
  
  In a file named timetrav.rex, write a rex function timetrav(L) that returns the maximum time-travel profit available. You may write any helper functions you might want.
  
  Be sure to submit your files timetrav.isc, timetrav.pl, and timetrav.rex with cs60submitall.



• #5 -- [20 points: Java revisited]
  
  Note that this problem is due Wed. 4/28 by 11:59 pm for everyone, regardless of your CS 60 dollar status.
  
  Time Travel Securities has become so popular that their analysis systems are slowing down their customer throughput! They return to you to write a java version of their program that will find profit-maximizing strategies as quickly as possible (but they still need platform independence!)
  
  In /cs/cs60/assignments/assignment14, you will find the skeleton of a java file named timetrav.java. This file has a constructor

      public timetrav(int[] prices)
    

  which you need to preserve.
  
  Your task is to write the single method int bestStrategy(). Of course, you may write any helper methods you would like. The bestStrategy method should return the maximum profit available from the input list of prices. We will make sure that this maximum profit is always an int, though in general there may be zero and negative values in the array prices. Keep in mind that there may be more than one best buy day and sell day, but there can be only one maximum profit.
  
  In a comment at the top of your file, be sure to report the big-O running time of your bestStrategy method and show the analysis that indicates how you obtained it. Only half-credit (10 points) will be given for a O(N^2) solution to the problem! For full credit, your solution needs to be at least as efficient as O(N log(N)). It is possible to write a O(N) algorithm, as well! (Not surprisingly, O(N) is the best possible asymptotic running time.)
  
  A helper class ttHelper is available.     In the assignment directory, /cs/cs60/assignments/assignment14, you will also find a file ttHelper.java. The ttHelper class offers a number of methods that help you test your bestStrategy method. In the main method of the timetrav and ttHelper classes, you will see examples of how to test from the console, from files, and using a random number generator. We will use the random number generator to test your code... .


Coding Challenge!     Everyone's code will be considered both in a head-to-head race (including a submission by Prof. Ran), as well as a "code exhibition" -- see the extra credit description below for details... .



Extra Credit

There are two possibilities for extra credit on this problem, each worth up to 8 points. Both are optimizations of above problems -- there is no need to submit any extra files!

Part 1: Turing machine minimization.

Although the question of how many states are in the smallest possible turing machine is undecidable in general, for the particular case of problem #1, 3 states is known to be the minimum needed. Extra credit will be given for solutions to the turing machine problem that use six or fewer states, up to 7 points for a solution using only 3 states -- which can be done, even using one of those states as the accepting state! However, you will certtainly have to write symbols other than 0 and 1 to the tape... .

If you find a solution with 3 states, you must have a flair for optimizations -- so the final bonus point (after all, you're not working on this for the points, ... are you?) is available for the 3-state turing machine that uses the fewest different symbols in its program. We have kept track of previous CS 60 student's solutions and hope that someone will break the current record of 6. (I do not know what the theoretical minimum is for this, but would like to!)



Part 2: The Coding Challenge

We will use the unix command time (or some similar utility) to measure the actual processor time that your solution to the timetrav.java problem requires. Prizes, points, fame, and fortune are at stake here! If you'd like to try using time, simply type man time at turing's prompt to see its options... . Anything you'd like to do to speed the code up is OK, as long as you follow these rules:
• All of the code is in java (no external calls to compiled C code!)
• You stick to the same interface as problem #5 (so that we can test it!)
• Your program still computes the correct maximum profit!
Incentive: can your code outpace Ran's submission? He claims no, but only time will tell... .

Also, for those uninterested in such a competition, there will also be a code exhibition option for extra credit -- the most creative approaches in any area: formatting, algorithm approach, style, etc. will be considered. Please make a note on the top of your file explaining what you've done. We will bend all style rules for this problem to allow maximum flexibility... .