Given a set of jobs {J1, ... , Jn}, each job Ji = < ti, wi > has a required processing time ti and a weight wi. Design an efficient algorithm (pseudo code) to minimize the weighted sum of overall completion times ∑ni=1wiCi, where Ci is the completion time of job i. What is the time complexity of your algorithm? Note: You first need to briefly explain your ideas to solve the problem, e.g. what data structures are used, how the intermediate results are saved, which sorting strategy is used, and why the final results are correct;

Given a set of jobs {J1, ... , Jn}, each job Ji = < ti, wi > has a required processing time ti and a weight wi. Design an efficient algorithm (pseudo code) to minimize the weighted sum of overall completion times ∑ni=1wiCi, where Ci is the completion time of job i. What is the time complexity of your algorithm? Note: You first need to briefly explain your ideas to solve the problem, e.g. what data structures are used, how the intermediate results are saved, which sorting strategy is used, and why the final results are correct;

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter15: Recursion

Section: Chapter Questions

Problem 18SA

See similar textbooks

Similar questions

Consider array A of n numbers. We want to design a dynamic programming algorithm to find the maximum sum of consecutive numbers with at least one number. Clearly, if all numbers are positive, the maximum will be the sum of all the numbers. On the other hand, if all of them are negative, the maximum will be the largest negative number. The complexity of your dynamic programming algorithm must be O(n2). However, the running time of the most efficient algorithm is O(n). Design the most efficient algorithm you can and answer the following questions based on it. To get the full points you should design the O(n) algorithm. However, if you cannot do that, still answer the following questions based on your algorithm and you will get partial credit. Write the recursion that computes the optimal solution recursively based on the solu- (a) tion(s) to subproblem(s). Briefly explain how it computes the solution. Do not forget the base case(s) of your recursion.
Let's consider the bar cutting problem: Suppose we have a bar of length n. p is the selling price of a bar of length i; Let's assume that (i=1, 2, ..., n). Our goal is to split the bar into parts of integer length to get maximum profit. (a) Design a dynamic programming algorithm for this problem. Instead of pseudocode, a well-explained explanation is preferred. Also mention the time and place complexity of your algorithm. (Hint: Define the function F(n) as the maximum profit that can be obtained for a stick of length n and construct an iterative relation.) (b) Apply the dynamic programming algorithm you designed for the following example: You have a stick of length 6. Selling prices of parts: pi=1, P2=6, p3=7, p=11, p=14, po=15.
6] An algorithm has a count of basic operations C(n) = 25-n²-log(n). For a problem size n implementing the algorithm was timed and found to run in 5 minutes. (a) Your boss is asking to run the program for a problem size n = 100,000 on the same m the time it would take. Is it feasible? • Hint: We do not need Cop because it will simplify in the ratio anyway! Solution:
Given a positive integer number n (i.e., n>0), we can use the following algorithm to find the nth fibonacci number:fibonacci(n){If n=1, return 1;If n=2, return 1;return fibonacci(n-1) + fibonacci(n-2);}Given that there exists overlaps in the sub-problems of the problem, write a Dynamic programmingalgorithm to overcome the overlapping. Implement both algorithms in C++. You need to submit source code. Give the number of additions needed for each algorithm when n=10, 15, 20, 25, 30, 35, 40.
Consider the following part of a function (assume n>=1 and m>=1 and n and m are inputs to the function) for (i = 1 to n) for (j - 1 to m) for (k = 1 through 1000) { Task A Task B If Task A requires t time units and Task B requires s time units, then the algorithm requires _in the worst case, assuming that t and s are constants. time units to be executed, and therefore it is 1000 * t* s* n units, O(1000 * t* s ) 1000 + n + m +t + s units, O(1000 + n+ m +t+ s) n*m* t*s units, O(n*m*t*s) 1000*n*m* (t +s) units, O(n*m) O (1000 +m + n) * (t +s) units, O(m + n) O m'n units, O(mn)
A computer science student designed two candidate algorithms for a problem while working on his part-time job The time complexity of these two algorithms are T,(n) = 3 n logn and T2(n) = n6/5 a) Which algorithm is better? Why? b) If we run both algorithms at the same time with an input size of 105, which algorithm produces results faster than the other one? Why?
Design an algorithm to read the bus rapid transit system routes list and print the number of tickets we need to purchase if we want to visit all places minimal twice. The complexity of the algorithm must be O(V+E). V is the number of places. E-> is the number of transits. PS: Use Tarjan’s or Kosaraju’s strongly connected component algorithm.
Let us assume that we have two algorithms A and B. Algorithm A has run time given by (10n)2 and algorithm B has run time given by (Sin2n + Cos2n +1)n where n is the input size. Also assume that both algorithms are run on the same computer. Find the smallest value of n for which the runtime of algorithm A is less than the run time of algorithm B.
Please assist with this question
The diagram below shows roads connecting towns near to Rochdale. The numbers on each arc represent the time, in minutes, required to travel along each road. Peter is delivering books from his base at Rochdale to Stockport. Use Dijkstra's and Bellman-Ford's algorithm to find the minimum time for Peter's journey. Show every iteration for D and P. Which algorithm is more efficient in this example? Rochdale 15 10 Bury 25 8 14, Oldham 17 23 14 Trafford Manchester 17 20 Ashton 13 Stockport
A computer science student designed two candidate algorithms for a problem while working on his part-time job The time complexity of these two algorithms are ?1(?) = 3 ? log ? and ?2(?) = ? 6/5a) Which algorithm is better? Why?b) If we run both algorithms at the same time with an input size of 105 which algorithm produces results faster than the other one? Why?
1s=10^6 μs 1m = 60 x 1s log n Vn nlogn n² 2. For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds. n³ 2n n! 1hr = 60 x 1m 1 day = 24 x 1hr 1 second 1 minute 1 hour 1 month = 28 x 1 day 1 day 1 month 1 year = 12 x 1 month 1 year 1 century 100 x 1 year 1 century