Problems

[Page 525 (continued)]

15.1	What are each of the following: Interpreter Compiler Machine language Java Virtual Machine (JVM) RAM Cache Class P problems Class NP problems
	[Page 526]
15.2	Find animations of different sorting algorithms on the Web.
15.3	Look up how to do a bubble sort. Write a method to do a bubble sort of an array of names.
15.4	Look up how to do an insertion sort. Write a method to do a insertion sort of an array of names.
15.5	Look up how to do quicksort. Write a method to do quicksort of an array of names.
15.6	How many times will the following code print out the message? String message = "I will be good!"; for (int i = 0; i < 5; i++) { for (int j = 0; j < 10; j++) { System.out.println(message); } }
15.7	How many times will the following code print out the message? String message = "I will be good!"; for (int i = 1; i <= 5; i++) { for (int j = 10; j > 0; j--) { System.out.println(message); } }
15.8	How many times will the following code print out the message? String message = "I will be good!"; for (int i = 1; i <= 5; i++) { for (int j = 10; j > 0; j--) { for (int k = 0; k < 3; k++) { System.out.println(message); } } }
15.9	What is the Big Oh of the method clearBlue?
15.10	What is the Big Oh of the method lighten?
15.11	You've now seen some examples of Class P problems (e.g., sorting and searching), intractable problems (optimization of the song elements), and Class NP problems (e.g., Traveling Salesman problem). Search the Web and find at least one more example of each class of problem.
15.12	Try something that takes a while in Java (e.g., chromakey on a large image) so that you can time it on a stopwatch. Now time the same task on several different computers with different amounts of memory and different clock rates (and different amounts of cache, if you can). See what a difference the different factors have in terms of the time it takes to complete the task.
15.13	Trace through the linear and binary search algorithms with a list of 10 items that you make up. Count exactly the number of times through the loop that are executed if the search string is (a) the first item in the list, (b) the last item in the list, (c) the middle item in the list, and (d) not in the list. Are there some situations where linear search is actually faster than binary search? [Page 527]
15.14	Don't actually trace it out, but imagine that the list has 1,000,000,000 items in it. Can you use your results from the last exercise to figure out the same loop counts for (a) through (d) for both linear and binary searches if you have a one billion item list?
15.15	Now assume that you're running a 1-gigahertz (roughly 1 billion instructions per second) processor, and you can run the whole loop, for either binary or linear search, in five instructions. Exactly how long, in seconds, are each of the results from the last exercise?
15.16	Recall that a linear search is O(n) and a binary search is O(logn). Let's imagine that we have two other search algorithms. The Bad Search is O(n2)on average, it takes n2 times through the loop to find the element. The Awful Search is O(n!). Imagine that we have a 1,000-item list, and the same 1-gHz processor as before, and the loop takes five instructions to run. How long will it take, in seconds, for Bad Search and Awful Search algorithms to complete an average search? Notice that this is a one thousand item list, not a 1-billion item list in this example.
15.17	Turing is known for another important finding in computer science, besides the proof that the Halting Problem is unsolvable. He gave us our test for whether a computer has actually achieved intelligence. Look up the "Turing Test" on the Web and see if you agree that that test would prove intelligence.
15.18	Define a MoreMath class that has a factorial method that takes an integer and returns the factorial of that integer. Make this method a class method by using the keyword static in the method declaration after the public keyword.
15.19	Create a new linearFind method in the Searcher class that works on any object of the type Comparable and takes a List of Comparable objects.
15.20	Create a new binaryFind method in the Searcher class that works on any object of the type Comparable and takes a List of Comparable objects.
15.21	If there are real problems that have such awful algorithms, and people really need solutions within their lifetimes, how do they solve those problems? Sometimes they use heuristicsrules that don't lead to a perfect solution, but they lead to a good enough solution. Look up "heuristics" on the Web. Find an example of a heuristic used in chess playing programs.
15.22	Another way around awfully hard algorithms is to use satisficing algorithms. There are algorithms that solve the Traveling Salesman problem (i.e., find a route to all the cities) that run in reasonable timethey just don't guarantee the optimal (best possible) solution. Find an algorithm on the Web that does solve the Traveling Salesman problem in reasonable time, but isn't optimal.