CSC231 Final Exam 2015

This exam is due on Dec 22nd, at 4:00 p.m..
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 using Piazza. Do not post code on Piazza. Do not suggest or imply possible solutions in your posts on Piazza. All three problems are worth the same number of points.

<showafterdate after="20151201 00:00" before="20151231 00:00">

Problem #1

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: "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 our case means 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."

"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, and that printf() takes at most 200 bytes of stack when it prints something.

Submission

See at the end of this page.

Problem #2

Python can handle very larger integer numbers, much larger than the integers Java can handle.

With real numbers, however, Python sometimes behaves in unexpected ways. To see an example of this, get a copy of 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.

Before answering the questions below, you may want to read this interesting page explaining how floating-point numbers are added inside an FPU.

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 perform (in any language of your choice) 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? Why?

Submission

• See at the end of this page.

Problem #3

Assume that we want to create a 16-bit version of the IEEE floating point format, with 1 sign bit, 7 bits for the exponent, and 8 bits of mantissa (1+7+8 = 16).

We want to follow the same rules the IEEE used to define the 32-bit and 64-bit formats.

Questions

Q1: what is the smallest normalized positive non-zero number we can represent with the new 16-bit format?

Q2: what is the largest normalized positive non-infinite number we can represent?

Q3: what is the smallest denormalized positive non-zero number we can represent?

Q4: what binary or hex values represent + infinity, - infinity, and NaN?

Q5: what is the bias of the exponent?

Q6: what is 1.75 in this new format?

Q7: what is -1.75 in this new format?

Q8: what is the real number with this representation 0 0001111 01000000?

Submission

• See next section.

Moodle Submission

Write the answers to the 3 problems in a pdf and submit it on Moodle in the section labeled Final Exam. Make sure to submit a copy of your pdf every time you have added a new problem to it!
Make sure to add your name at the top of the document you submit!.
</showafterdate >