Job Scheduling: Consider the problem of scheduling n jobs of known durations t1, t2, ..., tn, for execution by a single processor. The jobs can be executed in any order, one job at a time. You want to find a schedule that minimizes the total time spent by all the jobs in the system. (The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.) Design a greedy algorithm for this problem. Does the greedy algorithm always yield an optimal solution?

Job Scheduling: Consider the problem of scheduling n jobs of known durations t1, t2, ..., tn, for execution by a single processor. The jobs can be executed in any order, one job at a time. You want to find a schedule that minimizes the total time spent by all the jobs in the system. (The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.) Design a greedy algorithm for this problem. Does the greedy algorithm always yield an optimal solution?

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

The city of BeeOS has a sightseeing tour which departs from a bus stop, takes a city tour and arrives at the same bus stop. There is only one bus that takes these tours indefinitely. The city visitors wait at the bus stop to board the bus, which can hold maximum N people. Each visitor should queue up at the bus stop and not get on until the bus starts its engine. The bus should wait until N visitors have boarded before departing. The bus can start its tour only when it is full. Once the bus has finished the trip, the visitors should get off after the bus stops its engine. All visitors should leave before the bus starts again. The process codes to be run by the bus and visitors are given below without any synchronization. Note that ‘Visitor’ code will be called by each visitor separately.Bus{loop{start_engine();take_tour();stop_engine();}}Visitor{get_on();get_off();}Rewrite the Bus and Visitor codes, with convenient mutex and/or semaphore operations, such that all synchronization…
Problem Alice was given a number line containing every positive integer, x, where 1<=x<=n. She was also given m line segments, each having a left endpoint, l (1<=l<=n), a right endpoint, r (1<=r<=n), and an integer weight, w. Her task is to cover all numbers on the given number line using a subset of the line segments, such that the maximum weight among all the line segments in the chosen subset is minimal. In other words, let S=(l1,r1,w1),(l2,r2,w2),....,(lk,rk,wk), represent a set of k line segments chosen by Alice, max(w1,w2,...,wk) should be minimized. All numbers 1,2,....n should be covered by at least one of k the chosen line segments. It is okay for the chosen line segments to overlap. You program should output the minimized maximum weight in the chosen subset that covers all the numbers on the number line, or -1 if it is not possible to cover the number line. Input format The first line of the input contains an integer, n - denoting the range of numbers…
Consider the software that runs in an Automated Teller Machine (ATM) machine. One task that must be able to be performed is to determine the type (denomination) of currency and the numbers of bills (aka “banknotes” for those of you not from North America) for each type dispensed. A requirement is that our ATM use the fewest number of bills that it can to dispense the specified amount of money. It only dispenses fifties, twenties, tens, fives, and ones. Design and implement program that writes out what bills would be dispensed if this machine existed for the amount of money that was asked for by the user.Test CasesIn the comments at the top of your file, list 3 test cases that you came up with. Something like this but choose your own examples. You should write your test cases in such a way that, if they all pass, you can be fairly confident your program will work all the time. '''Test case #1:Input: $1Output: 0 fifties, 0 twenties, 0 tens, 0 fives, 1 onesTest case #2:Input: $22Output:…
Using python solve the given problems: Problem: USA has the largest army that exists in the world. In USA it is always the military officer's main worry to order his soldiers on parade correctly. Luckily, ordering soldiers is not really such a problem. If a platoon consists of n men, all of them have different rank (from 1 - lowest to n - highest) and on parade they should be lined up from left to right in increasing order of rank. Sounds simple, doesn't it? Well, Sgt Johnny thought the same, until one day he was faced with a new command. He soon discovered that his elite commandos preferred to do the fighting, and leave the thinking to their superiors. So, when at the first rollcall the soldiers lined up in fairly random order it was not because of their lack of discipline, but simply because they couldn't work out how to form a line in correct order of ranks. Sgt Johnny was not at all amused, particularly as he soon found that none of the soldiers even remembered his own rank. Over…
The same professor writes a program to analyze the chat logs from the various lectures as a partial measure of class participation. Each chat log consists of multiple lines, each of form TIME, NAME, COMMENT, in the order in which they were posted to the chat . The algorithm then sorts all that data - across all the chat logs - in order of student names, and scores each set using a metric based on the number of contributions and their length. [a] What are the various input sizes to consider when analyzing the algorithmic approaches? (One is the number of students in the class, but that is not the only factor.) [b] Which sorting algorithm do you think is best suited for the sorting portion of this algorithm and why? [c] What is the time complexity of the sorting algorithm chosen in step [b] as a function of the various input sizes identified in step [a]? [d] What is the overall time complexity of the chat analysis program as described above?
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.
11. ) An algorithm X has two parts XA and Xg. In order to complete running algorithm X both parts have to be executed consecutively. If running time of XA is e(f(n)), and running time of Xp is O() then what should be f(n) so that algorithm X has the most efficient solution.
using Python programming language. The Towers of Hanoi is a classic puzzle that consists of 3 towers, and n disks of different sizes that can slide onto any tower. The puzzle starts with the disks sorted in ascending order of size from top to bottom. It has the following constraints:a. Only one disk can be moved at a time.b. A disk can only be moved from the top of one tower to another tower.c. A disk can only be placed on top of a larger disk. Write a pseudo-code.
There are ? tasks assigned to ? workers, and each worker can be assigned only one task. Each worker can complete any one of the tasks, but the time spent varies. Use the ant colony algorithm to find the best allocation scheme that minimizes the total time spent. Please write a program to solve the problem (with python/C/C++)
Consider the weighted interval scheduling problem, we have the following iterative solution (see 1.2.6 (and earlier sections if needed) of L6) to the problem: Assume we have n requests (1. n). For each request i, v(i) is the value of /. Recall we have defined function previous in class. ***** Line 1: for i from 0 to n, M[i]:= 0. Line 2: for i from 1 to n, M[i]:= max(v(i) + M[previous(i)], M[i-1]) SEE Per a) Write down precisely what is the intended meaning of the data structure M[...] b) Why do we do line 1? c) Explain the meaning of M[i]:= max(v(i) + M[previous()], M[i-1]) in Line 2.
Branch-and-bound method exercise (Computer Science or Advanced Math) Let there be five jobs of the same type and one machine to get those jobs done. The processing time of the job on the machine and the time allowed for the job to be completed for each job are given in the table below. Job On the machinecompletion time(minute) To be finishedtime allowed(minute) 1 3 4 2 6 8 3 8 12 4 4 15 5 2 11 Apply the branch-and-bound method step by step to order the jobs in a way that minimizes the total delay time. State the optimal solution clearly. Thank you so much.