CS42: Midterm Examination

The scope of this examination includes much of the material covered in the first half of the course. This examination does not count toward your grade for the course, although I will ask you to give it your best effort in the time allotted (about 45 minutes). I will mark the exams and give you a grade. The goal of this examination is to give you and me feedback on how well you're learning the skills and material covered in the course.

Charlie and Ray work for the Simple Database Company and have together developed a high level language which they call SDL. Charlie feels that SDL would best be implemented by translating the SDL into Level 3 code (operating system machine level), while Ray advocates translation of SDL into a platform independent code which would then be interpreted by a platform-specific Level 4 virtual machine. Discuss and compare the two approaches. Be sure to consider speed, flexibility, cost, complexity, and other approriate issues.
Note: The persons named in this problem are fictitious. Any resemblance to real persons is purely coincidental.
The Really Useful Computer Company has produced a prototype machine in which the Level 0 interpreter (hardware interpreting the microcode) requires about 25 nanoseconds (25 x 10**-9 seconds) per microinstruction, and the Level 1 interpreter (microcode interpreting the conventional machine language) requires an average of 12 microinstructions per conventional machine language instruction. The test program, which places a typical practical load on the machine, takes 30 seconds to run. The hardware team believes that given an additional 30 days, it can shave 5 nanoseconds per microinstruction off the execution time, with little or no change to the microcode. The microcode team believes that it can reduce the average number of microinstructions per conventional machine instruction to 10 within the same period.
1. How long will the test program take if only the hardware team succeeds?
2. How long will the test program take if only the microcode team succeeds?
3. How long will the test program take if both teams succeed?
4. The management team feels that only a potential improvement of 33% or more (as measured by the time required by the test program) would warrant delaying the machine by a full month. Should they give the teams the go-ahead?
Convert the following numbers base 3 to their decimal, binary, and hexadecimal equivalents: 120, 21012, 1020102.
Convert the following numbers base 10 to their binary equivalents: 10.5, -12, 1023.9921875.
Convert the following decimal numbers to sixteen-bit one's complement binary numbers: 32500, -12345, -2.
Convert the following decimal numbers to eight-bit two's complement binary numbers: 120, -12, -120.
Convert the following eight-bit one's complement numbers to decimal: 10101010, 01000010, 11111111.
Convert the following eight-bit two's complement numbers to decimal: 01010101, 10111100, 11111111.
Perform an eight-bit two's complement addition of 01010101 and 10101011.
In IEEE single-precision notation, there is a sign bit, an 8-bit radix 2 excess 127 exponent, and a 23-bit significand in which the leading 1 is implied for normalized numbers.
Convert the following decimal numbers to a 32-bit hexadecimal representation of their IEEE single-precision floating point equivalents: 32.03125, -1.5, -99.875.
Convert the following 32-bit hexadecimal representations of IEEE single-precision floating point numbers into their decimal equivalents: 01230000, FEDC0000, ABC00000.
Consider a computer having a 12-bit memory cells.
1. How many bytes of memory can be accessed using a 12-bit address?
2. How many bytes of memory can be accessed using a 24-bit address?
3. How many bytes of memory can be accessed using a 36-bit address?
4. If a single memory cell were used to store a single character, how many different characters could be represented by a cell?
A certain hard disk has 320 cylinders, 7 tracks, and 31 sectors of 512 bytes each. It spins at 3600 revolutions per minute, and has an adjacent cylinder seek time of 3 msec, and a max seek time of 100 msec. Switching between tracks in the same cylinder is instantaneous.
1. What is the total available storage capacity of the disk?
2. What is the minimum time required to read all the data on the disk, starting with the first track of the first cylinder, reading all the tracks in that cylinder, advancing to the next cylinder, etc.?

Compute the Hamming distance of the following code:

0000011110001111
0001011010011110
0010010110101101
0011010010111100

While browsing the web, you found an 8 Megabyte mpeg file which you wanted to download. Calculate a MINIMUM time (in days, hours, minutes, seconds) required to transmit the file to your PC at each of the following data rates:
1. 56 Kbits per second (synchronous)
2. 19.2 Kbits per second (asynchronous)
3. 110 bits per second (asynchronous)
Examine the following diagram.
1. What does this circuit do?
2. Using truth tables and/or boolean logic, prove your statement about what the circuit does.
3. How many transistors (minimum) would be required to implement this circuit?