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]
4 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]4 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
La computadora es un medio de comunicacion moderno?
kolbaska11 [484]
Moderno = mordern, if It does than yes!
3 0
3 years ago
As part of a team, you are assigned to create a financial report. One of your tasks is to put the pieces together as other team
erastova [34]
Summary task
or
Introduction
6 0
3 years ago
Which statement best explains the way that similar apps are used in different devices?
monitta

The statement that  best explains the way that similar applications are used in different devices is option b:  Although the systems are different, the apps are still designed to work the same way.

<h3>How does an app work?</h3>

An app is known to be a kind of a software that gives room for a person to be able to carry out some specific tasks.

Note that Applications for desktop or laptop computers are said to be called desktop applications and those apps that are used in mobile devices are known to be called mobile apps.

Hence, The statement that  best explains the way that similar apps are used in different devices is option b:  Although the systems are different, the apps are still designed to work the same way.

Learn more about Software applications from

brainly.com/question/22442533

#SPJ1

6 0
2 years ago
Given an array as follows
slava [35]

Answer:

1) Method calcTotal:

  1. public static long calcTotal(long [][] arr2D){
  2.        long total = 0;
  3.        
  4.        for(int i = 0; i < arr2D.length; i++ )
  5.        {
  6.            for(int j = 0; j < arr2D[i].length; j++)
  7.            {
  8.                total = total + arr2D[i][j];
  9.            }
  10.        }
  11.        
  12.        return total;
  13.    }

Explanation:

Line 1: Define a public method <em>calcTotal</em> and this method accept a two-dimensional array

Line 2: Declare a variable, total, and initialize it with zero.

Line 4: An outer for-loop to iterate through every rows of the two-dimensional array

Line 6: An inner  for-loop to iterate though every columns within a particular row.

Line 8: Within the inner for-loop, use current row and column index, i and j, to repeatedly extract the value of each element in the array and add it to the variable total.

Line 12: Return the final total of all the element values as an output

Answer:

2) Method calcAverage:

  1. public static double calcAverage(long [][] arr2D){
  2.        double total = 0;
  3.        int count = 0;
  4.        
  5.        for(int i = 0; i < arr2D.length; i++ )
  6.        {
  7.            for(int j = 0; j < arr2D[i].length; j++)
  8.            {
  9.                total = total + arr2D[i][j];
  10.                count++;
  11.            }
  12.            
  13.        }
  14.        
  15.        double average = total / count;
  16.        
  17.        return average;
  18.    }

Explanation:

The code in method <em>calcAverage</em> is quite similar to method <em>calcTotal</em>. We just need to add a counter and use that counter as a divisor of total values to obtain an average.

Line 4: Declare a variable, count, as an counter and initialize it to zero.

Line 11: Whenever an element of the 2D array is added to the total, the count is incremented by one. By doing so, we can get the total number of elements that exist in the array.

Line 16: Use the count as a divisor to the total to get average

Line 18: Return the average of all the values in the array as an output.

Answer:

3) calcRowAverage:

  1. public static double calcRowAverage(long [][] arr2D, int row){
  2.        double total = 0;
  3.        int count = 0;
  4.        
  5.        for(int i = 0; i < arr2D.length; i++ )
  6.        {
  7.            if(i == row)
  8.            {
  9.                for(int j = 0; j < arr2D[i].length; j++)
  10.                {
  11.                    total = total + arr2D[i][j];
  12.                    count++;
  13.                }
  14.            }
  15.            
  16.        }
  17.        
  18.        double average = total / count;
  19.        
  20.        return average;
  21.    }

Explanation:

By using method <em>calcAverage </em>as a foundation, add one more parameter, row, in the method <em>calcRowAverage</em>. The row number is used as an conditional checking criteria to ensure only that particular row of elements will be summed up and divided by the counter to get an average of that row.

Line 1: Add one more parameter, row,

Line 8-15: Check if current row index, i, is equal to the target row number, proceed to sum up the array element in that particular row and increment the counter.

5 0
3 years ago
Effective communication skills are a desirable workplace skill
OLga [1]
Yes. If there is no effective communication in the workplace then nothing is going to be done.
4 0
3 years ago
Other questions:
  • Brittany just pulled up a database table with employee information that contains 50 records of employees at her company. Which o
    12·1 answer
  • A user saves a password on a website the user logs into from a desktop. Under which circumstances will the password be saved on
    14·1 answer
  • Study and compare the tables and draw conclusions.
    13·1 answer
  • darren wants to substitute every occurence of the word bulky in his spreadsheet with the word strong. which of these options sho
    9·2 answers
  • In order to plan George’s birthday, his father gave him a list of people who attended his birthday for the last five years. What
    8·1 answer
  • The software used to help run the computer hardware is the _____.
    9·2 answers
  • Unwanted email sent to large groups of people who did not request the communication is called _____
    12·1 answer
  • Write a nested loop to set values as follows: [0] [1] [2] [3] [4] [0] 1 2 3 4 5 [1] 1 2 3 4 5 [2] 1 2 3 4 5 [3] 1 2 3 4 5
    12·1 answer
  • Write code that outputs variable numCats. End with a newline.
    6·1 answer
  • 2. what are the advantages of breaking up a single logical message into a number of fixed-sized packets and then sending each on
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!