Analysis of Algorithms : An Active Learning Approach

258 OTHER ALGORITHMIC TECHNIQUES

9.4 Programming Exercises

1. Write a program for the traveling salesperson approximation algorithm.
   Run your program for a set of 10 cities by randomly placing distance values
   between 1 and 45 into the adjacency matrix. Print out the adjacency matrix
   and the path found. Check them to see if the result is optimal.


2. Write a program for the bin packing approximations. Your program should
   implement the four methods mentioned in the text and exercises: first fit,
   best fit, next fit, and worst fit. Generate a random set of objects and pass the
   same set into each of the four methods to see how many bins each would
   use. Write a report on your results. You should test these methods with the
   number of objects being 50, 100, 200, and 500. To get more accurate
   results, you should generate and test multiple sets of sizes for each of these
   four cases.


3. Write a program to do Monte Carlo integration of the function x^3 in the
   range between 0 and 1. Because we know that the answer is 0.25, you
   should write your program to test how many darts need to be thrown for
   the answer to be within various levels of accuracy. You should run this to test
   the number of darts needed to be within ±0.0001, ±0.000001, and
   ±0.00000001 of the correct answer.


4. Write a program to use random numbers to calculate the value of  as
   described in the text. How many darts are needed for the fifth digit after the
   decimal point to be correct? How many darts are needed for the seventh
   and tenth digits after the decimal point to be correct?


5. Create a program that will sort a list using a standard Quicksort and a
   Quicksort with a Sherwood-based PivotList. Generate a number of
   random lists of 500 values and count the number of comparisons done by
   each of these sorts. Report the maximum, minimum, and average number
   of comparisons done. Write a report describing your findings. (Additional
   details on how to do this are given in the programming exercises in Chapter
   3.)


6. Write a Sherwood-based binary search. Create an ordered list with the
   numbers from 1 to 10,000. Generate a series of values between 1 and
   10,000 and pass them to both the standard and Sherwood binary searches.
   Write a report comparing the maximum, minimum, and average number of
   comparisons done by these two methods. The more values you test, the bet-
   ter your results will be.