CSE222 -  Programming Assignment 5 - Solved

1           Introduction
In this assignment, you’re going to write a C program that uses recursion and dynamic programming to solve the egg drop analysis problem (EDAP). EDAP is a classic problem with a clever recursive solution whose e ective implementation requires dynamic programming.

2           Problem Statement
The Question

Given a number of identical eggs and a building with a number of oors, one wishes to answer the question: what is the highest oor from which an egg can be dropped without it breaking.

Approaches

There are many ways to do this:

•    given as many eggs as there are oors, one can simply drop an egg from each oor to discover the answer;

•    given only a single egg, one needs to start from                oor 1 and work towards higher        oors, since, once an egg is broken, it cannot be re-used

•    The cases in-between are more interesting. Given two eggs, one can try the middle oor. If the egg survives, you only need to investigate the higher oors (and you still have 2 eggs); whereas if the egg breaks, you need to investigate the lower oors (and now only have one egg left).

The goal of EDAP is to determine worst case how many experiments must be run to answer The Question.

Note that you are not coming up with the algorithm for running these experiments (since the steps of the experiment depend on whether or not the egg survives any given drop).

3           Algorithm
You are to design and implement a function int egg(int floors, int eggs);

which will return the smallest number of experiments guaranteed to be su cient to answer The Question for the given number of oors and eggs. One may de ne egg() recursively as follows:



0

1

egg(floors,eggs) = floors

min1 ≤(1+f ≤ floorsmax(egg(f −1,eggs −1),egg(floors − f,eggs))
floors ≤ 0 floors = 1 eggs = 1

otherwise
This has the familiar repeated-subcase structure of other algorithms we’ve been discussing (knapsack, rod cutting, etc.) and, similar to those, the performance is abysmal if coded as shown above. Therefore, you must employ dynamic programming to speed up the calculation of the egg function. You can do this by using a 500x500 array of ints:

int save[500][500]={0}; where save[f][e] stores the value of eggs(f,e).

See your notes from lecture for various simplifying assumptions and other relevant details.

4           Main Program
Your submission should include a main le named eggtest.c and a make le for creating an executable le named eggtest eggtest should simply:

1.    ask the user for the number   oors;

2.    ask for the number of eggs; and then

3.    print the minimum guaranteed-su        cient trials required, and exit.

Please don’t print anything else, ask for any other output, or perform any other actions. See /tmp/eggtest on the server for a sample executable.