Question

Program 0 (50%): In many computer science courses, when you study sorting, you also study “runtime” - and it can be confusing to understand when you first see it.  For example, they say that BubbleSort “runs in O(n2)”  time (pronounced “Big-Oh of n-squared") - but what does that mean?  For simplicity, it means if you have n elements, the worst it could run would be n2 low-level computer operations (like comparisons, assignment statements and so on).  For example, if we had an array of 10 elements, then n == 10 and the worst-case scenario would be 100 operations (and we’re skipping some of the math behind “Big-Oh”).  Note: runtime doesn’t mean clock time!
 
Let’s look at BubbleSort for an array of 10.  In the first pass through the array, the most we could have would be ~9 comparisons, at which point the largest element is now at the end of the array.  The second pass would be ~8 comparisons (since we don’t have to look at the largest element – it's already in the correct spot).  The third pass would be ~7 operations and so on.  So the total operations would be 9+8+...+3+2+1 == 45.  But wait! 45 doesn’t equal 100, so what gives?  Remember, the 100 is a worst-case scenario, not the actual.  Mathematically, we can sum up the numbers between 1 to n using n*(n-1)/2 (plug in 10 for n and you get 45).  Interestingly, that equation still gives us n2 if we remove any constants.
 
For this assignment, you’re going to write a visualization that helps you understand the concept above (because employers like asking sorting questions).  Declare an array of 5 random numbers between 0-99 and run BubbleSort on it.  After each pass of BubbleSort (the inner loop), you should print the array as well as the total number of comparisons and the total number of swaps. You should initialize the array to random values.  Your output should be formatted like the output below.  However, because your random numbers are different, your results will vary.  Hint: start with a function that prints an array.  It will help with debugging. 
 
Sample run 1:  |79|12|72|87|17| ============ |12|79|72|87|17| Comps:1 Swaps:1   |12|72|79|87|17| Comps:2 Swaps:2   |12|72|79|87|17| Comps:3 Swaps:2   |12|72|79|17|87| Comps:4 Swaps:3   |12|72|79|17|87| Comps:5 Swaps:3   |12|72|79|17|87| Comps:6 Swaps:3   |12|72|17|79|87| Comps:7 Swaps:4   |12|72|17|79|87| Comps:8 Swaps:4
Page 2 of 4
  |12|17|72|79|87| Comps:9 Swaps:5   |12|17|72|79|87| Comps:10 Swaps:5

Program 1 (50%): For this program, you’re going to extend the “Find the Wabbit” game to 2 dimensions to create the game Battleship.  For simplicity, imagine you have an 8x8 board of holes and two “ships” that have pegs on the bottom that go into those holes.  When you play, you place your ships on your board and your opponent does as well.  However, you can’t see each other’s boards.  So, you call out coordinates – guessing where your opponent’s ships are and vice versa.  If you guess a correct coordinate, your opponent says “Hit”.  Otherwise, they say “Miss”.  For this program, you’re going to play against the computer, even though you know where two ships are ☺   I hard-coded this example to the following, where S means “Ship”:
 
| | | | | | | | | | |S| | | | | | | | |S| | | | | | | | |S| | | | | | | | |S| | | | | | | | |S| | | | | | | | | | | |S|S|S| | | | | | | | | | |
 
Write the program that prints out the board, but does not show where the two ships are (similar to Find the Wabbit).  For each round, print the board and ask the player for an X and a Y coordinate.  If there’s a hit, the ‘S’ should be replaced by a ‘!’.  If it’s a miss, the ‘ ‘ should be replaced by ‘X’.  The game is over when the number of hits == 8 (two ships of size 5 and 3).  You must use at least two meaningful functions that take in a 2D array. Note, when printing, you may need to print [y][x] instead of [x][y].
 
Sample run:
 
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Enter x: 0 Enter y: 4 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |X| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Enter x: 1 Enter y: 1 | | | | | | | | | | |!| | | | | | | | | | | | | | | | | | | | | | | | | |X| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
 
Page 4 of 4
[CUT]
 
Enter x: 4 Enter y: 6 | | | | | | | | | | |!| | | | |X| | | |!|X| | | | | | | |!| | | | | | | |X|!| |X| | | | | | |!| | | | |X| | | |X| | |!|!|!|X| | | | | | | | | | 64m3 0v3r