Problem Class Questions for

1007 (Programming Principles) Week 1

1. Write down the algorithm for performing long division by hand. Verify that your algorithm is correct for 11974608 ÷ 159 and 235675 ÷ 1886.

2. A regular hexagon has six sides. Given the coordinates of the centre of a hexagon and the length of a side, how do you calculate the coordinates of each corner of a hexagon?

3a. Assume that the River Thames is 100m wide at Tower Bridge, and is 10m deep for its entire width. Estimate how many cubic kilometres of water pass under the bridge each year assuming an even flow of 0.5m per second.

3b. If the depth of the river is actually 1m at each bank and 10m only at the centre, produce a new estimate of the amount of water that passes under the bridge each year.

3c. The Thames is actually tidal below Tower Bridge. At low tide water flows under the bridge at 1m per second, while at high tide the flow stops. Assume high tide occurs every 12 hours. Estimate how much water flows under the bridge per year taking into account the tides.

Note: You are asked to estimate - a calculator is not needed.

4a. Suppose you are in a corridor lined with 100 lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open, or open it if it is closed (call this toggling the locker). You continue toggling every nth locker on pass number n. After your hundredth pass of the corridor, in which you toggle only locker number 100, how many lockers are open?

4b. In a corridor with k lockers, how many lockers remain open after pass k?

5a. Imagine a cube made up of a 3x3x3 arrangement of smaller cubes (like a Rubik's Cube). How many small cubes are there on the surface of the larger cube?

5b. Now imagine you have cube made up of a 4x4x4 arrangement of smaller cubes. How many cubes are there on the surface of the larger cube?

5c. Generalise your solutions to 5a and 5b for an n x n x n arrangement. In terms of n how many small cubes are on the surface?

6a. You are standing in a corridor next to three light switches, all of which are off. Each switch operates a different incandescent light bulb in the room at the end of the corridor. You cannot see the lights from where the switches are. Determine which light corresponds to each switch. You may go into the room with the lights three times.

6b. Repeat 6a but now you are only allowed to go to the room twice.

6c. Repeat 6a again, but now you can only go to the room once.