CSC231 Final Exam 12/08

--D. Thiebaut 15:03, 1 December 2008 (UTC)

---

Take Home Exam

This exam is due on Dec 19, at noon.

This exam is given under the rules of the honor code. You have access to all your notes, to books, and to the Web. You cannot, however, discuss the details of the exam with anybody other than your instructor. Questions regarding the exam can only be asked in class, or via email. In case you send a question via email, the text of your question in its entirety and the answer to it will be broadcast back to the whole class, so be careful not to divulge too much in your questions. In this fashion, everybody will have access to the same information and same clarifications.

Problem #1 (2 points)

Part 1 (1 point)

You are done with your exams, and enjoying the free time before you leave the college to go around the quiet campus, and, just for fun, you stop by the campus center. After getting a nice cup of hot chocolate, you climb the steps to the second floor, and see two of your friends, both computer science majors, engaged in a heated discussion in one of the small conference rooms. You enter the room and ask them what all the fuss is about.

"Oh, it's this computer program," says Jane, one of your friends. We don't agree on its limits. "Maxim thinks it will run out of memory before it will ever finish, while I think we will run out of time before it finishes!"

(Note from DT: "running out of time" here means something that will take much much longer than we are willing to wait for. Running out of time in this case would mean an execution time of several centuries.)

"What do you mean?" you ask.

"Well, it's the tower of Hanoi program says Maxim. We have just seen it in class. It's a famous program. In fact it's all over the place on the Web. It's a hugely recursive program, and it generates all the moves you need to follow in order to move all 64 disks from one peg to another peg."

(Note from DT: feel free to learn more about the towers of Hanoi by exploring the Web at this point!)

"Really" you ask? "What does the code look like?"

"Here. That's what we did in class the other day," says Jane, and she hands you a piece of paper with the C code for the moveDisk function:

               main() {
                   moveDisk( 64, 'A', 'B', 'C' );
               }

               void moveDisk( int numberOfDisks, char FromPeg, char ToPeg, char ExtraPeg ) {
                   if ( numberOfDisks == 1 ) 
                      printf( "Move disk from %c to %c\n", FromPeg, ToPeg );
                   else {
                      moveDisk( numberOfDisks-1, FromPeg, ExtraPeg, ToPeg );
                      printf( "Move disk from %c to %c\n", FromPeg, ToPeg );
                      moveDisk( numberOfDisks-1, ExtraPeg, ToPeg, FromPeg );
                   }
               }

(A python version of this code is available here.)

You take the code and sit for a while, scribbling some notes on the sheet... A few minutes later you get up and announce "Of course! ..."

And you start telling them why one of them is wrong, and why the other one is right, and why...

What are your arguments?

You may assume that the stack is at most 6 MBytes in length.

Part 2 (1 point)

Write the Tower of Hanoi program in assembly. Store your program in a file called hanoi.asm.

Your program should display the number of disks N used, and then the series of moves that need to be taken to move all the disks from one peg to the other.

Instead of the program asking the user for the number of disks to start with, make the program use a global variable that defines how many disks are used:

          section .data
N         dd      5

Use 5 for N Store your answers to Part 1 in the header of the program and submit it as follows:

              submit exam hanoi.asm

Problem #2 (2 points)

We saw that Python seems to be more "clever" about floating point numbers than other languages.

Sometimes, however, it seems to behave in unexpected ways. To see an example of this, get the following Python program: sum_of_floats.py, and study it. It creates a list of 10 random floating-point numbers, each one the result of picking a random real number between 0 and 1.0, which is then multiplied by 10 raised to some other random integer in the range -40 to +40.

The program then computes the sum of the ten numbers as stored in the list. That's sum1. Next it sorts the list in increasing order and computes the sum again, this time saving it into sum 2. Finally, it reverses the list so that it is sorted in decreasing order, and computes the sum of the numbers which it stores in sum3. It then compares sum1, sum2, and sum3, and displays the list and the sums if these are not equal.

Question 1: Explain why the 3 sums are usually the same, but sometimes not equal. Base your explication on the 32-bit IEEE Floating-Point format which we saw in class.

Question 2: What recommendations would you make when one has to compute the sum of several floating-point numbers?

Question 3: What test could you use when you are given a list of numbers to figure out whether the sum might not be correct when the addition is performed?

Question 4: Do we have to be worried about incurring the same problem when computing the product of a series of real numbers?

Store your answers in a text file (not a Word doc file, please!) called sumfloat.txt and submit it as follows:

           submit exam sumfloat.txt

Grading

The main rules that will be followed when testing and reading your programs:

1. programs should run, and not crash
2. programs that crash without outputting any result will be given at most a D+
3. programs should solve the problem given, but if they do not, they should come "close", and solve a simpler version of the problem, or only a few cases covered by the problem.
4. the documentation should explain what the program does and does not do, and what assumptions have been taken that transform the original problem.
5. the header of the program should contain
   1. The name of the program
   2. The name of the programmer
   3. The date
   4. The problem addressed by the program
   5. How the program solves the problem, or a variation of the problem.
   6. What limitations or special cases that the program either covers, or does not cover.
6. Each function should have a header indicating what the function performs, and what registers it modifies, and eventually whether it uses global variables or not.

For the written parts, you are allowed and encouraged to use the computer to generate your answer. This means that you shouldn't hesitate to write programs, use programs (eXcel for example), or whatever other tool you have access to. In this case, include copies of the programs or screen captures illustrating the data that help you make your case.