_{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?
}

_{How is a new process added to the list? }

_{}