Brute Force Approach - Algorithm Design Technique
Sam Kas Co is a shipping company that owns six ships. In emergency cases, the company will release the coordinates of each ship to other ships. The nearest ship will be assigned to help the trouble ship. Assume now that a ship. MayDay with coordinate (10,5), is in trouble. Table below shows the current coordinates for all the other ships.
|
Ship Name |
Coordinate X |
Coordinate Y |
|
Air |
18 |
11 |
|
Bay |
7 |
1 |
|
Cell |
3 |
7 |
|
Dream |
11 |
4 |
|
Eve |
6 |
6 |
1.
Write a pseudocode that receives the coordinate of the
troubled ships and a list of other ships’ coordinates. The algorithm will
return coordinate that of the nearest ship to the troubled ship.
FindNearestShip(troubleShipX,
troubleShipY, ship_list)
minDistance = INFINITE
nearestShip = “”
nearestX = 0
nearestY = 0
FOR each ship IN ship_list:
distance = SQRT((ship.coordinateX - troubleShipX)^2 + (ship.coordinateY
- troubleShipY)^2)
IF distance < minDistance:
minDistance = distance
nearestShip = ship.name
nearestX = ship.coordinateX
nearestY = ship.coordinateY
END IF
END FOR
RETURN (neareastShip, nearestX, nearestY)
END
2.
Using the proposed algorithm in (1), trace the
algorithm to identify the nearest ship. The input troubled ship is (10,5) and
input for others is stated in Table above.
|
Ship Name |
X |
Y |
Calculation |
Distance |
Nearest? |
|
Air |
18 |
11 |
|
10 |
No |
|
Bay |
7 |
1 |
|
5 |
No |
|
Cell |
3 |
7 |
|
7.28 |
No |
|
Dream |
11 |
4 |
|
1.41 |
Yes |
|
Eve |
6 |
6 |
|
4.12 |
No |
3.
Calculate the time efficiency for the algorithm in (1).
Show the steps.
|
ID |
Steps |
Code |
Notation |
|
1 |
Loop through n ships |
FOR each ship
IN ship_list: |
O(n) |
|
2 |
Calculate distance |
distance = SQRT((ship.coordinateX - troubleShipX)^2 + (ship.coordinateY
- troubleShipY)^2) |
O(1)
per ship |
|
3 |
Update minimum distance |
IF distance
< minDistance: |
O(1)
per ship |
|
4 |
Return nearest ship |
RETURN (neareastShip,
nearestX, nearestY) |
O(1) |
Overall time complexity is O(n)
Refer this video on to How to Calculate the time complexity: https://www.youtube.com/watch?v=KXAbAa1mieU
4.
What is the Algorithm Design Technique (ADT) that is
used in algorithm in (a)? State ONE advantage
of using the ADT.
Algorithm Design Technique used to solve the solution is Brute
Force Approach. This approach is suitable to handle the small input data. This method
will check all possibilities and compare the distance to find the nearest ship.
This method is accurate and guarantees the correct solution.
Ulasan