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
According to the reading on the course web pages, the earliest usage of cooking began around _____ million years ago.
fenix001 [56]

Answer:

According to the reading on the course web pages, the earliest usage of clothes began around ____ million years ago. 3.4 1.5 0.8 0.5 1.7 2. According to the reading on the course web pages, lime mortar was probably discovered from annealing: Charcoal Obsidian Flint Glass 3.

Explanation:

6 0
3 years ago
Jasmine plays a game on her computer screen. A moving balloon appears on the screen, and she has to pop the balloon by clicking
Elena-2011 [213]
Please find the answer as attachment.

4 0
2 years ago
Keystroke loggers are stealth software packages that are used to monitor keyboard activities. Which is the best location to plac
irina [24]

Answer: Keyboard hardware & the operating system

Explanation:Keystroke loggers is also referred as the monitoring system which is a for the inspection of the every key pressed on an operating system. This technology monitors the activities of keypad devices such as smart phones etc. It is also used for the surveillance of the unauthorized activities that are done by the hackers or criminals.

Thus the correct option is keyboard hardware and the operating system is the location of the placement of the key loggers.

7 0
3 years ago
Select the correct answer.<br><br> Which statement is true with respect to Java?
NARA [144]

Answer:

where are the options ..... to select

7 0
2 years ago
Given a sorted array of integers created on the heap, its size and a new integer, design a function which will enlarge the array
Debora [2.8K]

Using the computational language in C++ to write a code that will organize the values ​​in an array through a mathematical condition.

<h3>writing code in C++</h3>

<em>#include <bits/stdc++.h></em>

<em>using namespace std;</em>

<em>int getIndexInSortedArray(int arr[], int n, int idx)</em>

<em>{</em>

<em>/* Count of elements smaller than current</em>

<em>element plus the equal element occurring</em>

<em>before given index*/</em>

<em>int result = 0;</em>

<em>for (int i = 0; i < n; i++) {</em>

<em>if (arr[i] < arr[idx])</em>

<em>result++;</em>

<em>if (arr[i] == arr[idx] && i < idx)</em>

<em>result++;</em>

<em>}</em>

<em>return result;</em>

<em>}</em>

<em>int main()</em>

<em>{</em>

<em>int arr[] = { 3, 4, 3, 5, 2, 3, 4, 3, 1, 5 };</em>

<em>int n = sizeof(arr) / sizeof(arr[0]);</em>

<em>int idxOfEle = 5;</em>

<em>cout << getIndexInSortedArray(arr, n, idxOfEle);</em>

<em>return 0;</em>

<em>}</em>

See more about C++ at brainly.com/question/12975450

#SPJ1

7 0
2 years ago
Other questions:
  • Which situation is an example of? "relational context" in the transactional model of? communication?
    12·1 answer
  • What character makes an assignment statement an assignment statement?
    15·1 answer
  • Geobubble Chart (2D) displaying Robot Density Per 10,000 Employees for the specified countries;
    7·1 answer
  • Betrand Meyer developed the ______ programming language which is not type-safe because it violates the law of contravariance.
    9·1 answer
  • ________ is used by text recognition software to convert typed, printed, or handwritten text into the computer-based characters
    15·1 answer
  • 1. Which of the following is not related to a buffer overflow? A. Static buffer overflow B. Index error C. Canonicalization erro
    10·1 answer
  • Which types of computers are used by large businesses
    10·1 answer
  • You want to draw a rectangle over the moon you added to your slide and then move it behind the moon. You want it to look like a
    15·1 answer
  • 9.2 lesson practice ​
    6·1 answer
  • Explain why you would use the soft on/off jumper when working on ATX system
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!