University of Ottawa

School of Information Technology and Engineering

CSI1102

Quiz 4

Q1. [3 marks]

Determine the validity of the following statements.

(T/F) 1. Traversing a maze is much easier to do iteratively than recursively.

(T/F) 2. Queues and Stacks can be implemented using either arrays or linked lists.

(T/F) 3. If an exception is thrown and is not caught anywhere in the program, then the program terminates.

Q2. [3 marks]

Euclid’s algorithm for finding the Greater Common Divisor (gcd) is as follows: Given two natural numbers a and b, check if b is zero. If yes, a is the gcd. If not, repeat the process using b as the first number and a%b as the second number (a%b is the remainder after integer division of a and b). Write a recursive method “static int gcd(int a, int b)” that implements Euclid’s algorithm. Assume that b is less than a.

Example: gcd(18,4) = gcd(4,2) = gcd(2,0) = 2

static int gcd(int a, int b)

{

if (b == 0)

return a;

else

return gcd(b, a%b);

}

Last Name:	First Name:
Student number:	Section: