Algorithms and Data Spring 2012 Karl Lieberherr Due: March 28, 2012 Proposed by Ahmed AbdelmegedThis assignment focuses on two problems that you would need to deal with when developing algorithms for solving problems in the real world. We call these two problems: algorithms in disguise and incomplete requirements.
Provide an algorithm that determines (if possible) wages for employees such that the sum of all wages is minimized.
Analyze the running time of your algorithm and justify why your algorithm is correct.
As stated above, the algorithm can be complex to develop and computationally intensive. Additional restrictions to the problem (that might have been too obvious and hence overlooked in the problem statement) can greatly simplify the algorithm as well as make it less computationally intensive. Two examples of these restrictions are given: 1) You are going to use a whole word from the magazine as a whole word in the letter. 2) There are no repeated words in the letter.
a. Provide an algorithm for solving the problem under both restrictions. Analyze the running-time of your algorithm. Note that under these two restrictions the problem is a disguised form for the problem of checking whether a set S is a subset of another set T. b. Provide an algorithm for solving the problem under the first restriction. Analyze the running-time of your algorithm. c. Provide an algorithm for solving the problem without restriction. Analyze the running-time of your algorithm. d. Assume that after running the algorithm you developed in (b) you either (I) decided to add a new word to your letter, or (II) Mistakenly ruined a word from your magazines. Provide two derived versions of these algorithms that can support you in figuring out whether it is still possible to write your letter in both cases (I), (II). The challenge is to figure out which auxiliary information you should produce during an initial run of your algorithm and how to use it in both (I), (II).
With this extra-credit homework you improve your midterm grade or your final exam score. You can do a part of the homework or all of it. Because those points are used to improve exam scores, you need to do the work individually, outside your team.
What to turn in: Algorithms and their analysis. Implementation is not required but it will give you extra points.