Exercises

1. Consider the greedy strategy for counting out change given in Section . Let be the set of available denominations. E.g., the set represents the denominations of the commonly circulated Canadian coins. What condition(s) must the set of denominations satisfy to ensure the greedy algorithm always finds an optimal solution?
2. Devise a greedy algorithm to solve optimally the scales balancing problem described in Section .
   1. Does your algorithm always find the optimal solution?
   2. What is the running time of your algorithm?
3. Consider the following 0/1-knapsack problem:

   i
   1	10	10
   2	6	6
   3	3	4
   4	8	9
   5	1	3
   C=18

   1. Solve the problem using the greedy by profit, greedy by weight and greedy by profit density strategies.
   2. What is the optimal solution?
4.   Consider the breadth-first solver shown in Program . Suppose we replace the queue (line 3) with a priority queue.
   1. How should the solutions in the priority queue be prioritized?
   2. What possible benefit might there be from using a priority queue rather than a FIFO queue?
5.   Repeat Exercise , but this time consider what happens if we replace the queue with a LIFO stack.
6. Repeat Exercises  and , but this time consider a branch-and-bound breadth-first solver.
7.   (This question should be attempted after reading Chapter ). For some problems the solution space is more naturally a graph rather than a tree.
   1. What problem arises if we use the DepthFirstSolver given in Program  to explore a search space that is not a tree.
   2. Modify the DepthFirstSolver so that it explores a solution space that is not a tree. Hint: See Program .
   3. What problem arises if we use the BreadthFirstSolver given in Program  to explore a search space that is not a tree.
   4. Modify the BreadthFirstSolver so that it explores a solution space that is not a tree. Hint: See Program .
8.   Devise a backtracking algorithm to solve the N-queens problem : Given an chess board, find a way to place N queens on the board in such a way that no queen can take another.
9. Consider a binary search tree that contains n keys, , , ..., , at depths , , ..., , respectively. Suppose the tree will be subjected to a large number of Find operations. Let be the probability that we access key . Suppose we know a priori all the access probabilities. Then we can say that the optimal binary search tree  is the tree which minimizes the quantity

   

   1. Devise a dynamic programming algorithm that, given the access probabilities, determines the optimal binary search tree.
   2. What is the running time of your algorithm?

   Hint: Let be the cost of the optimal binary search tree that contains the set of keys where . Show that

   

10. Consider the typesetting problem discussed in Section . The objective is to determine how to break a given sequence of words into lines of text of the appropriate size. This was done either by stretching or compressing the space between the words. Explain why the greedy strategy always finds the optimal solution if we stretch but do not compress the space between words.
11. Consider two complex numbers, a+bi and c+di. Show that we can compute the product (ac-bd)+(ad+bc)i with only three multiplications.
12. Devise a divide-and-conquer strategy to find the root of a polynomial. E.g., given a polynomial such as , and an interval [u,v], such that such that , and , , find r.
13. Devise an algorithm to compute a normally distributed random variable. A normal distribution is complete defined by its mean and standard deviation. The probability density function for a normal distribution is

    

    where is the mean and is the standard deviation of the distribution. Hint: Consider the central limit theorem .

14. Devise an algorithm to compute a geometrically distributed random variable. A geometrically distributed random variable is an integer in the interval given by the probability density function

    

    where is the mean of the distribution.

    Hint: Use the fact , where Z is an exponentially distributed random variable with mean .

15. Do Exercise .

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.