Untitled

Computers in Engineering 308-208B 1995

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?