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
Recall the binary search algorithm.1. Using the algorithm/algorithmic environment, give pseudocode using a for loop.AnswerMy alg
faust18 [17]

Answer:

Following are the Pseudo Code to the given question:

Explanation:

Following are the pseudo-code by using the For loop:

Defines the A function (node, element)

The node is larger than 0.

if another value of the node equals its element

Loop Break

That element if node. value becomes lower than that

Node is node equivalent.

right

Using other nodes is node equivalent.

 left

Node Return

If the node is vacant

print the Tree is empty

Following are the pseudo-code by using the while loop:

Defines the function A(node,element)

While this node is not zero.

if the value of the node equals the element

Loop Break

The element if node. value is lower than

Node is node equivalent.

right

Using other nodes is equivalent to an a.left node

Node Return

If the node is vacant

print Tree is empty

following are the Pseudo-code for recursion:

Set the function A (node, key)

If no root is the same as the root or no root.

return the root.

If the root value is lower than that of the quest for key return (root. right, key)

Return your lookup (root.left,key)

 

5 0
2 years ago
Select all examples of proper keyboarding technique.
emmasim [6.3K]
Keep your eyes on the text and aim to make no mistakes
4 0
3 years ago
Read 2 more answers
Does anyone know a working free spotify premium on ios 2021 plz i have had any luck finding anything:(​
natima [27]
No sorry

................
5 0
3 years ago
Read 2 more answers
11. Describe an algorithm that interchanges the values of the variables x and y, using only assignments. What is the minimum num
Svetlanka [38]

Answer:

Following is the algorithm to interchange the value of two variable x and y.

step 1:Read the two integer x and y.

step 2 :t=x

Step 3: x=y  

step 4: y=t

The minimum number of assignment to do this is 3

Explanation:

After reading two integer x & y, create a variable "t" of integer type.

with the help of variable "t", we can swap the value of variable x and y.

It requires 3 assignment to interchange the value.

6 0
3 years ago
Design a circuit that has a 3-bit binary input B2, B1, B0 (where B2 is most significant bit and B0 is least significant bit) and
jenyasd209 [6]

Isn't this circuit just a wire, where Z=B0?

3 0
3 years ago
Other questions:
  • Which of the following provides astronomical evidence for the age of the earth?
    11·1 answer
  • When Clara accesses the programs and documents on her computer by way of icons, she is said to be employing
    12·1 answer
  • Write a Java program that generates GUI (Graphical User Interface). Your program should provide labels and textfields to a user
    9·1 answer
  • You’ve just finished training an ensemble tree method for spam classification, and it is getting abnormally bad performance on y
    9·1 answer
  • Why is Linux widespread in academic environments?
    7·1 answer
  • How can you stretch or skew an object in paint
    12·2 answers
  • What types of printed information are useful to obtain from your target employers?
    5·1 answer
  • Help me to solve please​
    8·2 answers
  • Dunbar's number, 150, refers to the number of:
    5·1 answer
  • Which of the following terms refers to the cells that contain values and labels to be graphed in the chart?.
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!