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
The goal of a system is to
andreyandreev [35.5K]

Answer:

The answer is option C, which is: perform a task

6 0
3 years ago
I need an answer fast !!! (APEX)
lana [24]
Your answer is B)<span>The Intel 4004</span>
3 0
3 years ago
Why are high-quality transformers wound with large diameter wire?
lesya692 [45]
So that they can lower the I2R losses
8 0
3 years ago
A ____ attack is much more substantial than a DoS attack because of the use of multiple systems to simultaneously attack a singl
victus00 [196]

Answer: (D) Distributed denial- of- service (DDoS)

Explanation:

The distributed denial of service attack is one of the type of attack that occur when the multiple system are basically flooded with the resources and the bandwidth.

  • Botnet is one of the example of DDoS as it caused the DOS (denial of service) for the users.
  • This type of attack is more substantial as compared to the DoS attack as they use the multiple system for attack the single target simultaneously.

Therefore, Option (D) is correct.

8 0
3 years ago
mapa mental con la explicación de que medios de comunicación y redes sociales intervienen en la construcción de tu identidad​
lisov135 [29]

Answer:

este presente yo cuando me pidieron eso

5 0
3 years ago
Other questions:
  • Which of these is a social consequence of effective communication
    12·1 answer
  • What's is the contribution of technology to the country?
    15·1 answer
  • What is the output of the second println statement in the main method? public class Foo { int i; static int s; public static voi
    14·1 answer
  • What is Administrator windows 10
    8·1 answer
  • Write a program that takes the radius of a sphere (a floating-point number) as input and then outputs the sphere’s: Diameter (2
    7·1 answer
  • When computing the cost of the basket of goods and services purchased by a typical consumer, which of the following changes from
    11·1 answer
  • After fixing the format of her subheadings, she notices that she misspelled the name of one of the famous people
    7·2 answers
  • What is the positional weigh of the digit 7 in the octal number 7642 ?​
    15·1 answer
  • Microsoft word 2010 lab 6-1
    7·2 answers
  • You are a teaching assistant for an introductory computer concepts course at your local community college. The instructor asks y
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!