ZuoTi.Pro
Question

For each 1 ≤ ? ≤ ? job ?? is given by two numbers ?? and...

For each 1 ≤ ? ≤ ? job ?? is given by two numbers ?? and ??, where ?? is the deadline and ?? is the penalty. The length of each job is equal to 1 minute and once the job starts it cannot be stopped until completed. We want to schedule all jobs, but only one job can run at any given time. If job i does not complete on or before its deadline, we will pay its penalty ??. Design a greedy algorithm to find a schedule such that all jobs are completed and the sum of all penalties is minimized. What is the running time of your algorithm?

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

0 0
Add a comment
Know the answer?
Add Answer to:
For each 1 ≤ ? ≤ ? job ?? is given by two numbers ?? and...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Suppose you have a set of classes to schedule among a large number of lecture halls,...

    Suppose you have a set of classes to schedule among a large number of lecture halls, where any class can class place in any lecture hall. Each class cj has a start time sj and finish time fj. We wish to schedule all classes using as few lecture halls as possible. Verbally describe an efficient greedy algorithm to determine which class should use which lecture hall at any given time. What is the running time of your algorithm?

  • You're in charge of running a scientific program (job) that simulates a physical system for as ma...

    You're in charge of running a scientific program (job) that simulates a physical system for as many discrete steps as you can. The lab you're working in has two large supercomputers, which we'll call A and B, which are capable of processing this job. However, you're not one of the high-priority users of these supercomputers, so at any given point in time, you're only able to use as many spare cycles as these machines have available. Here's the problem you...

  • You need to visit four cities one time each and return home (H) to start your...

    You need to visit four cities one time each and return home (H) to start your political campaign. The travel costs ($) between all locations are given the table below. H А B с D H 450 510 820 350 A 450 600 550 490 B 510 600 720 680 с 820 550 720 650 D 350 490 680 650 a) Sketch a weighted graph for this problem. b) Starting at B, the greedy algorithm gives BHDACB. Find the total...

  • You are given a set of integer numbers A = {a1, a2, ..., an}, where 1...

    You are given a set of integer numbers A = {a1, a2, ..., an}, where 1 ≤ ai ≤ m for all 1 ≤ i ≤ n and for a given positive integer m. Give an algorithm which determines whether you can represent a given positive integer k ≤ nm as a sum of some numbers from A, if each number from A can be used at most once. Your algorithm must have O(nk) time complexity.

  • Suppose you’ve taken a part-time job where you drive sales executives of a company to client site...

    Suppose you’ve taken a part-time job where you drive sales executives of a company to client sites. Each trip starts and ends at the company’s headquarters. A sales executive specifies a trip by its start and finish times. A trip is specified by a start time s and a finish time f. The start time is when you leave the headquarters for a client site; the finish time is when you get back to the headquarters from the client’s site....

  • Problem 1: Given a graph G (V,E) a subset U S V of nodes is called...

    Problem 1: Given a graph G (V,E) a subset U S V of nodes is called a node cover if each edge in E is adjacent to at least one node in U. Given a graph, we do not know how to find the minimum node cover in an efficient manner. But if we restriet G to be a tree, then it is possible. Give a greedy algorithm that finds the minimum node cover for a tree. Analyze its correctness...

  • Problem 1 (5+15 points) Consider the set P of n points and suppose we are given...

    Problem 1 (5+15 points) Consider the set P of n points and suppose we are given the points of P one point at a time. After receiving each point, we compute the convex hull of the points seen so far. (a) As a naive approach, we could run Graham’s scan once for each point, with a total running time of O(n2 log n). Write down the pesuedocode for this algorithm. (b) Develop an O(n2) algorithm to solve the problem. Write...

  • 12. Suppose you haven video streams that need to be sent, one after another, over a...

    12. Suppose you haven video streams that need to be sent, one after another, over a communication link. Streami consists of a total of b, bits that need to be sent, at a constant rate, over a period of t seconds. You cannot send two streams at the same time, so you need to determine a schedule for the streams: an order in which to send them. Whichever order you choose, there cannot be any delays between the end of...

  • Give pseudocode that performs the traceback to construct an LCS from a filled dynamic programming table...

    Give pseudocode that performs the traceback to construct an LCS from a filled dynamic programming table without using the “arrows”, in O(n + m) time. 2. Suppose we are given a “chain” of n nodes as shown below. Each node i is “neighbors” with the node to its left and the node to its right (if they exist). An independent set of these nodes is a subset of the nodes such that no two of the chosen nodes are neighbors....

  • 2. (40 pts) Let A, B, and C be three strings each n characters long. We want to compute the longest subsequence that is...

    2. (40 pts) Let A, B, and C be three strings each n characters long. We want to compute the longest subsequence that is common to all three strings. (a) Let us first consider the following greedy algorithm for this problem. Find the longest common subsequence between any pair of strings, namely, LCS(A, B) LCS(B, C), LCS(A, C). Then, find the longest common subsequence between this LCS and the 3rd string. That is, supposing that the longest common pair wise...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT