Ask Question, Ask an Expert

+61-413 786 465

info@mywordsolution.com

Ask Computer Engineering Expert

Question :

Suppose we are given a "chain" of n nodes as shown below. Each node i is "neighbors" with the node to its left and the node to its right (if they exist).

An independent set of these nodes is a subset of the nodes such that no two of the chosen nodes are neighbors. In the below example, the first and fourth vertices form an independent set, but the first, third, and fourth vertices do not (because the third and fourth are neighbors). Now suppose each node has a positive weight.

We are interested in computing an independent set such that the sum of the weights of the chosen nodes are as large as possible. In the example, the optimal solution is to choose the second and fourth vertices for a weight of 30.

(15) - (20) - (7) - (10)

(a) A natural attempt of a greedy algorithm for this problem is to take the vertex with the largest weight, then delete that vertex's neighbors (because they cannot also be in an independent set). Repeat this process until there are no more vertices which can be included. Give a counterexample which shows that this algorithm may not give an optimal solution.

(b) Let a[i] denote the weight of a maximum-weight independent set when only considering the first i vertices of the path. Give the values a[1], a[2], a[3], and a[4] for the example given above.

(c) Define a recursive definition of a[i]. Don't forget the base case.

(d) Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M93128711

Have any Question? 


Related Questions in Computer Engineering

Question 1 identify all the dfd data flow diagram elements

Question: 1. Identify all the DFD (data flow diagram) elements (Shostack, 2014, p.531.). 2. Identify all threat types to each element(Shostack, 2014, p.531.). 3. Identify threats (three or more), one each for data flow, ...

Question 1 identify the three main types of computer

Question: 1. Identify the three main types of computer software that were discussed in your unit lesson. Within the three main categories, give examples of each and a brief explanation of each. Each explanation/descripti ...

Question introduction to management information systemsread

Question: Introduction to Management Information Systems Read at least three (3) academically reviewed articles on Management Information Systems and complete the following activities: (Wikipedia articles will not be acc ...

Question suppose you had to design a wired ethernet network

Question : Suppose you had to design a wired Ethernet network for a 4-story office building containing 20 users per floor. Each floor is 90 meters in length and 5 meters in height. Draw a network topology of your propose ...

Taylor found that 8 of the recipients of loans from a

Taylor found that 8% of the recipients of loans from a particular mortgage lending institute default within the first 3 years. If he takes a random sample of 4 customers, who received loans 3 years ago, what is the proba ...

A balloon has 050 mol ar at 175 k 0997 atm and 0775 l if

A balloon has 0.50 mol Ar at 175 K, 0.997 atm and 0.775 L. If the moles are doubled and the temperature dropped to 115 K at constant pressure, what would the volume (in L) be?

Question critical infrastructures -1discuss cybersecurity

Question: Critical Infrastructures - 1. Discuss cybersecurity policy issues affecting SCADA and ICS systems for Critical Infrastructure services for the public, and compare those issues to the policy issues that affect t ...

Question draw a map labeling every aspect which represents

Question: Draw a map, labeling every aspect, which represents how IP addressing works with DNS servers to process a request for a web page from your computer that returns the web page.Using tracert from your terminal ent ...

Question suppose you want to perform two sums one is a sum

Question : Suppose you want to perform two sums: one is a sum of 10 scalar variables, and one is a matrix sum of a pair of two-dimensional arrays, with dimensions 10 by 10. What speed-up do you get with 10 versus 100 pro ...

In 2005 team dad used a toyota truck with a system of

In 2005, Team DAD used a Toyota truck with a system of spinning lasers as its "visual" system. What advantages and or disadvantage does such a system have compared to camera-based systems?

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As