Part 2: Solving the "Please take me out of here!" with a Greedy Approach

Back to labs page.

As you know from the course, a greedy algorithm is any algorithm that constructs the optimal solution of the problem by performing a local, efficient optimal choice at each step. The attractive features of greedy algorithms is they are usually easy to program, and very efficient in their computational complexity.

A number of problems can be solved by greedy algorithms: you might want to have a look, for example, at the MST problem or the SSSP problem.

Unfortunately not all the problems can be solved efficiently with this approach, and "Please take me out of here!" is, of course, one of these problems. This means that, regardless of which greedy strategy one can imagine, there will always be a class of instances for which the proposed strategy will produce a sub-optimal result.

In this assignment we want you to experiment how easy it is to imagine a greedy strategy for a problem, and how tricky it is to ensure the designed strategies guarantees optimality in all problem instances.

To achieve this result, you need to complete the following tasks:

• define two greedy strategies for "Please take me out of here!" (show that they are indeed greedy strategies).
• for each of these two greedy strategies,
  • define a successful instance (an instance in which the optimal solution is found when the strategy is applied). The instance should have at least 4 nodes.
  • define a failing instances (an instance in which the optimal solution is NOT found when the strategy is applied). The instance should have at least 4 nodes.

You then need to provide us documentation of your experiments. This documentations consists of

• a file containing a program, and
• a file containing your report.

The requirements on these two files are given below.

PROGRAM REQUIREMENTS

• INPUT
  Your program must be able to read input data from files. The two old instances from Part 1 each represent an example of a valid file:
  • instance 1
  • instance 2
Please note, again, that the file structure is the same you used in the previous submisson.
• INTERNALS
  Your program must:
  • read the input file;
  • execute the first strategy, and print its result;
  • execute the second strategy, and print the result;
  While you are testing your code, we recommend you run your bruteforce solution (if you made one) from lab 1 on the input file, to see if your greedy strategies
  • produce optimal results in their successful instance;
  • produce suboptimal results in their failing instance.
  As usual we recommend you to reduce as widely as possible complex/excessive class hierarchies, awkward programming style and all other distractions that can hide your ideas and result in a negative feedback.
• OUTPUT
  Your program must output both the value and the composition (i.e. the set of edges) of the optimal path for both the two strategies. Optionally, you can include the optimal path (produced using your brute force strategy from Lab 1). This means all the runs of the program will produce two (optionally, three) results, each of which must be formatted the same way as the output in lab 1.

REPORT REQUIREMENTS

• First page: put there your group number on the fire system, your names, personal numbers and email addresses.
• Chapter 1: how your strategies work
  You will have two sections here, one for each strategy you present.
  Use words, high level pseudocode and illustrations. The important thing is to reveal the underlying idea and as a help to understand the pseudocode in the next step. A "dry swim" of some steps is very good here.
• Chapter 2: greedy certification
  While the concept "greedy algorithm" is not formally defined (thus you cannot formally prove that an algorithm is greedy), one can easily argue why an algorithm is greedy. As the course book says, [KT, p115], "An algorithm is greedy if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion." This means a necessary condition a greedy solution must satisfy is:
  • the strategy which is used at each step to extend the solution is easy to identify in the algorithm
  • the cost for running the strategy is order of some small polynomial
  For each strategy you described in Chapter1, you will therefore:
  • write the pseudocode in order to make the strategy you apply completely visible
  • carefully evaluate the complexity in terms of the strategy cost, and number of times the strategy will be called
  We remind you that:
  • pseudocode means a mixture of programming language, mathematics, english and other suitable notation. You can use abstract data types (for instance lists...) and sentences like "for every edge e in E loop"
  • It is not enough to say how costly your strategies are supposed to be, you must motivate their complexity by referring to the pseudocode you wrote to implement them.
• Chapter 3: successful and failing instances
  Here you will list four instances in total: two will be successful (one for each strategy) and two will be failing (one for each strategy). The idea is we will copypaste them in a text file when checking your submisson, so find a reasonable way of showing them.
  PLEASE NOTE it might be (much) more convenient to keep these instances in separated text files instead. For this part you are therefore allowed to submit, in conjunction with the file containing the program and the file containing the report, exactly four text files containing the four required instances. The files must be named
  • 1accept.txt --- accepting instance for first greedy strategy
  • 1fail.txt --- failing instance for first greedy strategy
  • 2accept.txt --- accepting instance for second greedy strategy
  • 2fail.txt --- failing instance for second greedy strategy
  PLEASE NOTE THIS IS THE ONLY ADMITTED EXCEPTION, SUBMITTING ANY OTHER FILE WILL IMPLY A STRAIGHT REJECT
• Appendix: references to all sources you used, if any. And an example about how to compile and run your program

Submission

Deadline for this assignment is 23 Semptember, and the deadline is strict.