Semester 1 Final Exam

Introduction to Computer Science:
Semester 1 Final Exam: Friday, Jan 12, 2001
Sewickley Academy, 2000-2001

Show your work as much as possible.
You must work alone without books, notes, files, etc.
When you are finished, you will have the following files on your desktop:

1a.txt, 1b.txt, 1c.dwm, 1d.cpp, 2.asm, 3.cpp, 4.cpp, 5.cpp

Place these files in a single zip file called "<yourUserId>Final.zip", as in "dkosbieFinal.zip".
Good luck!

Question 1.

1a) Prove that all boolean logical functions can be expressed using only Nor gates. Place this in a file called "1a.txt" on your desktop.

1b) As an example, follow the steps in your proof of (1a) to express (A Xor B) using only Nor gates. Place this in a file called "1b.txt" on your desktop.

1c) Prove that your expansion in problem (1b) works by creating a Digital Works circuit (in a file called "1c.dwm" on your desktop) which takes two inputs, A and B, and has two outputs -- the first is simply (A Xor B) and the second is your answer to (1b) using only Nor gates. Note that when constructing this circuit you do not have to duplicate sub-circuits, but instead can re-use their output (as we demonstrated in class). The "proof" is clear when the 2 inputs are set to their 4 possible combinations (true/true, true/false, false/true, false/false), and the 2 outputs have the same values for all 4 combinations.

1d) Prove that your expansion in problem (1b) works by writing a C++ program as follows. First, write the following two functions (in a file called "1d.cpp", which should be placed on your desktop):

bool xor(bool a, bool b)
{
// returns true if and only if (a xor b) is true
}
bool nor(bool a, bool b)
{
// returns true if and only if (a nor b) is true
}

Next, write the function norExpansionOfXor:

bool norExpansionOfXor(bool a, bool b)
{
    // This function uses the nor() function above to compute
    // the expansion of Xor from problem (1b).
    // Note that this function must call the nor() function,
    // and may only call the nor() function.
}

Finally, in your main() function, simply demonstrate that xor(a,b) equals norExpansionOfXor(a,b) for all 4 possible combinations of a and b (true/true, true/false, false/true, false/false). Be sure to output all 4 values from both functions as well, so your output should begin with something like:

a=false,b=false --> xor(a,b)= false , norExpansionOfXor(a,b)= false
a=false,b=true --> xor(a,b)= true , norExpansionOfXor(a,b)= true

Question 2. Write a SimpSim program (in a file called "2.asm" on your desktop) which, when run, uses the special ASCII symbols to output a box surrounding the letters SA, as in:

Further, your program should assume there is a count in memory location FF, and should print out that many such boxes. Hint: You may want to look at both HelloWorld and OutputTest, which are under the Examples item in the Help menu of SimpSim.

Question 3. Write a C++ program (in a file called "3.cpp") which uses mergeSort to sort lists from largest to smallest (so v[0] is largest). Include a main() which repeatedly tests your sort on vectors of random integers until the user enters a vector size <0. Be sure to print out both the unsorted and the sorted vectors.

Question 4. Write a C++ program (in a file called "4.cpp") which uses Monte Carlo methods to determine the probability that when 2 dice are rolled they come up with a 7 (that is, a 6-1, 5-2, 4-3, 3-4, 2-5, or 1-6).

Question 5. Write a C++ program (n a file called "5.cpp") which repeatedly asks the user for a number (exiting when the input is <0) and outputs the sum of the digits in the number the user entered. Here is some sample output:

Enter a number (<0 to exit): 43
The sum of the digits in 43 = 4 + 3 = 7.
Enter a number (<0 to exit): 1904
The sum of the digits in 1904 = 1 + 9 + 0 + 4 = 14.

See Course Home Page.