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
FromTheMoon [43]
3 years ago
10

Choose a problem that lends to an implementation that uses dynamic programming. Clearly state the problem and then provide high-

level pseudocode for the algorithm. Explain why this algorithm can benefit from dynamic programming. Try to choose an algorithm different from any already posted by one of your classmates.
Computers and Technology
1 answer:
Svetradugi [14.3K]3 years ago
8 0

Answer:

Explanation:

The maximum weighted independent collection of vertices in a linear chain graph is a straightforward algorithm whereby dynamic programming comes in handy.

Provided a linear chain graph G = (V, E, W), where V is a collection of vertices, E is a set of edges margins, and W is a weight feature function applied to each verex.  Our goal is to find an independent collection of vertices in a linear chain graph with the highest total weight of vertices in that set.

We'll use dynamic programming to do this, with L[k] being the full weighted independent collection of vertices spanning from vertex 1 \to vertex k.

If we add vertex k+1 at vertex k+1, we cannot include vertex k, and thus L[k+1] would either be equivalent to L[k] when vertex k+1 is not being used, or L[k+1] = L[k-1] + W[k+1] when vertex k+1 is included.

Thus, L[k+1] = max \{ L[k], \ L[k-1] + W[k+1] \}

As a result, the dynamic programming algorithm technique can be applied in the following way.

ALGO(V, W, n) // V is a linearly ordered series of n vertices with such a weight feature W

\text{1. L[0] = 0, L[1] = W[1], L[2] = max{W[1], W[2]} //Base cases} \\ \\ \text{2. For i = 3 to n:- \\} \\ \\\text{3........ if ( L[i-1] > L[i-2] + W[ i ] )} \\ \\ \text{4............Then L[ i ] = L[i-1]} \\ \\ \text{5.........else} \\ \\ \text{6................L[i] = L[i-2] + W[i] }\\ \\ \text{7. Return L[n] //our answer.}

As a result, using dynamic programming, we can resolve the problem in O(n) only.

This is an example of a time-saving dynamic programming application.

You might be interested in
Program 7 - Circle You write ALL the code, then run it - Produce the correct output. Turn in code and screen print of successful
fgiga [73]

Answer:

Here is the Circle class:

public class Circle {   // class definition

private int radius;    // private data member of type int of class Circle named radius that stores the value of radius

public Circle(int r) {   // parameterized constructor of class Circle that takes radius as argument

 radius = r;  }    // sets value of radius as r

public int getRadius() {   // accessor method to get the value of radius

 return radius;  }   // returns the current value of radius

public int Diameter() {   // method to compute diameter of a circle

 return radius * 2;  }   // multiply radius value by 2 to compute diameter of Circle

 

public double Area() {   // method to compute area of a circle

 return Math.PI  * Math.pow(radius, 2);   }   //the formula of area is

π x radius² where value of π is get using Math.PI

 

 public double Circumference() {   // // method to compute circumference of a circle

 return 2* Math.PI * radius;   }   }  //the formula of circumference is

2 x π x radius where value of π is get using Math.PI

Explanation:

Here is the Main class:

import java.util.Scanner;  //to accept input from user

public class Main {  //definition of Main class

public static void main(String[] args) {  //start of main method

   

    Scanner scanner = new Scanner (System.in);  //creates Scanner object to take input from user

    System.out.println("Enter radius: ");  //prompts user to enter radius

    int r = scanner.nextInt();  //reads the value of radius from user

 Circle c = new Circle(r);  // calls Constructor of Circle passing r as argument to it using the object c of class Circle

 

    if(c.getRadius()<=0){  //calls getRadius method to get current value of radius using objec and checks if this value (input value of r ) is less than or equal to 0

        System.out.println("Error!");   }  //when above if condition evaluates to true then print this Error! message

    else {  //if the value of radius is greater than 0

System.out.println("the radius of this Circle is: " +c.getRadius());  //calls getRadius method to return current value of r (input value by user)

System.out.println("the diameter of this Circle  is: " + c.Diameter());  //calls Diameter method to compute the diameter of Circle and display the result on output screen

System.out.printf("the circumference of this Circle  is: %.2f", c.Circumference());  //calls Circumference method to compute the Circumference of Circle and display the result on output screen

System.out.println();  //prints a line

System.out.printf("the Area of this Circle  is: %.2f", c.Area()); } }  }

//calls Area method to compute the Area of Circle and display the result on output screen

The program and its output is attached.

7 0
4 years ago
Since technology has advanced so much in the last 20 years, how has it impacted televisions?
kherson [118]

Answer:

Television began to have better graphics, and usually thinner. Television also gained a lot of new features of the years as the technology in the world got better

Explanation:

5 0
4 years ago
Meaning of computer care​
lara31 [8.8K]

Looking after computer

5 0
4 years ago
Write a program that gets five integer test scores from the user, calculates their average, and prints it on the screen. Test yo
Alex

Answer:

total = 0

for i in range(5):

   score = int(input("Enter a score: "))

   total += score

average = total / 5

print("The average is " + str(average))

Explanation:

*The code is in Python.

Initialize the total as 0

Create a for loop that iterates five times. Inside the loop, ask the user to enter a score. Add the score to the total (cumulative sum)

After the loop, calculate the average, divide the total by 5

Print the average

5 0
3 years ago
Method does not override or implement a method from a supertype
muminat
Where is the question? if there was a question i could potentially help you.
4 0
3 years ago
Other questions:
  • a. Is there any functional difference between the class being instantiated in the following two ways? Balanced bal = new Balance
    15·1 answer
  • 6.67
    5·1 answer
  • ___________is a security strategy that applies multiple layers of defense because there is an assumption that any single protect
    12·1 answer
  • The leader in student travel who provides educational tours at affordable prices is called?
    8·1 answer
  • To calculate perimeter of a rectangle​
    9·2 answers
  • What is the final amount stored in value if the computer selects 17 as the
    12·1 answer
  • A website for a certain political party or candidate is likely to have unbiased
    6·1 answer
  • Join the class <br> The class code is hello112
    5·2 answers
  • Which of the following is a quality of a mixed economy?
    5·1 answer
  • Which key doesn't relate to keyboard A:return key B :enrollment key C: delete key D:tab key
    9·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!