CS 395/Math 395: Analysis of Algorithms Semester: Spring 2019
Assignment #1
Written Portion Points: 110
Programming Portion Points: 115 (Probs: 1b, 3c, 6e, 7b, 8c, 9b, 10 and 12)
Total Points: 225 (Maximum score 200)
Read the “Assignment Guidelines” on BBLearn.
 Consider the following algorithm for finding the distance between the two closest elements in an array of numbers.
 [Points: 5] Make as many improvements as you can (at least two) in this algorithmic solution to the problem. If you need to, you may change the algorithm altogether; if not, improve the implementation given.
 [Points: 10] Write a computer program (using C/C++) implementing the final version (i.e., after your improvements) of the algorithm.

Königsberg bridges: The Königsberg bridge puzzle is universally accepted as the problem that gave birth to graph theory. It was solved by the great Swissborn mathematician Leonhard Euler (1707–1783). The problem asked whether one could, in a single stroll, cross all seven bridges of the city of Königsberg exactly once and return to a starting point. Following is a sketch of the river with its two islands and seven bridges:
 [Points: 5] State the problem as a graph problem.
 [Points: 8] Does this problem have a solution? If you believe it does, draw such a stroll; if you believe it does not, explain why and indicate the smallest number of new bridges that would be required to make such a stroll possible.

Gaussian elimination, the classic algorithm for solving systems of n linear equations in n
unknowns, requires about ⅓n3 multiplications, which is the algorithm’s basic operation.
 [Points: 5] How much longer should you expect Gaussian elimination to work on a system of 1000 equations versus a system of 500 equations?
 [Points: 5] You are considering buying a computer that is 1000 times faster than the one you currently have. By what factor will the faster computer increase the sizes of systems solvable in the same amount of time as on the old computer?
 [Points: 15] Write a computer program (using C/C++) implementing the algorithm given below for Gaussian elimination. Can your program answer the two questions above? Compare outputs from the program for the two questions with your previous answers.
 [Points: 8] Use the informal definitions of O, Θ, and Ω to determine whether the following assertions are true or false.
a) n(n + 1)/2 ∈ O(n3)
b) n(n + 1)/2 ∈ O(n2)
c) n(n + 1)/2 ∈ Θ(n3)
d) n(n + 1)/2 ∈ Ω(n)
 [Points: 12] Find the order of growth of the following sums. Use the Θ(g(n)) notation with the
simplest function g(n) possible.
 Consider the following algorithm.
 [Points: 4] What does this algorithm compute?
 [Points: 4] Find the time efficiency class of the algorithm.
 [Points: 5] Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.
 [Points: 4] Is this algorithm based on the bruteforce approach?
 [Points: 10] Write a computer program (using C/C++) implementing the Enigma algorithm above after your improvement (if any).

Restricted Tower of Hanoi: Consider the version of the Tower of Hanoi puzzle in which n disks have to be moved from peg A to peg C using peg B so that any move should either place a disk on peg B or move a disk from that peg. (Of course, the prohibition of placing a larger disk on top of a smaller one remains in place, too.)
 [Points: 10] Design a recursive algorithm for this problem and find the number of moves made by it.
 [Points: 10] Write a computer program (using C/C++) implementing the algorithm.
 [Points: 5] Design a recursive algorithm for computing 2n for any nonnegative integer n that is based on the formula 2n = 2n−1 + 2n−1.
 [Points: 5] Draw a tree of recursive calls for this algorithm and count the number of calls made by the algorithm.
 [Points: 5] Is it a good algorithm for solving this problem? Why or why not?
 [Points: 10] Write a computer program (using C/C++) implementing the algorithm. Your program should output a (rudimentarydrawn) tree of recursive calls and the number of calls.
 A network topology specifies how computers, printers, and other devices are connected over a network. The figure below illustrates three common topologies of networks: the ring, the star, and the fully connected mesh.
You are given a Boolean matrix A[0..n − 1, 0..n − 1], where n > 3, which is supposed to be the adjacency matrix of a graph modeling a network with one of these topologies.
 [Points: 10] Design a bruteforce algorithm for determining which of these three topologies, if any, the matrix represents and indicate its time efficiency class.
 [Points: 10] Write a computer program (using C/C++) implementing the algorithm.
 [Points: 30] Battleship game Write a computer program (using C/C++) based on a version of brute force pattern matching for playing the game Battleship on the computer. The rules of the game are as follows:
 There is only ONE player in this version of the game, the user of the computer.
 The game is played on one board of (10 × 10
tables of squares) on which the computer program places the ships, not seen by the player. At the start of the program, the program may randomly place the ships in the 10×10 matrix; or may read the matrix
(representing the board with the ships in place) from a data file.
 The board has five ships, each of which occupies a certain number of squares on the board:
 a destroyer (two squares, DD), a submarine (three squares, SSS), a cruiser (three squares, CCC), a battleship (four squares, BBBB), and an aircraft carrier (five
squares, AAAAA).
 Each ship is placed either horizontally or vertically, with no two ships touching each other. There must be at least one vacant square between two ships. Diagonal adjacency is ok.
 The game is played by the player “shooting” at the ships, entering the coordinates of the board, e.g.,A3 or H10, etc. The result of every shot is
displayed as either a hit or a miss by the program.
 To sink a ship, all squares occupied by the ship must be hit.
 The goal is to sink all the ships. The program will output how many hits were used to sink all the ships.
 a destroyer (two squares, DD), a submarine (three squares, SSS), a cruiser (three squares, CCC), a battleship (four squares, BBBB), and an aircraft carrier (five
 [Points: 10] Find the convex hulls of the following sets and identify their extreme points (if they have any):
 a line segment
 a square
 the boundary of a square
 a straight line
 [Points: 20] Write a computer program (using C/C++) implementing the bruteforce algorithm for the convexhull problem. Your program should work for any set of n distinct points, including sets with many collinear points.