Problem 1. (25 pts) A Version of "Battleships" Alice and Beth are playing the following variation on the classic boardgame "Battleships." The game board is composed of a grid {0, 1,2..., n^ x [0,1,2, ..., n^ in which Beth has hidden inside one of the squared a battleship. In the given example (Figure 1a) where n = 5, the board is set such that the ship is inside the square 3,4] x [2,3]. Unfortunately, Alice is left with a single bomb, so Alice must find the square containing this battleship before she can use her only bomb to sink the battleship To that end, Alice has an arsenal of special "sonar"-bomb. A sonar-bomb is dropped to a single grid-point (i,j) and forces Beth to tell Alice the direction to the square where the battleship is placed in relation to the point (i, j): NE (above and right), NW (above and left), SW (below and left) or SE (below and right). So, to continue our example, in Figure 1b we illustrate the case that Alice drops a sonar on the point (2,1) (the red X) then is gets as a reply 'NE' (since the battleship is found inside the subgrid 12.3, 4, 5} {1, 2, 3, 4, 5)); and should Alice drop a sonar on the point (4,4) (the purple X) then the reply Alice gets is 'SW' (since the battleship is found inside the subgrid 10, 1,2,3,4) x [0,1,2,3,4)). To continue on our example, Alice eventually (in Figure 1c) drops a sonar on the points covered with an orange X: (3,3) (to which the reply is 'SE') and (4,2) (to which the reply is 'NW"), and so now Alice knows for certainty the bomb is inside the 3,4 x [2, 3 square, and she wins the game 5 0 0 0 0 1 23 45 0 1 23 45 0 1 23 45 Figure 1: An Example of This Version of Battleships (a) (15 pts) Help Alice win the game. Devise an algorithm for Alice to minimize the number of sonar bombs she uses until she is certain which square holds Beth's battleship. (b) (10 pts) Prove that your algorithm is optimal. That is, if the algorithm that you designed uses in the worst-case s sonar-bombs, then show that any algorithm that is guaranteed to find the square holding the battleship must also use s sonar-bombs in the worst-case Note: Ideally, your upper-and lower-bounds will match exactly (or up to 1). If you can't get them to match exactly, have your bounds be asymptotically the same Problem 1. (25 pts) A Version of "Battleships" Alice and Beth are playing the following variation on the classic boardgame "Battleships." The game board is composed of a grid {0, 1,2..., n^ x [0,1,2, ..., n^ in which Beth has hidden inside one of the squared a battleship. In the given example (Figure 1a) where n = 5, the board is set such that the ship is inside the square 3,4] x [2,3]. Unfortunately, Alice is left with a single bomb, so Alice must find the square containing this battleship before she can use her only bomb to sink the battleship To that end, Alice has an arsenal of special "sonar"-bomb. A sonar-bomb is dropped to a single grid-point (i,j) and forces Beth to tell Alice the direction to the square where the battleship is placed in relation to the point (i, j): NE (above and right), NW (above and left), SW (below and left) or SE (below and right). So, to continue our example, in Figure 1b we illustrate the case that Alice drops a sonar on the point (2,1) (the red X) then is gets as a reply 'NE' (since the battleship is found inside the subgrid 12.3, 4, 5} {1, 2, 3, 4, 5)); and should Alice drop a sonar on the point (4,4) (the purple X) then the reply Alice gets is 'SW' (since the battleship is found inside the subgrid 10, 1,2,3,4) x [0,1,2,3,4)). To continue on our example, Alice eventually (in Figure 1c) drops a sonar on the points covered with an orange X: (3,3) (to which the reply is 'SE') and (4,2) (to which the reply is 'NW"), and so now Alice knows for certainty the bomb is inside the 3,4 x [2, 3 square, and she wins the game 5 0 0 0 0 1 23 45 0 1 23 45 0 1 23 45 Figure 1: An Example of This Version of Battleships (a) (15 pts) Help Alice win the game. Devise an algorithm for Alice to minimize the number of sonar bombs she uses until she is certain which square holds Beth's battleship. (b) (10 pts) Prove that your algorithm is optimal. That is, if the algorithm that you designed uses in the worst-case s sonar-bombs, then show that any algorithm that is guaranteed to find the square holding the battleship must also use s sonar-bombs in the worst-case Note: Ideally, your upper-and lower-bounds will match exactly (or up to 1). If you can't get them to match exactly, have your bounds be asymptotically the same
