Suppose we assign n persons to n jobs. Let,C base ij, be the cost of assigning the i^th person to the j^th job. a) Write a greedy algorithm that finds an assignment that minimizes the total cost of assigning all n persons to all n jobs. b) Test your algorithm based on the following example and discuss if your algorithm provides an optimal solution to the problem

Suppose we assign n persons to n jobs. Let,C base ij, be the cost of assigning the i^th person to the j^th job. a) Write a greedy algorithm that finds an assignment that minimizes the total cost of assigning all n persons to all n jobs. b) Test your algorithm based on the following example and discuss if your algorithm provides an optimal solution to the problem

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Write the formula for calculating the optimal cut of the text t of length n, where we have m cut points given in the field R.TIP: In the case of the first question, R = [3, 7, 17].C) Record the algorithm for calculating the optimal cut and estimate the time and complexity.
Assuming you possess a total of 'm' dollars, and are accompanied by a group of 'n' friends. For every friend i, where i ranges from 1 to n, the price P[i] of the candy that would bring contentment to the respective friend is known. The objective is to devise a method for allocating a sum of m dollars in a manner that maximizes the number of contented friends. Propose an O(n log n) time greedy algorithm for determining the monetary allocation to be assigned to each friend.
Given an array of intervals I[1, . . . , n] where I[i] = [si, fi], find the minimumnumber of intervals you need to remove to make the rest of the intervals non-overlapping. Precisely define the subproblem.Provide the recurrence equation.Describe the algorithm in pseudocode to compute the optimal value.Describe the algorithm in pseudocode to print out an optimal solution.
Consider the following problem. The input consists of n skiers with heights p1, ··· , pn , and n skies with heights s1, ··· , sn. The problem is to assign each skier a ski to to minimize the average difference between the height of a skier and his/her assigned ski. That is, if the ith skier is given the Alpha(i)th ski, then you want to minimize: 1/ffln ∑i=1 to n |pi- s↵(i)| (a) Consider the following greedy algorithm. Find the skier and ski whose height di↵erence is minimized. Assign this skier this ski. Repeat the process until every skier has a ski. Prove of disprove that this algorithm is correct. (b) Consider the following greedy algorithm. Give the shortest skier the shortest ski, give the second shortest skier the second shortest ski, give the third shortest skier the third shortest ski, etc.Prove of disprove that this algorithm is correct. HINT: One of the above greedy algorithms is correct and one is incorrect for the other. The proof of correctness must be done…
he heuristic path algorithm is a best-first search in which the objective function is f(n) = (4 −w)g(n) + wh(n). For what values of w is this algorithm guaranteed to be optimal? What kind of search does this perform when w = 0? When w = 1? When w = 4?
Given an array of integers, find the longest non-decreasing subsequences (the subsequence does not need to be consecutive). For example, A = [8,5,2,10,3,6,9,7] contains the longest subsequences [2,3,6,9] and [2,3,6,7].a. Formulate the recursive relation of the optimal solution (do not miss the base case); b. Design a bottom-up (iterative) algorithm to calculate the length of the longest non-decreasing subsequences (pseudo code); c. Analyze the complexity of your algorithm.
Assume there are n courses offered by the university, where each course has one or no prerequisites.If course j is the prerequisite for course i, then we are only allowed to take course i after course j. And after taking each course i, we can get a reward r_i. Given the reward and prerequisite for each course, design analgorithm to find the maximum total reward we can get by taking m courses. The time complexity shouldbe O(nm^2).
Let's say there are n villages, {X1, . . . , Xn} on the country-road and we aim to build K < n restaurants to cover them. Each restaurant has to be built in a village, and we hope to minimize the average distance from each village to the closest restaurant. Please give an algorithm to compute the optimal way to place these K restaurants. The algorithm should run in O(k * n^2) time. Solutions with slightly higher time complexity also accepted.
Assume there are n courses offered by the university, where each course has one or no prerequisites.If course j is the prerequisite for course i, then we are only allowed to take course i after course j. And after taking each course i, we can get a reward r_i. Given the reward and prerequisite for each course, design analgorithm to find the maximum total reward we can get by taking m courses. The time complexity shouldbe O(nm^2). Please only answer if you have the algorithm
The classic example of following a greedy algorithm is making change. Let’ssay you buy some items at the store and the change from your purchase is63 cents. How does the clerk determine the change to give you? If the clerkfollows a greedy algorithm, he or she gives you two quarters, a dime, andthree pennies. That is the smallest number of coins that will equal 63 cents(given that we don’t allow fifty-cent pieces).It has been proven that an optimal solution for coin changing can alwaysbe found using the current American denominations of coins. However, if weintroduce some other denomination to the mix, the greedy algorithm doesn’tproduce an optimal solution.Write a program that uses a greedy algorithm to make change (this codeassumes change of less than one dollar):
In this problem we have n jobs j1, j2, ..., jn, each has an associated deadline d1, d2, ..., dn and profit p1, p2, ..., pn. Profit will only be awarded or earned if the job is completed before the deadline. We assume that each job takes 1 unit of time to complete. The objective is to earn maximum profit when only one job can be scheduled or processed at any given time.Provide the pseudocode of an algorithm to find the sequence of jobs to do with the maximum total profit. Also describe the main idea of your algorithm using plain language.[Hint: You can select the jobs in a greedy way. You can use the following example to help your analysis.] Job J1 J2 J3 J4 J5 Deadline 2 1 3 2 1 Profit 60 100 20 40 20 The best job sequence would be J2 →J1 →J3.
Consider the following version of Knapsack. Given are two weight limits Wi and W2, where WW2. Given are also n items (wi, ci), (W2, C2)..... (Wn, Cn), where w, is the weight and c the cost of the i-th item. We want to find a subset of these items of the highest cost, where the subset weights at least W₁ and at most W2. Give an O(nW₂) algorithm for this problem. (Recall that the cost (respectively weight) of a subset is the sum of the costs (respectively weights) of the items in the subset.)