Determine the longest unweighted path

Assignment Help Basic Computer Science

Reference no: EM13968302

1. When a vertex and its incident edges are removed from a tree, a collection of sub- trees remains. Give a linear-time algorithm that ?nds a vertex whose removal from an N vertex tree leaves no subtree with more than N/2 vertices.

2. Give a linear-time algorithm to determine the longest unweighted path in an acyclic undirected graph (that is, a tree).

3. Consider an N-by-N grid in which some squares are occupied by black circles. Two squares belong to the same group if they share a common edge. In Figure 9.88, there is one group of four occupied squares, three groups of two occupied squares, and two individual occupied squares. Assume that the grid is represented by a two-dimensional array. Write a program that does the following:

a. Computes the size of a group when a square in the group is given.

b. Computes the number of different groups.

c. Lists all groups.

Reference no: EM13968302

Questions Cloud

How big is your protein footprint : How big is your protein footprint? Does a meat-rich diet have a negative impact on our environment? Does it contribute to global warming?

Algorithm to solve version of the problem : Suppose that walls in the maze can be knocked down, with a penalty of P squares. P is speci?ed as a parameter to the algorithm. (If the penalty is 0, then the problem is trivial.) Describe an algorithm to solve this version of the problem. What is..

Define evangeliam as it occurs in acts : Read all of the biblical book of Acts with reference the book "The Mystical Way of Evanglism" by Heath's , I need you to read in the content of thier good news relationship between DEED AND WORD. Define evangeliam as it occurs in Acts

Strategic issues analysis of a global company : Strategic Issues Analysis of a Global Company - while this is the strategy that I most admire of the Starbucks Corporation, it is also the first topic that comes to mind when asked about a major strategic issue they are currently facing: How do the..

Determine the longest unweighted path : 1. When a vertex and its incident edges are removed from a tree, a collection of sub- trees remains. Give a linear-time algorithm that ?nds a vertex whose removal from an N vertex tree leaves no subtree with more than N/2 vertices. 2. Give a linear..

Problem regarding the polynomial-time algorithm : Give a polynomial-time algorithm that ?nds rV/21 vertices that collectively cover at least three-fourths (3/4) of the edges in an arbitrary undirected graph.

Design a linear algorithm : Let G = (V, E) be an undirected graph. Use depth-?rst search to design a linear algorithm to convert each edge in G to a directed edge such that the resulting graph is strongly connected, or determine that this is not possible.

How a business should be managed may sound attractive : The stakeholder view of how a business should be managed may sound ethically attractive but could be too simplistic.

How would you respond to the director of visitor''s bureau : In light of the city's fiscal problems, what is the most likely motivation for the new charge? Will the new overhead charge achieve its objective?

User Account

All Pages