Reference no: EM132516415

Data Structure & Algorithms Assignment -

You've been hired to work at the prestigious research lab of the company Gugle. However, soon after starting, you experience a serious accident where you and everyone else in the research lab has temporarily lost their memories of what they were working on and who they were working with.

1. You've been hired by Google to work for one of their research labs! You're super excited, but the day that you arrive, you are greeted with chaos. It seems that someone in the research lab was working on a device to enhance human memory, and accidentally erased everyone's memory of what project they were working on, and who they worked with. The information loss was so complete that somehow, all reference to the original organization of the lab was also deleted from every computer and every backup in Google. They're all smart people and could probably figure this out themselves, but because they're dealing with the emotional challenges of memory loss and want you to feel important, they decide to let you deal with it. Also, because there is the possibility for future memory loss, you need to not only come up with specific solutions (which may be forgotten), but algorithms for producing those solutions (which can be remembered and rerun if necessary.)

For each of the challenges below, give an algorithm to solve it with the lowest asymptotic complexity.

2. First, you have to rebuild a new management structure. A leadership hierarchy of some kind seems good, but you want to make sure that the teams and leaders are reasonable. Write an efficient algorithm that will organize the department (i.e. determine for each person, who is their boss), under the following conditions, or report that it is impossible.

Each person but one (the lab director) should have exactly one boss.

Each boss should have at most k people reporting to them.

You have the seniority records for each member of the team, and need to make sure that each boss has at least twice as many years of experience as each person reporting to them.

2. First, you have to rebuild a new management structure. A leadership hierarchy of some kind seems good, but you want to make sure that the teams and leaders are reasonable. Write an efficient algorithm that will organize the department (i.e. determine for each person, who is their boss), under the following conditions, or report that it is impossible.

Each person but one (the lab director) should have exactly one boss.

Each boss should have at most k people reporting to them.

You have the seniority records for each member of the team, and need to make sure that each boss has at least twice as many years of experience as each person reporting to them.

Some people strongly dislike the idea of using seniority alone as the metric for how the teams should be organized. While they will accept the idea of the most senior member being the director, they argue that the rest of the organization should go based on effective communication. When the director sets a goal, she has to tell her direct reports, who have to tell their direct reports, and so on. They did a little testing, and for every pair of people in the lab, they figured out how well that pair could communicate in general, with a real-valued score from 0 to I based on what proportion of information was successfully communicated.

Give an efficient algorithm that will construct a hierarchical organization, starting with a given director, such that the percentage of information accurately communicated to each member of the lab by passing messages from the director through the chain of management to any other member. The information received is determined by the product of the communication scores between each pair of individuals in the chain, and the communication scores between every pair of individuals is available to choose from in forming the hierarchical structure.

3. The director of research lab now needs to work with each group to try and find a good research project to work on. She needs to make the rounds and meet with each group to discuss what that group is going to do. To organize this, the director asks each group propose a specific meeting time (start time and length), and rank how important it is to meet with her as soon as possible. For the day, she has to pick a schedule of meetings that maximizes the total number of urgency-points she gets through.

Give an efficient algorithm to plan the director's day, or prove that the problem is NP-complete. Your inputs are, for all groups, a proposed meeting slot (start time and length, both in increments of 30 minutes), and a score for how important the meeting is. Your output must be a valid schedule for that day which maximized the sum of the importance scores satisfied with the chosen meetings.

4. Well, this is the problem with letting everybody decide their own project. It turns out people found out about an experimental quantum computer in the basement, and at least half of the groups want to do quantum computing research on it. The director wisely decides that different groups should actually be researching different things, and that they aren't going to buy extras of the expensive equipment they already have. With some discussions, inventories of equipment, and sharing of potential research ideas, each group comes up with a list of research projects they would be willing to pursue, and for each one, a list of equipment that they will need. Using a machine-learning screening and classification on the proposals, the director weeds out the bad projects, and separates those remaining into categories, with the goal that no more than one project in each category should be pursued at once.

Give an efficient algorithm to select which projects should be selected for research, or prove that the problem is NP-complete. Your inputs are the proposals (which group is making the proposal, what category of project their proposal is, and the list of resources needed to complete the research), and you must select a set of projects such that each group has exactly one selected project, no two projects from the same category are selected, and no limited resource is assigned to more than one of the projects selected.