Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Exercises

  1. Consider the greedy strategy for counting out change given in Section gif. Let tex2html_wrap_inline67428 be the set of available denominations. For example, the set tex2html_wrap_inline68600 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 gif.
    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 tex2html_wrap_inline67468 tex2html_wrap_inline57649
    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 gif. 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 gif, but this time consider what happens if we replace the queue with a LIFO stack.
  6. Repeat Exercises gif and gif, but this time consider a branch-and-bound breadth-first solver.
  7.   (This question should be attempted after reading Chapter gif). 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 gif 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 gif.
    3. What problem arises if we use the BreadthFirstSolver given in Program gif 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 gif.
  8.   Devise a backtracking algorithm to solve the N-queens problem : Given an tex2html_wrap_inline68614 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, tex2html_wrap_inline63509, tex2html_wrap_inline63511, ..., tex2html_wrap_inline68624, at depths tex2html_wrap_inline65671, tex2html_wrap_inline65673, ..., tex2html_wrap_inline68630, respectively. Suppose the tree will be subjected to a large number of Find operations. Let tex2html_wrap_inline57649 be the probability that we access key tex2html_wrap_inline63523. 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

    displaymath68590

    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 tex2html_wrap_inline67912 be the cost of the optimal binary search tree that contains the set of keys tex2html_wrap_inline68638 where tex2html_wrap_inline68640. Show that

    displaymath68591

  10. Consider the typesetting problem discussed in Section gif. 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. For example, given a polynomial such as tex2html_wrap_inline68648, and an interval [u,v] such that p(u) and p(v) have opposite signs, find the value r, tex2html_wrap_inline68658, such that p(r)=0.
  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

    displaymath68592

    where tex2html_wrap_inline68444 is the mean and tex2html_wrap_inline68664 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 tex2html_wrap_inline68666 given by the probability density function

    displaymath68593

    where tex2html_wrap_inline68668 is the mean of the distribution.

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

  15. Do Exercise gif.
next up previous contents index

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