Material: Textbook (Goodrich/Tamassia), Sections 3.1, 3.2, 4.1, 4.3, 4.8, and Chapter 5.

HOMEWORK 2 PROBLEMS

1. Chapter 3 Exercises:
   • C-3.3 (binary search tree)
   • R-3.5 (AVL tree)
   • R-3.6 (AVL tree)

2. Chapter 4 Exercises:
   • R-4.9 (Sorting)

3. Chapter 5 Exercises:
   • R-5.4 (Recurrence equations)
   • C-5.3 (Greedy algorithm, making change)

4. Use a Dynamic Programming technique to solve the following design for reliability problem.

   Consider a system composed of n stages of devices connected in series. To increase the reliability of the design, each stage i contains m_i devices of type D_i connected in parallel. The internal switching circuitry is responsible for making exactly one device in each stage active at any time, switching between the devices of a given type in case of a failure. Let r_i be the reliability of the device D_i, i.e. probability that the device will function properly. If stage i contains m_i copies of device D_i, its reliability is determined by a function F(m_i) = 1-(1-r_i)^m_i. The reliability of the system is determined as a product of the reliabilities of the individual stages. Each device D_i has a cost c_i associated with it.

   Determine the number of devices m_i in each stage i to maximize the reliability of the system. This optimization is to be carried out under a cost constraint: the total cost of the devices must not exceed a given value C.

   • Formulate the problem as a dynamic programming problem. Write the objective function, the constraint set, and the recurrence equations. Demonstrate that the principle of optimality applies. (Hint: this problem is similar to a 0,1 knapsack problem.)
     
   • Solve the problem for n=3 stages with the following data:
     • Maximum allowed cost C=105.
     • Device costs: c₁=30, c₂=15, c₃=20.
     • Device reliabilities: r₁=0.9, r₂=0.8, r₃=0.5.

5. Programming Assignment

   Implement a computer program for solving a genaral knapsack problem, capable of handling either fractional or 0-1 knapsack problem. The input to your system is a file containing a total weight W of the knapsack, a set of N pairs (weight, benefit) , and a parameter specifying whether the program is fractional or 0-1 (this parameter can be entered interactively).
   Discuss the data structure used in your program. Perform experimental analysis to test the efficiency of your program.

   Publish your program on the web, showing the link to the executable code of the program and provide a short README file explaining how to run it. Clearly state the limitations, if any, in terms of the number of items you can handle (at least 20), the size of the sack, etc. Provide the link to your page on your solution sheet.

   A simple data string will be posted later on which you can test your algorithm.