Computers and Reality - Cognitive Science 110 - Spring 2007

1. Suppose we are handed a program P in JavaScript that computes some function f, and we're asked to write a URM program Q that computes the same function f. The goal of this problem is to show that this can be done algorithmically. Assume that P uses only commands of the following type:
   x = 0 ;
   x++ ;
   x=y ;
   var x ;
   if(x == y) { ...} ;
   while(x == y) {...} ;
   Note that the first three statements translate directly into the URM instructions Z, S, and T, respectively. The statement "var x" need not be "translated directly"; instead, we just replace every instance of x in P with a URM register. So it remains to take care of "if" and "while" statements:
   1. Explain how an "if" statement in P can be implemented into URM instructions.
   2. Explain how a "while" statement" in P can be implemented into URM instructions.
2. How about the reverse problem: can you give an algorithm for converting a URM program Q into a JavaScript program P?
3. Consider the following program, which we wrote today in class to compute the Collatz function: the number of iterations it takes to reach 1 by repeatedly applying the function

   f(x) = {

   x/2               if x is even 3x+1            otherwise

   As we saw in class, this program has a "bug"; for some reason, it never stops. Find its bug. (Note: it may have several bugs. Work on the program until everything works as it should.)

   ////////////////////////////////////////////////////
   var x // x serves as input
   x = 3
   
   var c // c counts the number of iterations
   c = 0 
   
   if(x==1) document.write("<br> we reached 1 in 0 iterations")
   while(x != 1)
   {
     var d // another counter
     var y
     y = x
     while(y >= d) // this loop is to tell if x is even or odd
     {
       if(x==d) {x=x/2 ; c++}
       d++
       if(x==d) {x=3*x+1;  c++}
       d++
     }
   }
   document.write("<br> We reached 1 in c steps")
   ///////////////////////////////////////////////////////////////
   

4. (Do this problem; but you don't need to write up anything for it.) The sequence of numbers: 1, 1, 2, 3, 5, 8, 13, 21, ... is called the Fibonacci sequence.  Do you see the pattern? Each integer is the sum of its two previous integers. The following program computes the "nth Fibonacci number" (e.g., 13 is the 7th Fibonacci number) by using recursion, i.e., using a function that calls itself! First run it to see that it really works. Then see if you can figure out how it works.
   
   ///////////////////////////////////////////////////////////////
   function fib(n)
   {
     if(n==1) return(1)
     if(n==2) return(1)
     if(n>=3) return(fib(n-1) + fib(n-2)) 
   }
   var n=7
   document.write("<br> fib(", n, ") = ", fib(n))
   ///////////////////////////////////////////////////////////////
   
   
5. (Do this problem; but you don't need to write up anything for it.) Below is a program that does the same job as the program in Problem 3 above, but without using any loops! It uses recursion instead. First run it to see that it really works. Then see if you can figure out how it works. Note: x%2 gives the remainder of dividing x by 2. Example: 7%2 = 1;  10%2 = 0.

   ///////////////////////////////////////////////////////////////
   function collatz(x)
   {
     if(x==1) return(0)
     if(x%2==0) return(1+collatz(x/2))
     return(1+collatz(3*x+1))
   }
   var z=3
   document.write("<br> Input: ",z, " ; Number of iterations: ", collatz(3))
   ///////////////////////////////////////////////////////////////

    
6. Consider the sequence of integers 0, 1, 2, 3, 6, 7, 14, 15, 30, 31, ... . Do you see the pattern? Odd integers are doubled, even ones are incremented by one. Define f(n) to be the nth integer in this sequence (e.g., f(9)=30, f(10)=31). Use recursion to write a JavaScript program that computes f. You may use the "mod function" %.