We will be referring to the following graph in the questions below S 1 A 3 4 1 2 E I 2 2 ст 5 5 ст F 9 7 H G 6 2 4 8 B C Ꭰ Suppose we start Prim's algorithm from S on this graph. Write down the state of the Priority Queue being used as the fringe after S is visited, after B is visited, and after the algorithm is completed. Each value in the priority queue should be an integer. Resolve ties by alphabetical order of the vertices. For example: if A and C have the same priority, then you should first pop A since it comes alphabetically first. Initialize the priority of each vertex as inf which we'll use to represent ∞. So, before the first iteration, the values of the fringe are: fringe = {S:0, A:inf, B:inf, C:inf, D:inf, E:inf, F:inf, G:inf, H:inf, I:inf} Order your fringe by priority values. You should use the same alphabetical tie-breaking scheme when choosing the order of the fringe. Make sure you include the { and > in your answer. If the fringe is empty, put { }

We will be referring to the following graph in the questions below S 1 A 3 4 1 2 E I 2 2 ст 5 5 ст F 9 7 H G 6 2 4 8 B C Ꭰ Suppose we start Prim's algorithm from S on this graph. Write down the state of the Priority Queue being used as the fringe after S is visited, after B is visited, and after the algorithm is completed. Each value in the priority queue should be an integer. Resolve ties by alphabetical order of the vertices. For example: if A and C have the same priority, then you should first pop A since it comes alphabetically first. Initialize the priority of each vertex as inf which we'll use to represent ∞. So, before the first iteration, the values of the fringe are: fringe = {S:0, A:inf, B:inf, C:inf, D:inf, E:inf, F:inf, G:inf, H:inf, I:inf} Order your fringe by priority values. You should use the same alphabetical tie-breaking scheme when choosing the order of the fringe. Make sure you include the { and > in your answer. If the fringe is empty, put { }

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

If there is an Euler path that starts at AA and ends at some other vertex, give it. Otherwise enter DNE.This should be a list of letters, from A to the other vertex: e.g. ACBDEAD (if that were even possible!). Path: Since this is a planar graph, the number of regions - arcs + nodes equals what number?
We can traverse a graph using recursion. True False
Graph Transversal Simulation: For this graph write down the order of vertices encountered in a breadth-first search starting from vertex A. Break ties by picking the vertices in alphabetical order (for example, A before Z)
Problem: A graph is given. You need to implement BFS traversal to traverse all the nodes of the given graph. Consider the below graph. 2 Start 3 The output should be: Visited 2 Visited 0 Visited 1 Visited 3
Let’s consider there are 6 nodes. The nodes are denoted as A,B,C,D,E,F.The edges are(Remember all the edges are undirected)A->BA->CA->DB->EB->DC->DD->ED->FE->FQ- Draw the graph. Now assign weights.The value of the weights will be my id. my id is 201002259edge values from the starting.For example edge A->B value is 1A->C=2 similarly others and E->F=9From the above graph which you have drawn find the MST using Prim’s algorithm, alsowrite the algorithm and find the complexity using your graph.
4 Write the shortest path length from A to every other node of the above in the Graph and the path component. (e.g. Path A to G: length: 3, consist of: A->C->G) 3 2 2 D F 3 A H. G 4.
True or false: For graphs with negative weights, one workaround to be able to use Dijkstra’s algorithm (instead of Bellman-Ford) would be to simply make all edge weights positive; for example, if the most negative weight in a graph is -8, then we can simply add +8 to all weights, compute the shortest path, then decrease all weights by -8 to return to the original graph. Select one: True False
Part 2 We want to find a valid ordering for a graph or determine that no such ordering exists. We'll use depth-first search to do it. Notice that the pseudocode we've given you has only odd line numbers. We'll adapt DFS to our purpose by adding two even numbered lines. Note: This is DFS in a directed graph. The edge (v, w) is directed from v to w. 19 DFSValid (G) { 21 23 25 27 29 31 33 35 37 } unmark all vertices. unmark all edges for each vertex v { 51 53 55 57 59} if v is unmarked { DFS (G,V) } } return seq 39 DFS (G, v) { 41 mark v 43 for each edge (v,w) { 45 if w is unmarked { 47 49 } mark (v,w) TREE DFS (G,w) } else if (v,w) is unmarked { mark (v,w) NONTREE } Note that seq is a global variable that is initially an empty list. At what even line number should we add add v to front of seq so seq, returned by a call to DFSValid (G), is a valid ordering of G (if one exists)? Line= integer At what even line number should we add if w not in seq then fail so DFS fails if the graph has no…
9.Write the shortest path length from A to every other node of the above in the Graph and the path component. (e.g. Path A to G: length: 3, consist of: A->C->G) B 3 2 2 D F 3 A H. G 2.
3. Kleinberg, Jon. Algorithm Design (p. 519, q. 28) Consider this version of the Independent Set Problem. You are given an undirected graph G and an integer k. We will call a set of nodes I "strongly independent" if, for any two nodes v, u € I, the edge (v, u) is not present in G, and neither is there a path of two edges from u to v. That is, there is no node w such that both (v, w) and (u, w) are present. The Strongly Independent Set problem is to decide whether G has a strongly independent set of size at least k. Show that the Strongly Independent Set Problem is NP-Complete.
Given a graph that is a tree (connected and acyclic). (I) Pick any vertex v.(II) Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance.(III) Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. Consider the path p from w to x. Which of the following are truea. p is the longest path in the graphb. p is the shortest path in the graphc. p can be calculated in time linear in the number of edges/vertices
Question 7 Bot pr O3 A B D. A 21 51 4 59 18 B. 21 38 24 27 60 51 38 26 46 32 D 4 24 26 40 22 59 27 46 40 54 F 60 32 22 54 The weights of edges in a graph are shown in the table above. Apply the sorted edges algorithm to the graph. Give your answer as a list of vertices, starting and ending at vertex A. Example: ABCDEFA Calculator 1,