Computer Science 111
Fall 1998
Second In-Class Exam
December 7, 1998

Instructions: This exam is open-book. You may use your personal notes and problem set submissions, copies of any of the course Web pages, copies of the problem set solutions, and Computer Science: An Overview by Brookshear. No other materials are allowed.

You have 50 minutes for this exam. There are 5 problems. Show your work.

Use an exam booklet. Be sure that your name is on the front of the booklet and printed legibly. Write and sign the honor code pledge.

Honor Code Pledge: I pledge my honor that I have not violated the honor code during this examination.

Problem 1:(20 points)
Can an operating system allow several programs to have started and be in the process of execution at the same time without using time slices? That is, can an operating system provide some sort of multitasking without using time slices? If your answer is yes, how? If your answer is no, why not?

Problem 2:(25 points)
Given an array A with n items (or elements) A[1], A[2], ... A[n], write pseudocode that copies array A into another array B, but in reverse order. That is, after your pseudocode is executed, B should contain the same items as A, but reading B from B[1] through B[n] will give the items in the same order as reading A from A[n] through A[1]. You should try to make your pseudocode statements as much like statements in a real programming language as possible, but you need not use perfect Java (or perfect any other programming language).

Problem 3:(25 points)
Given array A as shown below, what is printed by applying PrintsWhat to the array A with length containing the value 7 and start containing the value 1. That is, execute PrintsWhat(A,7,1) and show the results. Also, show how the computation progresses by indicating when each recursive application of PrintsWhat is begun and when each value is printed. PrintsWhat is a procedure specified in Java-like pseudocode. (It is not correct Java.) Note that * denotes multiplication. Warning: giving what is printed correctly without showing how the execution produces that printing will not receive full credit.

PrintsWhat(int A[], int length, int start) 
  { 
    if ( 2*start <= length )
          {  temp = 2*start
             PrintsWhat(A, length, temp)  
          }
    if ( (2*start)+1 <= length )
          {  temptoo = (2*start)+1
             PrintsWhat(A, length, temptoo) 
          }
    print A[start]
  }

Array A:   
A[1]= 22
A[2]= 13
A[3]=  9
A[4]=  8
A[5]=  5
A[6]=  3
A[7]=  6

Problem 4:(20 points)
Below are two functions (in pseudocode) that return x^k (x raised to the power k) for arguments x and k ( k >= 0 ). Which function is more efficient? Justify your answer. You may do an example as part of your justification.

int PowerA(int x, int k)
  { 
    result = 1
    i=1
    while (i <= k)
       { result = result * x
         i = i+1
       }
    return result
   } 



int PowerB (int x, int k)
   { 
     if (k <= 0) 
          { return 1 }
     else {
             half = integer part of k/2     i.e. round k/2 down
             temp = PowerB(x, half)
             if (remainder of k/2 is 1)
                  {result = temp * temp * x}
             else {result = temp * temp}
             return result
           }
   }
Problem 5:(10 points)
In the definition of function PowerA in Problem 4, I gave the types of the two arguments, x and k, and the returned value, but I did not make any other declarations. What declarations would need to be made to satisfy a Java compiler?

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 doc.

The translation was initiated by Andrea LaPaugh on Thu Jan 7 13:13:25 EST 1999


Andrea LaPaugh
Thu Jan 7 13:13:25 EST 1999