1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Mkey [24]
3 years ago
12

You are an interior decorator, confronted with a dark living room. To lighten the room up, you have n candles and want to build

k trees of candles. First, the candles {1, . . . , k} are already put on the floor, to serve as roots of the k trees. You would like to put the remaining n − k candles {k + 1, . . . , n} on top of them to form k trees {T1, · · · , Tk} of candles, where each Ti is rooted at candle i. You can put an arbitrary number of candles on top of the same candle. The cost to putting candle i on top of candle j is C(i, j). We assume that C(i, j) ≥ 0 and C(i, j) = C(j, i)) for i 6= j. No candle can be reused or put on top of itself. You cannot use the candles {1, . . . , k} anymore, as they have already been fixed to the floor.(a) Describe an algorithm to find a solution of minimum cost. (b) Prove the correctness of your algorithm. (c) Give a runtime analysis of your algorithm in the previous part.
Computers and Technology
1 answer:
user100 [1]3 years ago
6 0

Answer:

a)

Algorithm to find a solution of min. cost

Function:cost(Graph G,Graph G1);

GC --> empty graph

for i in edges E:

if E(i,j) in G:

c(i,j)=c(i,j)

else if E(i,j) in G1:

c(i,j)=-c(i,j)

Function:Mincost(Graph G):

GC=Cost(G,G1)

while(negativecycle(GC)):

Update residal graph(G1)

GC=Cost(G,G1)

mincost=sum of Cij*F(i,j)

return mincost;

Explanation:

a)

1) Start the program

2) Read the no. of edges and vertices and also read the cost of the two nodes.

3) Find the min cost by travelling to the destination i.e.. finding all possible min. cost values.

4) Compare the all possible min.cost values

5) And display the least min. cost

6) Stop the program

b)

<u>Correctness of algorithm</u>

1)Here in these algorithm we are calculating all the possible cases.

2)These algorithm also supports the negative cost.

3)These algorithm occupies more space.

4)Takes less time

5)so,these algorithm provides the cost efficient solution very effectively.

c)

<u>Run Time Analysis</u>

1) While reading the values during the run time the program execution will stop until user provides the values.

2) Based on the User input Output vary.

3) Time consumption and space consumption is depends on the no. of inputs the user is given.

You might be interested in
Going to Grad School! In the College of Computing and Software Engineering, we have an option for students to "FastTrack" their
Zielflug [23.3K]

Answer:

The programming language is not stated. However, I'll answer this question using Python programming language.

The program uses no comments; find explanation below

i = 0

while not (i == 4):

     print("Sample Run: #"+str(i+1))

     Major = input("Major: ")

     GPA = float(input("GPA: "))

     if not (Major.upper() == "SWE" or Major.upper() == "IT" or Major.upper() == "CGDD" or Major.upper() == "CS"):

           if GPA >= 3.50:

                 print("Great GPA, but apply using the regular application")

           else:

                 print("Talk to one of our advisors about whether grad school is for you")

     if (Major.upper() == "SWE" or Major.upper() == "IT" or Major.upper() == "CGDD" or Major.upper() == "CS"):

           if GPA >= 3.50:

                 print("You can FastTrack.")

           else:

                 print("Correct major, but GPA needs to be higher.")

     i = i + 1

Explanation:

Line 1 of the program initializes the sample run to 0

Line 2 checks if sample run is up to 4;

If yes, the program stops execution else, it's continues execution on the next line

Line 3 displays the current sample run

Line 4 and 5 prompts user for Major and GPA respectively

Line 6 to 10 checks is major is not one of CS, SWE, IT, and CGDD.

If major is not one of those 4 and GPA is at least 3.5, the system displays "Great GPA, but apply using the regular application"

If major is not one of those 4 and GPA is less than 3.5, the system displays "Talk to one of our advisors about whether grad school is for you"

Line 11 to 15 checks is major is one of CS, SWE, IT, and CGDD.

If major is one of those 4 and GPA is at least 3.5, the system displays "You can Fastrack"

If major is one of those 4 and GPA is less than 3.5, the system displays "Correct major, but GPA needs to be higher."

The last line of the program iterates to the next sample run

6 0
3 years ago
Type the correct answer in the box. Spell all words correctly.
nadezda [96]

Answer: Alt Text.

Explanation:

Alt Text or alt="Text" Allows for the website to load just the description of the image, rather than the image itself. Gets the Same message across without insane load times of large images.

5 0
3 years ago
Identify and explain five areas where computers are used to process <br> data
Zigmanuir [339]

Answer:

Explanation:

They are used in homes, businesses, educational institutions, research organizations, the medical field, government offices, entertainment, etc.

Home. ...

Medical Field. ...

Entertainment. ...

Industry. ...

Education. ...

Government. ...

Banking. ...

Business.

6 0
1 year ago
Write a program to randomly fill an array of float of 10 elements (use the rand() function and make sure to use #include ) in ma
Lilit [14]

Answer:

#include <iostream>

#include <stdlib.h>

#include <time.h>

using namespace std;

// array fill and returnig array to the main()

float *arrayFill(float *arr) {

// srand() allows generate new random value everytime the program runs

srand(time(NULL));

for (int i = 0; i < 10; i++)

{

 // array fill with random number between 0 to 100

 arr[i] = (rand() % 100);

}

return arr;

}

// print array

void print(float* arr) {

cout << "Array:  ";

for (int i = 0; i < 10; i++)

{

 cout << arr[i] << "   ";

 

}

}

float maxNum(float* arr) {

float temp = arr[0];

for (int i = 1; i < 10; i++) {

 if (temp < arr[i]) {

  temp = arr[i];

 }

}

return temp;

}

int main() {

// creating dynamic array of elements 10 in heap memory

float *arrPtr = new float[10];

float result = 0;

// calling arrayFill()

arrPtr = arrayFill(arrPtr);

// calling print() to print array

print(arrPtr);

// calling maxNum() to find maximum number in the array

result = maxNum(arrPtr);

cout << "\nmaximum number: " << result;

delete[] arrPtr;

return 0;

}

Explanation:

please read inline comments inside the code section:)

4 0
3 years ago
Which hypervisor works on older pcs without hardware virtualization support?
patriot [66]
The hypervisor which works on older PC's without hardware virtualization support is called VirtualBox. It is a software allows you to run operating systems in special environment which is called virtual machine. It means that you can run another OS without re-installing existing one.
5 0
3 years ago
Read 2 more answers
Other questions:
  • When should students practice netiquette in an online course?
    9·1 answer
  • The countryside presents
    11·1 answer
  • Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of the
    6·1 answer
  • In JAVA,
    10·1 answer
  • How do you reduce computer screen flicker
    11·1 answer
  • PLEASE HELP ASAP!!! 99 POINTS FOR 3 MULTIPLE CHOICE QUESTIONS!!! PLEASE ANSWER ALL!!!
    8·1 answer
  • ______________ is a raw fact about a person or an object
    6·1 answer
  • I need help with yes lol please and thank you
    15·2 answers
  • Can someone please help me answer the extension activity and the exit ticket. I’ll award you. Thanks❤️.
    12·1 answer
  • Suppose a packet is 10K bits long, the channel transmission rate connecting a sender and receiver is 10 Mbps, and the round-trip
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!