Extra Credit Assignment

Algorithms and Data Spring 2012
Karl Lieberherr

Due: March 28, 2012

Proposed by Ahmed Abdelmeged

This 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.

Q1) Algorithms in disguise

Suppose that you want to figure out the wages for the employees in a company with n employees. And the human resources department (HR) has provided you with the following requirements: Newly hired employees (set NEW) should get a minimum wage of at least $w. Besides NEW there is a disjoint set of OTHER employees. NEW union OTHER is the set of ALL employees. HR provides constraints of the form: the wage of employee_i in ALL must be at least $s_i_j more than the wage of employee_j in ALL. $s is a matrix of non-negative integers. HR will ensure that for each employee employee_i in set OTHER, the HR provides at least one constraint of the form: the wage of employee_i must be at least $s_i_j more than the wage of some employee_j in NEW.

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.

Q2) Incomplete Requirements

Consider the following problem statement: " Suppose that you want to anonymously report a crime and you have determined that email is not a suitable medium to do so. So, you decided to do it the old way; cutting words (not individual letters) from magazines and pasting them into your letter. Provide an algorithm that tells you whether or not it is possible to write your letter using your current set of magazines."

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.