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
William brought some data into his Tableau Book, but the data had some null values and incorrect column headers. What did Willia
ozzi

William  had to manually edit the data if he wants to remove the null values and incorrect column headers.

<h3>What is data editing?</h3>

Data editing is known to be a term that connote the act of making changes, reviewing or adjustment  some survey data.

Note that by editing one can remove want one do not want from a group of data and as such,  William  had to manually edit the data if he wants to remove the null values and incorrect column headers.

Learn more about data from

brainly.com/question/26711803

#SPJ1

6 0
2 years ago
Which of the following is a safe work practice to protect you from electrocution hazards?
Flura [38]
What are the answer choices?
7 0
3 years ago
click the view lab button. restart the computer and press the f2 or delete key on your keyboard to enter the bios setup program.
IgorLugansk [536]

The brand of processor that is known to be installed are:

  • Intel
  • 4096
  • 1610
  • -3
  • Enabled
  • -Diskette Drive

<h3>What a processor means?</h3>

A processor (CPU) is known to be a kind of logic circuitry that  is known to answer to and work on the basic instructions that tends to drive a computer.

Note that the CPU is seen as the key  and most crucial integrated circuitry (IC) chip and the intel process is known to be one of the most common forms of processor.

Therefore, The brand of processor that is known to be installed are:

  • Intel
  • 4096
  • 1610
  • -3
  • Enabled
  • -Diskette Drive

Learn more about bios settings from

brainly.com/question/13103092

#SPJ1

Click the View Lab button. When the simulated computer starts, press the F2 or Delete key on your keyboard to enter the BIOS setup program. Explore the current BIOS settings to find the answers to the following questions.

What brand of processor is installed?

4 0
1 year ago
A(n) _____ element, as described by the World Wide Web Consortium (W3C), is an element that "represents a section of a page that
MariettaO [177]

Answer:

B. Aside element

Explanation:

The options for this question are missing, the options are:

A. ​article element

B. ​aside element

C. ​section element

D. ​content element

An aside element is defined as a section of a page that has content that is tangentially related to the content around the element. In other words, the aside element represents content that is indirectly related to the main content of the page. Therefore, we can say that the correct answer to this question is B. Aside element.

8 0
3 years ago
What should you keep in mind when adding contents to your digital portfolio?
sveticcg [70]

Answer:

The contents of the portfolio will depend on individual education, work experience and future goals

Explanation:

The contents of the portfolio will depend on the following -

a) Work biography/experiences

b) Career goals

c) personal details

d) contact information

e) Professional photograph

f) Relevant skills

g) Relevant documents, certificates, degree etc.

etc.

4 0
3 years ago
Other questions:
  • Write a void function SelectionSortDescendTrace() that takes an integer array, and sorts the array into descending order. The fu
    9·1 answer
  • Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[
    13·1 answer
  • What are an administrator's choices for managing file permissions on a drive formatted as fat32?
    10·1 answer
  • Write the definition of a function named quadratic that receives three double parameters a, b, c. If the value of a is 0 then th
    12·1 answer
  • This program outputs a downwards facing arrow composed of a rectangle and a right triangle. The arrow dimensions are defined by
    8·1 answer
  • Universal Containers uses a custom object within the product development team. Product development, executives, and System Admin
    11·1 answer
  • How do you write a multiplication formula in excel with an absolute refrence?
    11·1 answer
  • What are the factors affecting the life of ballast? Explain.​
    15·1 answer
  • Hot components or sharp edges of computer is an example of what hazard​
    14·1 answer
  • You are a developer for a news, entertainment, lifestyle, and fashion website. User traffic has steadily increased month-over-mo
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!