You are given a sequence of n songs where the ith song is l minutes long. You want to place all of the songs on an ordered series of CDs (e.g. CD 1, CD 2, CD 3,... ,CD k) where each CD can hold m minutes. Furthermore, (1) The songs must be recorded in the given order, song 1, song 2,..., song n. (2) All songs must be included. (3) No song may be split across CDs. Your goal is to determine how to place them on the CDs as to minimize the number of CDs needed. Give the most efficient algorithm you can to find an optimal solution for this problem, prove the algorithm is correct and analyze the time complexity

Answers

Answer 1

Answer:

This can be done by a greedy solution. The algorithm does the following:  

Put song 1 on CD1.

For song 1, if there's space left on the present CD, then put the song on the present CD. If not, use a replacement CD.

If there are not any CDs left, output "no solution".

Explanation:  

The main thing is prove the correctness, do that by the "greedy stays ahead argument". For the primary song, the greedy solution is perfect trivially.  

Now, let the optimal solution match the greedy solution upto song i. Then, if the present CD has space and optimal solution puts song (i+1) on an equivalent CD, then the greedy and optimal match, hence greedy is not any worse than the optimal.Else, optimal puts song (i + 1) on subsequent CD. Consider an answer during which only song (i + 1) is moved to the present CD and zip else is modified. Clearly this is often another valid solution and no worse than the optimal, hence greedy is not any worse than the optimal solution during this case either. This proves the correctness of the algorithm. As for every song, there are constantly many operations to try to do, the complexity is O(n).


Related Questions

Mối quan hệ giữa đối tượng và lớp
1. Lớp có trước, đối tượng có sau, đối tượng là thành phần của lớp
2. Lớp là tập hợp các đối tượng có cùng kiểu dữ liệu nhưng khác nhau về các phương thức
3. Đối tượng là thể hiện của lớp, một lớp có nhiều đối tượng cùng thành phần cấu trúc
4. Đối tượng đại diện cho lớp, mỗi lớp chỉ có một đối tượng

Answers

Answer:

please write in english i cannot understand

Explanation:

1. Describe data and process modeling concepts and tools.

Answers

Answer:

data is the raw fact about its process

Explanation:

input = process= output

data is the raw fact which gonna keeps in files and folders. as we know that data is a information keep in our device that we use .

Answer:

Data and process modelling involves three main tools: data flow diagrams, a data dictionary, and process descriptions. Describe data and process tools. Diagrams showing how data is processed, transformed, and stored in an information system. It does not show program logic or processing steps.

You have a shared folder named Reports. Members of the Managers group have been given Write access to the shared folder. Mark Mangum is a member of the Managers group. He needs access to the files in the Reports folder, but he should not have any access to the Confidential.xls file. What should you do

Answers

Answer:

Following are the solution to the given question:

Explanation:

The common folder called Report has also been shared. Writing access to a shared folder was given to management group members. Mark is a member of a group of managers. We can access the files within your reporting directory, but you really should not access the Confidential.xls file. We want to add Mark Mangum to our ACL files using Deny permissions on Confidential.xls.

State two ways of preventing virus attack on a computer.​

Answers

Answer:

updating the computer and having an anti virus on your computer

Would you prefer to use an integrated router, switch, and firewall configuration for a home network, or would you prefer to operate them as separate systems

Answers

Answer:

I would prefer to use an integrated router, switch, and firewall configuration for a home network instead of operating my home devices as separate systems.

Explanation:

Operating your home devices as separate systems does not offer the required good service in information sharing.  To share the internet connection among the home devices, thereby making it cheaper for family members to access the internet with one  Internet Service Provider (ISP)  account rather than multiple accounts, a home network is required. A home network will always require a network firewall to protect the internal/private LAN from outside attack and to prevent important data from leaking out to the outside world.

Given an array of n distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. Note that integers in array can be negative. Examples: #include using namespace std; void removeDivByFive(int *arr,int& size) { int index=0; for(int i=0;i

Answers

Answer:

The function is as follows:

int returnsFixed(int arr [],int n){

   int retVal = -1;

   for(int i = 0; i<n;i++){

       if(i == arr[i]){

           retVal = i;

           break;

       }

   }

   return retVal;

}

Explanation:

This defines the functionl it receives the array and the length of the array

int returnsFixed(int arr [],int n){

This initializes the return value to -1

   int retVal = -1;

This iterates through the array

   for(int i = 0; i<n;i++){

This checks if i equals arr[i]

       if(i == arr[i]){

If yes, the return value (i.e. the fixed point) is set to i

           retVal = i;

And the code is exited

           break;

       } This ends the if condition

   } This ends the iteration

This returns the calculated fixed point

   return retVal;

}

write a loop that reads positive integers from stands input and that terinated when it reads an interger that is not positive after the loop termpinates

Answers

Loop takes only positive numbers and terminates once it encounters a negative numbers.

Answer and Explanation:

Using javascript:

Var positiveInt= window.prompt("insert positive integer");

While(positiveInt>=0){

Alert("a positive integer");

Var positiveInt= window.prompt("insert positive integer");

}

Or we use the do...while loop

Var positiveInt= window.prompt("insert positive integer");

do{

Var positiveInt= window.prompt("insert positive integer");

}

While (positiveInt>=0);

The above program in javascript checks to see if the input number is negative or positive using the while loop condition and keeps executing with each input until it gets a negative input

Choose all that Apply: Which of the following steps should be performed by the CIS for creating a part dispatch for systemboard through Tech Direct?
a) Enter the customer's contact and email address into the primary contact fields when requesting a systemboard through TechDirect
b) Logging fusion ticket to request DPK via DDL
c) Access the customer's DDL account to retrieve DPK and activate the os for the customer
d) Verify the customer email address

Answers

Answer:

The steps that should be performed by the CIS for creating a part dispatch for system board through TechDirect are:

a) Enter the customer's contact and email address into the primary contact fields when requesting a system board through TechDirect

b) Logging fusion ticket to request DPK via DDL

c) Access the customer's DDL account to retrieve DPK and activate the os for the customer

d) Verify the customer email address

Explanation:

The four steps given above must be performed in the CIS if you want to create a part dispatch for the system board through TechDirect.  TechDirect is a support system that enables one to manage all Dell technologies from a single location. After creating the part dispatch, the customer's contact and email address are entered into the primary contact fields to enable the verification of the customer's email address  through the TechDirect.

Why input screens are better data entry than entreing data dirrctly to a table

Answers

Answer:

are better data entry designs than entering data directly to a table. ... hence a user can design input fields linked to several tables/queries.

Explanation:

Input screens are better data entry designs than entering data directly to a table because a user can design input fields linked to several tables/queries.

What is digital information?

Digital information generally consists of data that is created or prepared for electronic systems and devices such as computers, screens, calculators, communication devices. These information are stored by cloud.

They are converted from digital to analog and vice versa with the help of a device.

Data entered in the table directly is easier than data entry method.

Thus, input screens are better data entry than entering data directly to a table.

Learn more about digital information.

https://brainly.com/question/4507942

#SPJ2


describe the evolution of computers.​

Answers

Answer:

First remove ur mask then am to give you the evolutions

Which of the following restricts the ability for individuals to reveal information present in some part of the database?

a. Access Control
b. Inference Control
c. Flow Control
d. Encyption

Answers

Answer:

it would have to be flow control which would be C.

Explanation:

Flow Control is restricts the ability for individuals to reveal information present in some part of the database. Hence, option C is correct.

What is Flow Control?

The management of data flow between computers, devices, or network nodes is known as flow control. This allows the data to be processed at an effective rate. Data overflow, which occurs when a device receives too much data before it can handle it, results in data loss or retransmission.

A design concern at the data link layer is flow control. It is a method that typically monitors the correct data flow from sender to recipient. It is very important because it allows the transmitter to convey data or information at a very quick rate, which allows the receiver to receive it and process it.

The amount of data transmitted to the receiver side without any acknowledgement is dealt with by flow control.

Thus, option C is correct.

For more information about Flow Control, click here:

https://brainly.com/question/28271160

#SPJ5

what is the answer to the question asked in the picture attached below ​

Answers

Answer:

option - b

Explanation:

i think this is the right answer..

9. Which of the following prefixes which relate to bytes are arranged from the smallest to the largest? a) mega, giga, tera, kilo b) meqa tera, giga, kilo c) kilo, mega, giga, tera d) kilo, giga, mega, tera​

Answers

Answer:

Explanation:

C

kilo = 1000

mega = 1,000,000

giga = 1 billion = 1 000 000 000

tera = 1 trillion = 1 000 000 000  000

Computer data that is suitable for text​

Answers

Answer:

Answer:Data Types. Computer systems work with different types of digital data. In the early days of computing, data consisted primarily of text and ...

Declare an ArrayList of Strings. Add eight names to the collection. Output the Strings onto the console using the enhanced for loop. Sort the ArrayList using the method Collections.sort. Output the sorted List. Shuffle the list, and output the shuffled list. Note that Collections (with an s) is a class, while Collection is an interface. The Collections class has many useful static methods for processing interfaces, including the sort method. Search for a name in the list that exists; output the location where it was found. Search for a name that is not in the list. What location is reported? Convert the list to an array using toArray. Output the elements of the array. Convert the array back into a list using asList. Output the elements of the list.

Answers

Answer:

---------------------------

Explanation:

A browser is a program that allow
A. users transfer messages and files through internet.
B. users search for relevant information on the WWW.
C. users to access and view web pages on the internet.
D. users exchange real-time messages or files with another online user​

Answers

C. users to access and view web pages on the internet.

A technician is configuring the static TCP/IP settings on a client computer.
Which of the following configurations are needed for internet communications?
a. DHCP server address
b. DNS server address
c. Default gateway address
d. WINS address
e. APIPA address
f. Alternate IP address
g. IP address including a subnet mask (IPv4) or subnet prefix length (IPv6)

Answers

Answer:

The answer is below

Explanation:

Considering the situation and the available options above, the following configurations are needed for internet communications:

B. DNS server address: this matches the domain name to the IP address of a website such that browsers can bring internet resources.

C. Default gateway address: this uses the internet protocol suites and serves as a router to other networks in the absence of other route specifications that could match the destination IP address of a packet.

G. IP address including a subnet mask (IPv4) or subnet prefix length (IPv6): this is used by the internet-connected device to receive messages.

what its the difference between Arduinos and Assembler?

Answers

Answer:

The Arduino boards can be programmed in assembly. All you need is an ICSP Cable (In Circuit Serial Programmer) and the AVR toolchain (free from ATMEL) to write to the board. You then get the advantage of on board debugging.

As you suggested, you can just slap an ATMEL chip on a breadboard and go to town.

Explanation: cause i said so

14. For the declaration, int a[4] = {1, 2, 3};, which one is right in the following description-
(
A. The meaning of &a[1] and a[1] are same B. The value of a[1] is 1-
C. The value of a[2] is 3
D. The size of a is 12 bytes

Answers

Answer:

A.

thanks later baby HAHAHAHAHAA

mention two strategies of collecting data​

Answers

Types of quantitative and qualitative data collection methods include surveys and questionnaires, focus groups, interviews, and observations and progress tracking.

All of the following are technical solutions to protecting user privacy except: Group of answer choices Data use policies Anonymous email Preventing client computers from accepting cookies Email encryption Anonymous surfing

Answers

Answer:

Data use policies

Explanation:

Technically data use policies are not specifically made to protect user privacy, however it also should not violate user privacy. Data use policies are required by law. They are compulsory disclosures that list the various ways in which data in the form of personal data of individuals is collected, shared or used by digital companies(companies that operate on the internet, make use of email lists, etc ) are used.

what operation can be performed using the total feature ​

Answers

They can do different surgery on people. One is called cataract total and hip replacement surgery which is what can be expected

Question 1(Multiple Choice Worth 5 points)
(01.01 MC)
Which broad category is known for protecting sensitive information in both digital and hard-copy forms?
O Cybersecurity
O Information protection
O Information assurance
Internet Crime Complaint Center

Answers

Answer:

Information assurance

Explanation:

Data theft can be defined as a cyber attack which typically involves an unauthorized access to a user's data with the sole intention to use for fraudulent purposes or illegal operations. There are several methods used by cyber criminals or hackers to obtain user data and these includes DDOS attack, SQL injection, man in the middle, phishing, etc.

Information assurance is a broad category that is typically used by cybersecurity or network experts to protect sensitive user information such as passwords, keys, emails, etc., in both digital and hard-copy forms

Fred is a 29 year old golfer, who has been playing for 4 years. He is a 12 handicap. He is considering the Srixon ZX5 or the Mavrik Pro. Talk through major considerations and provide a recommendation that would be well suited for him. Include explanations about forged vs cast features, the look of the club, and overall feel.

Answers

Answer:

oh nice yes good fine I like it

Large computer programs, such as operating systems, achieve zero defects prior to release. Group of answer choices True False PreviousNext

Answers

Answer:

The answer is "False"

Explanation:

It is put to use Six Sigma had 3.4 defects per million opportunities (DPMO) from the start, allowing for a 1.5-sigma process shift. However, the definition of zero faults is a little hazy. Perhaps the area beyond 3.4 DPMO is referred to by the term "zero faults.", that's why Before being released, large computer programs, such as operating systems, must have no faults the wrong choice.

The values of existing data can be modified using the SQL ________ command, which can be used to change several column values at once.

Answers

Answer:

The values of existing data can be modified using the SQL ___Update_____ command, which can be used to change several column values at once.

Explanation:

However, if you are interested in modifying some columns, then you must specify the columns of interest by using Update (table name) Set column1, column2, etc., which assigns a new value for the columns that you want to update, with each column value separated by a comma.  The SQL (Structured Query Language) Update command is used to update data of an existing database table.

9.19 LAB: Sort an array Write a program that gets a list of integers from input, and outputs the integers in ascending order (lowest to highest). The first integer indicates how many numbers are in the list. Assume that the list will always contain less than 20 integers. Ex: If the input is:

Answers

Answer:

i hope you understand

mark me brainlist

Explanation:

Explanation:

#include <iostream>

#include <vector>

using namespace std;

void vector_sort(vector<int> &vec) {

int i, j, temp;

for (i = 0; i < vec.size(); ++i) {

for (j = 0; j < vec.size() - 1; ++j) {

if (vec[j] > vec[j + 1]) {

temp = vec[j];

vec[j] = vec[j + 1];

vec[j + 1] = temp;

}

}

}

}

int main() {

int size, n;

vector<int> v;

cin >> size;

for (int i = 0; i < size; ++i) {

cin >> n;

v.push_back(n);

}

vector_sort(v);

for (int i = 0; i < size; ++i) {

cout << v[i] << " ";

}

cout << endl;

return 0;

}

A recursive method may call other methods, including calling itself. A recursive method has:
1. a base case -- a case that returns a value or exits from a method without performing a recursive call.
2. a recursive case -- calling the method again with a smaller case..
Study the recursive method given below.
For example, this call recursiveMethod (5); returns 15:
public static int recursiveMethod (int num) (
if (num == 0)
return 1;
else {
if (numX2!=0)
return num * recursiveMethod (num -1);
else
return recursiveMethod (num-1);
}
}
1 What is the base case?
2. What does the following statement check?
3. What does the method do?

Answers

Answer:

Hence the answer is given as follows,

Explanation:

Base Case:-  

If (num == 0) //This is the base case for the given recursive method  

return 1;  

If(num % 2!=0) checks whether num is odd.  

The above condition is true for all odd numbers and false for even numbers.  

if the remainder is not equal to zero when we divide the number with 2 then it is odd.  

The method:-  

The above recursive method calculates the product of odd numbers up to the given range(that is num)  

For num=5   => 15(5*3*1).  

For num=7   => 105(7*5*3*1).  

For num=10 => 945(9*7*5*3*1).

Identify and differentiate between the two (2) types of selection structures

Answers

Answer:

there are two types of selection structure which are if end and if else first the differentiation between if and end if else is if you want your program to do something if a condition is true but do nothing if that condition is false then you should use an if end structure whereas if you want your program to do something if a condition is true and do something different if it is false then you should use an if else structure

You are having a problem with your Windows computer that is isolated to a single graphics editing program that you use every day in your work. When you described the problem to the customer service support person for this product, she told you that the only fix for it is to edit a key under HKEY-LOCAL_MACHINE\SOFTWARE. She has assured you that this fix will work without causing any problems, but you are wary of doing this. Descript the steps and precautions taken.

Answers

Answer:

I'm not a big tech head but I know that creating a restore point is highly recommended for changing anything that you aren't 100% sure about to your computer.

Other Questions
For which of the following transitions would a hydrogen atom absorb a photon with the longest wavelength?a. n = 1 to n = 2 b. n = 3 to n = 2 c. n = 5 to n = 6 d. n = 7 to n = 6 1.- Que distancia recorri una carga de 2,5x10-6 coul, generando as un campo elctrico de 55new/coul. What is the weighted average cost of capital if a business has a cost of equity of 11%, a yield on debt of 6%, a tax rate of 30%, 100 million market value of debt, and 250 million market value of equity How long do the detectives have left on their misson?a few daysa few hoursan houra few minutes 3 questions only pls help gota finish tofday How late do you stay up? URGENTTTTTTTT!! HELP QUICK PLZZZZZZZZz According to Garrett et al. (1975, 1988, 1989), language production proceeds through a series of processes: ______, ______, and ______. During the same Olympics, Bolt also set the world record in the 200-m dash with a time of 19.30 s. Using the same assumptions as for the 100-m dash, what was his maximum speed for this race Problem: Construct a triangle with interior angle measures of 60 and 60. Let one of the side lengths be 10. What are the lengths of the other sides? complex sentence using indolent Simplify this algebraic expression y-3 over 3+12 an object that has lost its electrons become? explain how World War I led to significant changes in society Write two points of differences between complete and incomplete combustion? PLEASE HELP ITS EASY BUT LIKE yh Cold air rises because it is denser than water, is this true? I NEED THIS ASAP!!!!!!!!!!!!!!!!!!The main idea of this paragraph is: Gertrude Elion was a determined woman who had real life and classroom experiences that helped her learn biochemistry. If sentence 3 is removed from the paragraph, what is the new main idea of the paragraph?Gertrude Belle Elion was born on Jan. 23, 1918, in New York City.She graduated from Hunter College in New York City with a degree in biochemistry in 1937.Unable to obtain a graduate research position because she was a woman, she took a series of jobs, including lab assistant, chemistry and physics teacher in New York City high schools, and research chemist.During this time she also took classes at New York University, where she earned a master's degree in 1941.Because she could not devote herself to full-time studies, Elion never received a doctorate. Elion learned everything she needed to know from her courses. Elion was a busy person and a distracted student. Elion never received her doctorate degree. Elion had full scholarships to college because she was a woman. Believe; Eat; Flow; Go; Grow; Make; Rise; Tell; Translate1.The earth................round the sun.2.Rice.......................in Britain.3.The sun..................in the east.4.Bees......................honey.5.Vegetarians............meat.6.An atheist..............in God.7.An interpreter....................from one language into another.8.A liar is someone who...........the truth.9.The River Amazon..................into the Atlantic Ocean. A pharmaceutical company is using blockchain to manage their supply chain. Some of their drugs must be stored at a lower temperature throughout transport so they installed RFID chips to record the temperature of the container.Which other technology combined with blockchain would help the company in this situation?