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 web is based on the ________ protocol
elena55 [62]
The standard (and default) port for HTTP<span> servers to listen on is 80, though they can use any port. </span>HTTP<span> is based on the </span>TCP/IP protocols<span>, and is used commonly on the Internet for transmitting web-pages from servers to browsers.</span>
3 0
3 years ago
How do I turn on your asus chromebook flip?
galben [10]
I believe the charger has to be connected for it to turn on.
3 0
3 years ago
In 1–2 sentences, describe how you would create a border around a group of cells
iragen [17]
Pick one of the cells you<span> want to format and then click the down arrow beside the </span>Borders<span> button in the Font </span>group<span> on the Home tab. A drop-down menu comes up with all the</span>border<span> options that </span>you can<span> apply to the </span>cell<span> selection</span>
4 0
3 years ago
Read 2 more answers
The area of a parallelogram is 18 square units.one side of the parallelogram is 24 units long.The other side is 6 unit long. whi
taurus [48]

Answer:

Height = \frac{3}{4}\ unit

Height = 3\ units

Explanation:

Given

Shape: Parallelogram

Area = 18 unit^2

Side\ 1 = 24  units

Side\ 2 = 6 units

Required

Determine possible heights of the parallelogram

Area of parallelogram is:

Area = Base * Height

Make Height the subject of formula

Height = \frac{Area}{Base}

When Base = 24 units;

Height = \frac{18}{24}

Height = \frac{3}{4}\ unit

When Base = 6 units;

Height = \frac{18}{6}

Height = 3\ units

8 0
2 years ago
2.3 Code Practice: Question 2
V125BC [204]

<u>Answer:</u>

<em>feetFab1 = int(input(""Enter the value in feet for the 1st  piece of fabric: ""))</em>

<em>inchFab1 = int(input(""Enter the value in inches for the 1st  piece of fabric: ""))</em>

<em />

<em>feetFab2 = int(input(""Enter the value in feet for the 2nd  piece of fabric: ""))</em>

<em>inchFab2 = int(input(""Enter the value in inches for the 2nd  piece of fabric: ""))</em>

<em />

<em>feetSum = (feetFab1 + feetFab2)</em>

<em>inchSum = (inchFab1 + inchFab2)</em>

<em />

<em>totalFeet = ((inchSum % 12) + feetSum)</em>

<em>totalInch = (feetSum % 12)</em>

<em>print (""Feet: "" + str(totalFeet) + "". Inches: "" + str(totalInch))</em>

7 0
3 years ago
Other questions:
  • Predict how digital video will be viewed in the future. Step into the year 2028. How are people viewing digital video? Or have w
    13·2 answers
  • Moderate changes to existing processes falls under the _________ analysis. Business Process Automation (BPA) Business Process Im
    5·1 answer
  • Pls help me
    5·1 answer
  • ___ is an example of a function prototype.
    12·1 answer
  • An IT firm came across a startup company that offers a new system of computer storage. It is currently in the experimental phase
    11·1 answer
  • A web application is an example of:
    7·1 answer
  • What is DATE data type and its syntax and what is TIMESTAMP data type and its syntax in SQL language.Explain the difference betw
    14·1 answer
  • Help me decide this hurry
    12·1 answer
  • What are the odds that you find someone you know in person on here
    5·1 answer
  • In Windows 7's Jump List, what can we do?
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!