Problem Class Questions for

1007 (Programming Principles) Week 3, 2005

Note, before your problem class spend time researching and preparing answers to these questions. There are many useful web sites but you need to learn how to search effectively and to evaluate the quality of a website (just because something is on the web doesn't mean it is accurate or trustworthy). Also make use of the Science Library.

1. An exampe of a classic kind of problem - during the night four travellers come to an ancient bridge over a bottomless chasm. The bridge can hold the weight of only two travellers at time, otherwise it will collapse. In addition, due to the state of the bridge, a torch is needed to light the way and avoid the holes.

The travellers need to cross the bridge but only have one torch between them. They also walk at different speeds, so the first traveller can cross in one minute, the second in two minutes, the third in five minutes and the forth in ten minutes. If two travellers cross together they have to travel at the speed of the slowest traveller.

What is the shortest time in which all the travellers can cross to the other side of the bridge?

2. Develop the algorithms to display the following patterns of characters. Note that a pattern must be displayed from left to right, line by line, one character at a time (also see programming exercises 2 questions). The algorithms should make use of loops to display repeated sub-patterns - can you see what the sub-patterns are? An algorithm that simply displays each character one-by-one without using loops is not an answer!

a) 
++++
-+++
--++
---+
----

b)
***********
*****+*****
****+ +****
***+   +***
**+     +**
*+       +*
**+     +**
***+   +***
****+ +****
*****+*****
***********

c)
%*&%*&%*&%*&
*&%*&%*&%*&%
&%*&%*&%*&%*
%*&%*&%*&%*&
*&%*&%*&%*&%
&%*&%*&%*&%*
%*&%*&%*&%*&
*&%*&%*&%*&%
&%*&%*&%*&%*

3. Determine what each of these statements prints and explain why:

 System.out.println(1.23E5 + 1.0);
 System.out.println(1.23E10 + 1.0);
 System.out.println(1.23E20 + 1.0);
 System.out.println(1.23E25 + 1.0E5);
 System.out.println(2.0 - 1.10);
 System.out.println(12345 + 5432l); // Sneaky - this does not print 66666 

4. Consider two rectangles drawn on a grid (like the drawing program in the programming exercises), so the (x,y) coordinate of each corner is known. Devise a function (that is a mathematical algorithm) to determine whether the two rectangles overlap. Take into account all the different ways two rectangles can overlap.

5. a) Develop an iterative algorithm to compute the square root of a real number to 6 decimal places (digits after the decimal point). Hint: find out about an approach like the Newton-Rhapson method.

b) Convert your iterative algorthm to a recursive algorithm.

c) If a real number is represented in a computer using a binary floating point representation that can store only 6 decimal places (digits after the point), how can you compute a square root to 20 decimal places of accuracy? Can you think of any situation where you need this level of accuracy?

6. Devise a mathematical algorithm that a computer might use to generate a sequence of random numbers. A random number is a number selected at random from a specified range, for example from the range 1-9 inclusive.

If a program implementing your algorithm has to be completely deterministic, is it actually possible to generate truly random numbers? Are the numbers different every time the algorithm is run?

7. Devise an algorithm to draw a maze. Here is an example of a simple maze: