Homework Answers
5)The 2 goals are :
A) Time taken to perform the search should be minimum , algorithm should have best possible case of time complexity.
B) The search must be efficient and accurate .Also it should be space efficient and use the necessary space only for execution.
6) BFS : Breadth first search , it is slower ,need more memory and uses FIFO implementation using queue data structure. It is used for finding the shortest path .
DFS : Depth first search , it is faster , need less memory and uses LIFO implementation using Stack data structure. It is used for examination of connected graphs and is not optimal for finding shortest path .
7) 
Add Answer to:
5) When designing a search algorithm what are two goals? 6) What is the difference between...
LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents th...
JAVA
LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents the graph. Your code should contain a function called addEdgelint i, int j). Use this function to add the appropriate edges in your matrix. Write code to implement Depth-First-Search (DFS) and Breadth-First-Search (BFS) of your graph. Let 0 be the source Node . Traverse the graph using DFS, print the Nodes as they are visited. . Traverse the...
5. For the following graph, (a) In what order will the nodes be visited using a...
5. For the following graph, (a) In what order will the nodes be visited using a Depth First Search? (5 points) (b) In what order will the nodes be visited using a Breadth First Search? (5 points) (Note: if A connects B and D, the node A visits B first and then considers D.)
What is the deference between A* search algorithm, Greedy best first search algorithm and hill climing...
What is the deference between A* search algorithm, Greedy best first search algorithm and hill climing algorithm ? What is the difference between FDS,BFS, uniform cost search, and iterative deepeneng depth search ?
(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void...
(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void breadthFirstSearch (vertex w) for all vertices u num (u) 0 null edges i=1; num (w) i++ enqueue (w) while queue is not empty dequeue ( V= for all vertices u adjacent to v if num(u) is 0 num (u) = i++; enqueue (u) attach edge (vu) to edges; output edges; Now consider the following graph. Give the breadth-first traversal of the graph, starting from...
Problem 5. (Lexicographical Optimisation with Paths) Provide pseudocode and an expla- nation for an algorithm that comp...
Problem 5. (Lexicographical Optimisation with Paths) Provide pseudocode and an expla- nation for an algorithm that computes a path between two nodes in an undirected graph such that: . The maximum weight in the path is minimised, ie., there does not exist another path with a smaller maximum weight .Amongst all such paths, it finds the path with minimum cost. . The time complexity is no worse than 0(( and V is the set of nodes. ·IvD-log(IVD), where E is...
1) Consider the directed graph below. “S” is the start state and “G1,G2,G3” are 3 goal...
1) Consider the directed graph below. “S” is the start state and “G1,G2,G3” are 3 goal states. In traversing the graph one can move only in the direction indicated by the arrows. The numbers on the edges indicate the step-cost for traversing that edge. The numbers in the nodes represent the estimated cost to the nearest goal state. In the following you will be asked to search this graph using various search strategies. When you work out your answer, please...
please answer one of the two 1. (25) [Single-source shortest-path: algorithm tracing] Show the tracing of...
please answer one of the two
1. (25) [Single-source shortest-path: algorithm tracing] Show the tracing of Dijkstra's shortest path search algorithm on the weighted directed graph shown below. Do the tracing it twice, first starting with the nodes and, second, starting with the node z. For each tracing, each time the shortest path to a new node is determined, show the graph with the shortest path to the node clearly marked and show inside the node the shortest distance to...
(c) Simulate breadth first search on the graph shown in Fig HW2Q1c. You can assume that...
(c) Simulate breadth first search on the graph shown in Fig
HW2Q1c. You can assume that the starting vertex is 1, and the
neighbors of a vertex are examined in increasing numerical order
(i.e. if there is a choice between two or more neighbors, we pick
the smaller one). You have to show: both the order in which the
vertices are visited and the breadth first search tree. No
explanations necessary.
(d) On the same graph, i.e. the graph in...
The following graph has been analyzed by a depth-first search. Draw the resulting depth-first forest. 27. Identify the algorithm that gives the following Information about the structure of a...
The
following graph has been analyzed by a depth-first search. Draw the
resulting depth-first forest.
27. Identify the algorithm that gives the following Information about the structure of a graph Information about the length of paths between ve 28. The following graph has been analyzed by a d Draw the resulting depth-first forest. 3/6 2/9 1/10 B. 1213 7/8 What is the meaning of the notation ".11/16" on node t timestamp earch 28. The following graph has been analyzed by...
Please answer all three parts. And show step-by-step answers for each part. Draw anything if necessary....
Please answer all three parts. And show step-by-step
answers for each part. Draw anything if necessary. And
please don't copy other answers to be at risk being downvoted.
Thank you.
Question 1 (50 POINTS): Given a graph G and the Breadth First Search (BFS) and Depth First Search (DFS) traversal algorithms as follows: BFSG) 1 for each vertex u € G.V – {3} 1 2 u.color = WHITE 3 u.d = 0 4 un = NIL 3 5 S.color =...
JAVA
LAB 1 2 5 7 6 9 3 8 . Write code to implement an adjacency matrix (2d matrix) which represents the graph. Your code should contain a function called addEdgelint i, int j). Use this function to add the appropriate edges in your matrix. Write code to implement Depth-First-Search (DFS) and Breadth-First-Search (BFS) of your graph. Let 0 be the source Node . Traverse the graph using DFS, print the Nodes as they are visited. . Traverse the...
5. For the following graph, (a) In what order will the nodes be visited using a Depth First Search? (5 points) (b) In what order will the nodes be visited using a Breadth First Search? (5 points) (Note: if A connects B and D, the node A visits B first and then considers D.)
(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void breadthFirstSearch (vertex w) for all vertices u num (u) 0 null edges i=1; num (w) i++ enqueue (w) while queue is not empty dequeue ( V= for all vertices u adjacent to v if num(u) is 0 num (u) = i++; enqueue (u) attach edge (vu) to edges; output edges; Now consider the following graph. Give the breadth-first traversal of the graph, starting from...
Problem 5. (Lexicographical Optimisation with Paths) Provide pseudocode and an expla- nation for an algorithm that computes a path between two nodes in an undirected graph such that: . The maximum weight in the path is minimised, ie., there does not exist another path with a smaller maximum weight .Amongst all such paths, it finds the path with minimum cost. . The time complexity is no worse than 0(( and V is the set of nodes. ·IvD-log(IVD), where E is...
please answer one of the two
1. (25) [Single-source shortest-path: algorithm tracing] Show the tracing of Dijkstra's shortest path search algorithm on the weighted directed graph shown below. Do the tracing it twice, first starting with the nodes and, second, starting with the node z. For each tracing, each time the shortest path to a new node is determined, show the graph with the shortest path to the node clearly marked and show inside the node the shortest distance to...
(c) Simulate breadth first search on the graph shown in Fig
HW2Q1c. You can assume that the starting vertex is 1, and the
neighbors of a vertex are examined in increasing numerical order
(i.e. if there is a choice between two or more neighbors, we pick
the smaller one). You have to show: both the order in which the
vertices are visited and the breadth first search tree. No
explanations necessary.
(d) On the same graph, i.e. the graph in...
The
following graph has been analyzed by a depth-first search. Draw the
resulting depth-first forest.
27. Identify the algorithm that gives the following Information about the structure of a graph Information about the length of paths between ve 28. The following graph has been analyzed by a d Draw the resulting depth-first forest. 3/6 2/9 1/10 B. 1213 7/8 What is the meaning of the notation ".11/16" on node t timestamp earch 28. The following graph has been analyzed by...
Please answer all three parts. And show step-by-step
answers for each part. Draw anything if necessary. And
please don't copy other answers to be at risk being downvoted.
Thank you.
Question 1 (50 POINTS): Given a graph G and the Breadth First Search (BFS) and Depth First Search (DFS) traversal algorithms as follows: BFSG) 1 for each vertex u € G.V – {3} 1 2 u.color = WHITE 3 u.d = 0 4 un = NIL 3 5 S.color =...
Most questions answered within 3 hours.
-
The energy required to remove an electron from a surface of a
solid element is called...
asked 38 minutes ago -
How would you train your employees to avoid risks of using
mobile devices?
asked 1 hour ago -
Assume Kw = 1.01 ✕ 10−14
For pure water, we can calculate [H3O+ ] = [OH...
asked 1 hour ago -
Suppose that on a temperature scale X, water boils at 203.0°X
and freezes at -105.7°X. What...
asked 2 hours ago -
BaS crystallizes in a cubic unit cell with S2- ions on each
corner and each face....
asked 3 hours ago -
A. 0≤P(Oi)≤10≤P(Oi)≤1 for each i
B. P(Oi)≤0P(Oi)≤0
C. P(Oi)=1+P(OCi)P(Oi)=1+P(OiC)
D. P(Oi)≥1P(Oi)≥1
If an experiment consists of...
asked 4 hours ago -
A battery has an emf of 9.20V and an internal resistance of 1.20
ohm. a)What resistance...
asked 4 hours ago -
The area of an elastic circular loop decreases at a constant
rate, dA/dt = −6.60×10−3 m2/s...
asked 5 hours ago -
The denaturation of proteins can be described by the
equilibrium
F⇌U
where F and U represent...
asked 7 hours ago -
Please answer what the maximum and minimum force is, and the
angle on the ion is...
asked 7 hours ago -
implement a program that reads a number of rows and a symbol.
The program will draw...
asked 7 hours ago -
Assume that when adults with smartphones are randomly selected,
45% use them in meetings or classes....
asked 7 hours ago