Algorithms, Computer Programming

1. For parts (a) through (d), consider the following two algorithms that determine the number of 1 ft² tiles required to fill an empty room:

Algorithm 1: Places tiles in the room, one at a time, until the entire room is full of tiles. Each time a tile is placed in the room, a counter is incremented by 1. The final value of the counter is the number of tiles required to fill the room.

Algorithm 2: Places tiles in the room, one at a time, along the edge of two adjacent walls. Each time a tile is placed in the room, a counter is incremented by 1. A single calculation is then made to compute the area of the room by multiplying the number of tiles placed across the floor along one wall by the number of tiles placed across the floor along the adjacent wall. The result of this single calculation is the number of tiles required to fill the room.

For parts (a) and (b), suppose that it takes 1 second to lay one tile in the room and 60 seconds to perform a single calculation. Note that incrementing a counter is not considered a calculation.

(a) How long (in hours) does Algorithm 1 take to determine the number of tiles required to fill an empty room that is 16 ft wide by 225 ft long? Include all units and show all work.

(b) How long (in seconds) does Algorithm 2 take to determine the number of tiles required to fill the same 16 ft wide by 225 ft long empty room? Include all units and show all work.

(c) Suppose that Algorithm 1 takes 1.5 hours and Algorithm 2 takes 300 seconds. Which algorithm is faster? How many times faster is it? Calculate your answer to a maximum of two decimal places. Include all units and show all work.

(d) Represent Algorithm 1 using a flowchart. You do not need to get into the details of determining when the edge of a wall is full of tiles. Essentially, represent the algorithm as it is described.