COMP 105: HW #6

Think about each question carefully and then, using information from the textbook, videos, and your class notes, formulate an answer. Answers should be carefully thought out and clearly written (use complete sentences and make sure your grammar and spelling are correct). Answers should be typed using an editor or word processor of your choice.

You are welcome to discuss these questions with your classmates, the instructor, or a TA. However, if you make use of any outside information in answering these questions, or if you receive help from anyone, you need to acknowledge that along with your answer.

1. What is the purpose and job of the clock in a computer? (2 pts)


2. Consider the following JavaScript function:

       function sumEveryOther(arr)
       {
           var indx = 0;
           var sum = 0;
           while (indx < arr.length)
           {
               sum = sum + arr[indx];   // This is the operation to count
               indx = indx + 2;
           }
           return sum;
       }
   

   1. Give an English language description of what the function is doing. (2 pts)
   2. If we are interested in the running time of this program as a function of the size of the input (the array), we should focus on the key computations in the loop. In this case, the key computation is the updating of the sum. What is the running time of the function in terms of the key computation? In other words, how many times is the update statement executed for an array of size n? (2 pts)
   3. Express the running time in big O notation. (2 pts)


3. Consider the following JavaScript function:

       function anotherSum(arr)
       {
           var sum = 0;
           for (var x = 0; x < arr.length; x++)
               for (var y = 0; y < arr.length; y++)
                   sum = sum + y;
           return sum;
       }
   
   

   1. Give an English language description of what the function is doing. (2 pts)
   2. If we again assume the updating of the sum is the key computation in this function, what is the running time of the function? In other words, how many times is the update statement executed? (2 pts)
   3. Express the running time in big O notation. (2 pts)


4. Briefly explain the difference between a non-computable problem and an intractable problem. (3 pts)


5. How is the Church Turing thesis relevant to proofs of non-computability? (3 pts)