3. Consider the problem of counting, in a given text, the number of strings that

Question

3. Consider the problem of counting, in a given text, the number of strings that start with Y and end with Z. For example, for the string Y AZY Z, there are three such substrings. Design a brute-force algorithm for this problem and determine its efficiency class.

4. Given a graph G(V, E) with vertices V and edges E, provide pseudocode for an exhaustive-search algorithm that determines whether or not a Hamiltonian path, a path that uses every vertex in the graph exactly once, exists for G. Determine the complexity of such algorithm as well.

Explanation / Answer

Solution for Question 1:
This below algortim will check the string is started with y and ended with z..will return true else return false

var string = "Y AZY Z"
VAR index = 0
var equal, equal1
var count = 0

if string[0] == 'Y' || 'y'
equal = true
else
equal = False
while string[i] != ''
string[i++]
count++;

if string[count-1]== 'Z' || 'z'
equal1 = true
else
equal1 = false

if equal == True && equal1 == True
print "String has started with y and ended with z"
else
print "Not Equal"

Solution for Question 2:

select a neighboring vertex at random, remove one of its existing edges (in a Hamiltonian path there can be only two edges from any single vertex), then draw a new edge from your current vertex to this now available randomly selected one. You then trace from the randomly selected vertex to the end of the graph (the first vertex that has only a single edge leaving it) and continue the algorithm.

Graph graph;
Vertex current;
Path path;

while(!IsHamiltonian(path))
{
if(HasUnvisitedNeighbor(current, path))
{
Vertex next = SelectRandomUnvisited(current, path);
DrawEdgeTo(next, current, path);
current= next;
}
else
{
Vertex next = SelectRandomNeighbor(current, path);
RemoveRandomEdgeFrom(next, path);
DrawEdgeTo(next, current, path);
path = FindEnd(next, current, path); //Finds the end of the path, starting from next, without passing through current
}
}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.