Answer Happy

Question 1: Algorithm Usage [20 Points] Map each of the following problems to one of the problems studied in class, and then give the running time of the most efficient algorithm studied in class for solving the problem. Briefly explain your mapping and describe any adjustments or conversions that may be needed to solve the given problem. If the problem is an NP-complete or NP-hard problem for which we did not study a solution, do the mapping and then state that it is NP-Complete or NP-hard. (a) Suppose that you are developing a professional networking application (like Linkedin). There are N users of the application. Each user i has c(i) contacts. Any two users X and Y are either directly connected, indirectly connected or not connected at all. Given two users X and Y, which algorithm would you use to determine if X and Y are connected or not, and if they are connected, compute the minimum number of intermediate users U(X, Y) who connect them together. For example, if X and Y are contacts of each other, U(X, Y) is 0. If X has a contact A, and A has a contact B, who has Y as a contact, U(X, Y) is 2 and so on. (b) Suppose that you are the manager of a construction company, and you have projects offered to you by your clients. For each project i, you have an estimate of the amount of time T(i) that it will take your team to complete that project and you know the amount of money M(i) that the client will pay you for that project. The clients are flexible about the start time. So, you can start working on a project whenever you are ready, but due to limited resources, your team can only work on one project at a time Given a limited period of time L, which algorithm would you use to choose a set of projects to work on in order to get the maximum amount of money during that period? (c) Suppose that you have a studio to be used for shooting N different shows. Each show requires a different setting furniture, decoration, etc). If the settings of two shows have some similarities, the time needed to change the studio setting between the two shows will be relatively short, while if the settings are very different the time will be longer, and so on. For every pair (i, j) of shows, you have an estimate t(i, j) of the time needed to change the studio setting from the setting of show i to the setting of show j. You also have for each show i an estimate of the time needed to change the setting from the setting of i to the original setting of the studio and vice versa. Which algorithm would you use to determine the order for shooting all N shows to minimize the time needed for changing settings between consecutive shows and restoring the original setting after shooting the last show?

(d) Suppose that you would like to form a political party. There are people that you would like to recruit for the party (target people), and each of them lives in a different location. To maximize the chances of acceptance, you would like to have an invitation letter delivered in person to every target person. The letter may be delivered directly by you or by some other person who has already received his/her invitation letter. So, you may, for example, deliver the letter directly to five people and then distribute the rest of the letters on them and have them deliver them to other people. These five people will then deliver the letters directly or indirectly to other people, and so on. You know the address of every target person and have computed the travel cost Cli, j) for every pair (i, j) of people. Which algorithm would you use to determine how all the letters should be delivered (who delivers to whom) such that the total travel cost is minimized?