Chapter 1

A concept related, but not identical, to an algorithm is the idea of a heuristic. Read about heuristics and identify differences between the two. Describe a heuristic for obtaining an approximate answer to the sum of two threedigit numbers and show how this "addition heuristic" differs from the addition algorithm of Figure 1.2.

Identify which type of algorithmic operation each one of the following steps belongs to: a. Get a value for \(x\) from the user. b. Test to determine if \(x\) is positive. If not, tell the user that he or she has made a mistake. c. Take the cube root of \(x\). d. Do Steps 1.1, 1.2, and 1.3 x times.

Under what conditions would the well-known quadratic formula $$ \text { Roots }=\frac{-b \pm \sqrt{b^{2}-4 a c}}{2 a} $$ not be effectively computable? (Assume that you are working with real numbers.)

The following is Euclid's 2,300-year-old algorithm for finding the greatest common divisor of two positive integers \(/\) and \(J\). Step Operation 1 Get two positive integers as input; call the larger value / and the smaller value J 2 Divide \(I\) by \(J\), and call the remainder \(R\) 3 If \(R\) is not 0 , then reset \(/\) to the value of \(J\), reset \(J\) to the value of \(R\), and go back to Step 2 4 Print out the answer, which is the value of \(J\) 5 Stop a. Go through this algorithm using the input values 20 and 32 . After each step of the algorithm is completed, give the values of \(I\), \(J\), and \(R\). Determine the final output of the algorithm. b. Does the algorithm work correctly when the two inputs are 0 and 32 ? Describe exactly what happens, and modify the algorithm so that it gives an appropriate error message.

A salesperson wants to visit 25 cities while minimizing the total number of miles she must drive. Because she has studied computer science, she decides to design an algorithm to determine the optimal order in which to visit the cities to (1) keep her driving distance to a minimum, and (2) visit each city exactly once. The algorithm that she has devised is the following: The computer first lists all possible ways to visit the 25 cities and then, for each one, determines the total mileage associated with that particular ordering. (Assume that the computer has access to data that gives the distances between all cities.) After determining the total mileage for each possible trip, the computer searches for the ordering with the minimum mileage and prints out the list of cities on that optimal route, that is, the order in which the salesperson should visit her destinations. If a computer could analyze \(10,000,000\) separate paths per second, how long would it take to determine the optimal route for visiting these 25 cities? On the basis of your answer, do you think this is a feasible algorithm? If it is not, can you think of a way to obtain a reasonable solution to this problem?

One way to do multiplication is by repeated addition. For example, \(47 \times 25\) can be evaluated as \(47+47+47+\ldots+47\) (25 times). Sketch out an algorithm for multiplying two positive numbers \(a\) and \(b\) using this technique.

A student was asked to develop an algorithm to find and output the largest of three numerical values \(x, y\), and \(z\) that are provided as input. Here is what was produced: Input: \(x, y, z\) Algorithm: Check if \((x>y)\) and \((x>z)\). If it is, then output the value of \(x\) and stop. Otherwise, continue to the next line. Check if \((y>x)\) and \((y>z)\). If it is, then output the value of \(y\) and stop. Otherwise, continue to the next line. Check if \((z>x)\) and \((z>y)\). If it is, then output the value of \(z\) and stop. Is this a correct solution to the problem? Explain why or why not. If it is incorrect, fix the algorithm so that it is a correct solution.

A rapidly growing area of computer science is ubiquitous computing, in which computers automatically provide services for a user without that user's knowledge or awareness. For example, a computer located in your car contacts the garage door opener and tells it to open the garage door when the car is close to home. Read about this new model of computing and write a paper describing some of its applications. What are some of the possible problems that could result?

Another important new area of computer science is cloud computing, which relies on a computer network, along with networking software, to provide transparent access to remote data and applications. Read about this new model of data and software access and write a paper describing some of the important uses, as well as potential risks, of this new information structure.

A standard computer DVD holds approximately 5 billion characters. Estimate how many linear feet of shelf space would be required to house 5 billion characters encoded as printed bound books rather than as electronic media. Assume there are 5 characters per word, 300 words per page, and 300 pages per inch of shelf.