CS 207
Midterm 1
Ondich
Due 8:30 AM Friday, April 28, 2000
For this exam, you may use your textbook, your notes and assignments,
your brain, and divine guidance if available. You may not use other
books, other people, or Internet resources. If you get stuck, talk to
Jeff Ondich, but please don't talk to anyone else about the exam.
Submit your answers on paper. For the PDP8 code in problem 1, submit your .pal
file using HSP.
- (12 points) Write a PDP8/E subroutine that takes the non-negative
integer N (stored in the AC at the time the subroutine is called) and
returns (in the AC) the largest non-negative integer whose square
is less than or equal to N. In particular, if N is a perfect square,
the result will be the square-root of N.
Your goal here is not an efficient algorithm (so, in particular, you
should not use your multiplication code from assignment 2). Your
goal is to write a correct subroutine that takes up as few words of
memory as possible. Your score will be based on correctness (8 points)
and brevity (4 points).
- (12 points) The table below shows the execution times for all of the
PDP8/E instructions (not including op-code 6).
Execution times in micro-seconds for PDP8/E instructions
--------------------------------------------------------
Addressing mode
------------------------------------------
Instruction Indirect with
Type Direct Indirect auto-increment
--------------------------------------------------------
AND 2.6 3.8 4.0
TAD 2.6 3.8 4.0
ISZ 2.6 3.8 4.0
DCA 2.6 3.8 4.0
JMS 2.6 3.8 4.0
JMP 1.2 2.4 2.6
Opcode 7 1.2 (addressing mode irrelevant)
--------------------------------------------------------
Answer the following questions:
- Does the notion of CPI make sense in the context of the PDP8/E?
Why or why not?
- Even if you said CPI does not make sense, you can still use
the timing table below to compute the native MIPS for
the PDP8/E if you first make some assumptions. What sort
of assumptions do you need to make?
- Using assumptions of the kind you described in the previous question,
compute the native MIPS for the PDP8/E. Make sure to explain
exactly what your assumptions are.
- In the Chapter 2 exercises, the fictional but more-or-less
modern machines you considered had native MIPS ratings around
400-600. Based on these ratings, how much faster than the PDP8/E
are modern machines? Does using native MIPS for comparison
misrepresent the relative performance of the PDP8/E and modern
machines? In whose favor?
- (7 points) Consider the following program:
#include <iostream>
int factorial( int N );
int main()
{
for( int N=1; N <= 40; N++ )
cout << N << "! = " << factorial( N ) << endl;
return( 0 );
}
int factorial( int N )
{
int product = 1;
for( int i=2; i <= N; i++ )
product = product * i;
return( product );
}
When you run this code, you get correct values of N! for a while, and then
you start to get incorrect values. Answer the following questions:
- For what value of N do you first get an incorrect value
for N factorial? Why? Does the answer you get make any kind
of sense, or is it just a random value?
- For what value of N does N! first get reported as 0? Why
do the zeros start at this particular value of N?
- (6 points) Consider the following program:
#include <iostream>
int main()
{
int m = 100;
int a[4];
int n = 200;
int i;
for( i=-1; i <= 4; i++ )
a[i] = i;
cout << "m = " << m << endl;
cout << "n = " << n << endl;
for( i=0; i < 4; i++ )
cout << "a[" << i << "] = " << a[i] << endl;
return( 0 );
}
Answer the following questions, which assume you are compiling
and running this program on one of the Math/CS Linux machines
(I tried it on codd.mathcs.carleton.edu).
- What happens to the variables m and n, and why?
- How does the order in which local variables are
declared affect their locations in memory when the
program runs?
- If I change the first for-loop to "for( i=-1; i <= 6; i++ )",
the program runs as before, but then suffers a segmentation
fault at the very end. Why?
- (2 points) Please direct me to an interesting Web site.
- (8 points) Write an algebraic expression describing the following
boolean function of three variables. Then simplify the expression
as much as you can, and draw a digital logic circuit that implements
the function based on your simplified formula.
A B C || f(A,B,C)
===============================
0 0 0 || 0
0 0 1 || 1
0 1 0 || 1
0 1 1 || 1
1 0 0 || 0
1 0 1 || 1
1 1 0 || 1
1 1 1 || 0