YOUR LAST NAME _____________________________
YOUR FIRST NAME ____________________________
YOUR MUSICB CODE HB________________________
YOUR STUDENT NUMBER ______________________
YOUR ENGINEERING DEPARTMENT_____________
McGill University
Faculty of Engineering
COMPUTERS in ENGINEERING
308-208B
Final Examination
Examiners:
Prof. G. Ratzer Date: Thursday 13 April 1994.
V. Donne Time: 9.00 -
12.00 noon
This examination consists
of 19 questions and is worth 50% (or 70% - depending on your mid-term)
of the final course grade.
Questions 1 - 15 multiple choice 30 marks
Questions 16 0 (Yes, zero!)
Questions 17 7
Question 18 7
Question 19 6
Total 50 marks
Answer questions 1 to 16 on the IBM sheet provided using an HB pencil.
Select the BEST answer from the five given.
REMEMBER to put your student
number on the IBM sheets both as numeric digits and by filling
in the circles below each digit.
Answer questions 17, 18
and 19 in the space provided on this paper.
Do rough work on the backs
of pages.
No CALCULATORS allowed.
Use space below on this
page to bring any apparent ambiguities to the notice of the examiners.
MAKE SURE YOU WRITE YOUR
NAME AND STUDENT NUMBER ON BOTH THE COMPUTER SCORE SHEET AND THIS
EXAMINATION PAPER.
QUESTION 1:
What is the output of this
FORTRAN 77 program:
A = 5.6E1 + 3.4E2
I = MOD(69,5)
B = 56/7
C = 56./7
K = C
J = 89/3*5
PRINT *,I,J,K,A,B,C
END
1) 1 145 9 396. 8. 8.
2) 4 145 8 399. 8. 8.
3) 4 146 9 396. 9. 8.
4) 4 145 8 396. 8. 8.
5) None of the above
QUESTION 2:
K=5/4
L=1
P=0.0
Q=0.0
DO 7 J = 1,7,2
L=L + 1
P=P + J/3
7 Q=Q + K/J
PRINT *, K, L, P, Q
END
What will be the output
of the above program?
1) 1 4 3.0000 1.00000
2) 1 4 3.0000 2.00000
3) 1 5 4.0000 1.00000
4) 0 3 1.0000 1.00000
5) None of the above.
QUESTION 3.
What will the following
program output?
LOGICAL a, b
b = .FALSE.
i = 7.23
f = i/3
r = f + 0.8 - (3.0)**2
IF ( (-3*f) .GT. r ) THEN
a = .TRUE.
ELSE
b = 1.GT.0
a = b
ENDIF
IF (a .AND. b) THEN
PRINT *, 'MOZART'
ELSE
PRINT *, 'BEETHOVEN'
ENDIF
IF (i+f .GT. 9.0) PRINT
*, 'HAYDN'
IF ((.NOT. a .AND. b).OR.(.NOT. b .AND. a)) THEN
PRINT *, 'i = ', i
ELSE
PRINT *, 'r = ', r
ENDIF
PRINT *,f
END
1) MOZART
r = 9
2.4100
2) BEETHOVEN
i = 7
2.0000
3) HAYDN
i = 7
2.0000
4) MOZART
i = 7
2.4100
5) None of the above
QUESTION 4.
Consider the following FORTRAN 77 program :
INTEGER L(10)
READ *, N
READ *, (L(I), I = 1, N)
DO 10 I = 1, N
J = 1
LMAX = L(1)
DO 20 K = 2, N
IF (LMAX - L(K) .GE. 0) GO TO 30
LMAX = L(K)
J = K
20 CONTINUE
30 PRINT 50, LMAX
50 FORMAT(10I5)
L(J) = -1
10 CONTINUE
END
/DATA
10
63 24 58 79 13 27 46 39
84 91
What output is produced
by the above program with the data provided?
1) 13 24 27 39 46 58 63 79 91 84
2) 91 84 79 63 58 46 39 27 24 13
3) 13 24 27 39 46 58 63 79 84 91
4) 24 13 27 39 46 58 63 79 84 91
5) None of the above
QUESTION 5.
REAL A(5,5), B(5)
READ 10, ((A(I,J), J = 1, 5), I = 1,5)
CALL RSUM(A, B, T)
PRINT 20, B, T
10 FORMAT(5F7.2)
20 FORMAT(1X, 5F7.2, ' T = ', F7.2)
STOP
END
SUBROUTINE RSUM(X, S, P)
REAL X(5,5), S(5)
DO 10 I = 1, 5
S(I) = X(I,1)
DO 10 J = 2, 5
10 S(I) = S(I) + X(I, J)
P = X(1, 1)
DO 20 I = 2, 5
20 P = X(I, I) * P
RETURN
END
/DATA
1.0 2.0 3.0 4.0 5.0
0.0 1.0 2.0 3.0 4.0
-1.0 0.0 1.0 2.0 3.0
-2.0 -1.0 0.0 1.0 2.0
-3.0 -2.0 -1.0 0.0 1.0
What will the above program
produce as output with the given data?
1) 25.00 10.00 5.00 0.00 -5.00 T = 1.00
2) 15.00 20.00 5.00 0.00 -5.00 T = 1.00
3) 15.00 10.00 5.00 0.00 -5.00 T = 1.00
4) 15.00 10.00 6.00 0.00 -5.00 T = 1.00
5) None of the above.
QUESTION 6.
The following piece of C
code (where the declarations are: int i, a[101];):
for ( i = 0; i < 100;
i++ ) a[i] = 0;
has the exact same effect
(regardless of what 'a' contains) as
(A) for ( i = 0; i <
100; a[i++] = 0 );
(B) for ( i = 0; i <=
100; i = i + 1 ) a[i] = 0;
(C) for ( i = 0; i <=
99; i += 1 ); a[i] = 0;
(D) for ( i = 99; i >=
0; a[i--] = 0 );
(E) for ( i = 100; i >
0; a[--i] = 0 );
1) A - B - C
2) A - D - E
3) B - C - E
4) A - C - D
5) B - D - E
QUESTION 7
#include <stdio.h>
main() {
float a, b; int c, d;
a = 3.0; b = 5.0; c = 11; d = c - a + b;
if (d > c) d = c; else d = b;
a = d / 2;
if (a > b) c = a; else c = b;
c = b * c - d;
printf("%1.0f %1.0f
%d %d", a, b, c, d); }
The above C program will
output:
1) 5 5 14 11
2) 2 5 20 5
3) 6 5 14 11
4) 5 4 14 5
5) None of the above
QUESTION 8
#include <stdio.h>
int d;
int foo(x, y, z)
int x, *y, *z; {
x = *y + *z;
y = z;
*y = x;
return (x + *z); }
main() {
int a, b, c;
a = 2; b = 3; c = 4;
d = foo(a, &b, &c);
b = foo(b, &d, &a);
printf("%d %d %d %d",
a, b, c, d); }
The above C program prints:
1) 2 15 4 13
2) 21 42 7 14
3) 2 15 7 13
4) 16 32 7 14
5) None of the above
QUESTION 9
#include <stdio.h>
#define N 6
int A[N];
void bar(a, n) int *a, n; {
int i;
for (i = 2; i < n; i++)
a[i] = a[i - 1] + a[i - 2]; }
main() {
int i;
for (i = 0; i < N; i++) A[i] = i;
bar(A, N);
printf("%d %d %d %d", A[0], A[1], A[4], A[5]);
}
The above C program will
output
1) 1 1 2 3
2) 0 1 1 2
3) 0 1 2 5
4) 0 1 3 5
5) None of the above
QUESTION 10
(a) In C, the following two function calls are equivalent
(a is declared as int a[10];):
foo(a); foo(&a[0]);
(b) In C, the "not
equal" operator is <>
(c) In C, sin and cos functions both take a double as the parameter.
The parameter is an angle in radians.
The function returns a double.
(d) In an array A[10][10]
in C, A[0][0] is stored right next to A[0][1] in memory
(e) The following C program
is legal (i.e. the compiler will accept it):
main() {
int a, *b;
b = &a;
*b = 1;
&a = b; }
Which of the above is/are
false?
1) a - b - c - d - e
2) a - c - d
3) b - e
4) b
5) None of them is false
QUESTION 11.
Using the Newton-Raphson
method to find the approximation to the root of a function F(x),
if the initial value of x is 4 and F(x) = -x*x +11x - 24, what
is the value of x after 1 iteration ?
1) x = 2.66
2) x = 3.25
3) x = -3.25
4) x = -2.66
5) None of the above
QUESTION 12.
Consider the following steps
of a sorting algorithm sorting an array of five integers in ascending
order:
32 28 22 70 69
22 32 28 69 70
22 28 32 69 70
Which sorting technique
would produce such intermediate steps?
1) Shell sort
2) Selection sort
3) Both selection and insertion sort
4) Insertion sort
5) Bubble sort
QUESTION 13.
Which of the following triangularized
matrices represent a solution of this system of linear equations
?
2 x - 4 y - z = 7
- x + 3 y - 3 z = 6
4 x + y + 5 z = 8
1) 1 -2 -1/2 7/2
0 1 -1/2 1/2
0 0 1 -21/23
2) 1 -2 -1/2 7/2
0 1 -7/2 19/2
0 0 1 -183/77
3) 1 -2 -1/2 7/2
0 1 -7/2 19/2
0 0 1 -159/49
4) 1 -2 -1/2 7/2
0 1 -1/2 1/2
0 0 1 -3/5
5) None of the above.
QUESTION 14.
Consider the following statements:
a) The Runge-Kutta method
to estimate a differential equation is less accurate than Euler's
method.
b) This pseudo-code implements
the Euler algorithm:
x <-- 0
y <-- y0
while ( x <= xf )
y <-- h*y + f(x)
x <-- x + h
c) Given the differential
equation y' = (0.25)*y + x + 7 on the interval [0, 0.4], and 2.478
is the value of y at x=0.2 using Euler's method with h=0.1 and
initial value of y=1 (i.e. y(0) = 1 ).
Which of the above statement(s)
is(are) false?
1) b only
2) a and b
3) a and c
4) a,b and c
5) a only
QUESTION 15.
If we approximate the integral
of the function f(x) = x*x - x + 1 from 0 to 2 with h=0.5 to be
equal to 2.75, which numerical integration approximation was used?
1) Midpoint rule
2) Left endpoint rule
3) Right endpoint rule
4) Trapezoidal rule
5) Simpson's rule
QUESTION 16.
On your IBM computer marked
sheet fill in circle ONE = 1
(This is to prove that you are still awake and got this far in
the exam!!)
QUESTION 17.
Four sorting methods were studied in class, each with strengths and
weaknesses.
a) Using "Big-O"
notation, how would you describe the performance of each of the
four sorting methods, in terms of:
- number of comparisons
- number of swaps
- running time
b) Is it true that an algorithm
that is O(n**2) may actually run faster than one that is O(n*logn)?
If so, for what cases of n?
QUESTION 18.
The Gaussian error function,
Erf(y), is defined by the integral from x = 0 to x = y of the
expression Exp(-x**2)*2/Sqrt(Pi).
STEP A: State the formula
for the Trapezoidal Rule for numerical integration of a function
f(x) in terms of lower and upper limits a and b, number of panels
n, and step size h.
STEP B: Write a FORTRAN
77 function to evaluate the integrand for Erf. That is, a function
F(x) which encodes the above expression for a value of x accepted
as an input parameter.
STEP C: Write a general purpose FORTRAN 77 function that uses the Trapezoidal Rule to estimate the integral of f(x) between a and b. Your function should accept as parameters values for a, b, and n,
and return the area.
STEP D: Write a main FORTRAN
77 program which reads input data for Y and tolerance Delta.
The program must then compute
Erf(Y) by calling the Trapezoidal Rule function with n = 2, 4,
8, 16,... until two successive estimates of the have an absolute
difference less than Delta.
Finally, the program must
print out values for Y, Erf(Y), and a count of the number of times
the Trapezoidal Rule function was called.
QUESTION 19.
A time-shared computing
system such as MUSIC needs to maintain a set of processes (jobs)
waiting for service (i.e. one hundred 308-208 students working
on an assignment at the same time). Usually, the MUSIC system
will make short jobs seem instantaneous so that most users will
be happy with the system's performance and will not complain.
A process that requires quite a few seconds of processing (i.e.
compiling and running a program with several thousand lines) cannot
be made to appear instantaneous.
One way of favoring short
processes is to give each process a priority number (in the range
0 to 100). The system will execute all higher priority (short
job) processes before getting to a lower priority (long job) process.
So, the system maintains a list of processes to be executed, SORTED
in order of priority. It will perform the following operations
on this list:
- always pick the highest
priority process
- once the process is finished
executing, remove it from the list
- whenever a student submits
a new job (i.e. compiling and executing his/her program), the
system will give the job a priority and add it to the list
Assuming that at most 1000
jobs can be in this list at any one time, describe how you would
solve this in a program. Don't write code; just give a description
(use English or French, and draw diagrams if necessary). Here
are some things you should write about:
- List several alternative approaches, and choose the one you think is best.
Your solution doesn't have
to be elegant; it has to work, though.
- Is using hash tables an effective way of solving this problem?
Why or why not?
- What does your data structure
look like?
- How is the highest priority
process picked and deleted from the list?