5.04-2. Bellman Ford Algorithm (1, part 2). Consider the scenario shown below, where at t=1, node e receives distance vectors from neighboring nodes d, b, h and f. The (old) distance vector at e (the node at the center of the network) is also shown, before receiving the new distance vector from its neighbors. Indicate which of the components of new distance vector at e below have a value of 2 after e has received the distance vectors from its neighbors and updated its own distance vector. (Note: You can find more examples of problems similar to this here DV in b: Dola) = 8 Do(f) = 00 Do(c) = 1 Dolg) = 00 Do(d) = 00 D,(h) = 00 Dole) = 1 D,li) = 00 old DV at e at t=1 e receives DVs from b, d, f, h DV in e: %3D DV in d: %3! Dela) = 00 D.(b) = 1 Delc) = 00 De(d) = 1 Dele) = 0 De(f) = 1 Delg) = De(h) = 1 Deli) = 00 Dala) = 1 00 = (9)'a a. Da(c) = 0 Dald) = 0 Dale) = 1 Dalf) = 00 Dalg) = 1 Da(h) = 00 Dali) = 00 8 1 Q: what is new DV computed in e at t=1? 1 = 00 compute- f- DV in f: 1 DV in h: Dn(a) = 00 Dn(b) = 00 Dr(c): Dn(d) = 00 Dn(e) = 1 Dn(f) = 00 Dg) = 1 D,(h) = 0 Dn(i) = 1 DAa) = 00 D(b) = 00 DAC): D{d) = D(e) = 1 DAf) = 0 DAg) = 00 D(h) : DAi) = 1 = 00 = 00 1 1 = 00 g- 1 1 = 00 %3D

5.04-2. Bellman Ford Algorithm (1, part 2). Consider the scenario shown below, where at t=1, node e receives distance vectors from neighboring nodes d, b, h and f. The (old) distance vector at e (the node at the center of the network) is also shown, before receiving the new distance vector from its neighbors. Indicate which of the components of new distance vector at e below have a value of 2 after e has received the distance vectors from its neighbors and updated its own distance vector. (Note: You can find more examples of problems similar to this here DV in b: Dola) = 8 Do(f) = 00 Do(c) = 1 Dolg) = 00 Do(d) = 00 D,(h) = 00 Dole) = 1 D,li) = 00 old DV at e at t=1 e receives DVs from b, d, f, h DV in e: %3D DV in d: %3! Dela) = 00 D.(b) = 1 Delc) = 00 De(d) = 1 Dele) = 0 De(f) = 1 Delg) = De(h) = 1 Deli) = 00 Dala) = 1 00 = (9)'a a. Da(c) = 0 Dald) = 0 Dale) = 1 Dalf) = 00 Dalg) = 1 Da(h) = 00 Dali) = 00 8 1 Q: what is new DV computed in e at t=1? 1 = 00 compute- f- DV in f: 1 DV in h: Dn(a) = 00 Dn(b) = 00 Dr(c): Dn(d) = 00 Dn(e) = 1 Dn(f) = 00 Dg) = 1 D,(h) = 0 Dn(i) = 1 DAa) = 00 D(b) = 00 DAC): D{d) = D(e) = 1 DAf) = 0 DAg) = 00 D(h) : DAi) = 1 = 00 = 00 1 1 = 00 g- 1 1 = 00 %3D

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

5.04-3. Bellman Ford Algorithm - a change in DV (1, part 3). Consider the network below, and suppose that at t=0, the link between nodes g and h goes down. And so at t=0, nodes g and h recompute their DVs. Following this recomputation, to which nodes will h send its new distance vector? (Note: to answer this question, you'll need to know some of the DV entries at g and h at t=0, but hopefully they'll be obvious by inspection). a 1 1 at t=0 the link (with a cost of 6) between nodes g and h goes down b. compute ∞ g all nodes 8 1 6 1 e 1 compute h 1 1 1 1 node i only nodes i and e only O node h does not send out its distance vector, since none of the least costs have changed to any destination. O nodes i and e and g only node e only
5.04-3. Bellman Ford Algorithm - a change in DV (1, part 3). Consider the network below, and suppose that at t=0, the link between nodes g and h goes down. And so at t=0, nodes g and h recompute their DVs. Following this recomputation, to which nodes will h send its new distance vector? (Note: to answer this question, you’ll need to know some of the DV entries at g and h at t=0, but hopefully they’ll be obvious by inspection).
5.04-4. Bellman Ford Algorithm - a change in DV (1, part 4). Consider the network below, and suppose that at t=0, the link between nodes b and c goes down. And so at t=0, node b recomputes its distance vector (DV) and sends out its new DV (as needed). At t=1 this new DV is received at b's neighbors, who then perform their calculation and send out their new DVs (as needed); these new DVs arrive at their neighbors at t=2, and so on. What is the last time in this network at which a DV calculation will take place as a result of the link change at t=0? U O O o 1 1 3 2 at t=0 the link (with a cost of 1) between nodes b and c goes down A 8 1 6 compute 1 1 1 1 an essentially infinite amount of time; this is the count-to-infinity problem 1 Second
5.04-4. Bellman Ford Algorithm - a change in DV (1, part 4). Consider the network below, and suppose that at t=0, the link between nodes b and c goes down. And so at t=0, node b recomputes its distance vector (DV) and sends out its new DV (as needed). At t=1 this new DV is received at b's neighbors, who then perform their calculation and send out their new DVs (as needed); these new DVs arrive at their neighbors at t=2, and so on. What is the last time in this network at which a DV calculation will take place as a result of the link change at t=0? O a 1 1 ♡ g at t=0 the link (with a cost of 1) between nodes b and c goes down 8 1 6 compute 1 1 -h- 1 1 1 an essentially infinite amount of time; this is the count-to-infinity problem
5.04-4. Bellman Ford Algorithm - a change in DV (1, part 4). Consider the network below, and suppose that at t=0, the link between nodes b and c goes down. And so at t=0, node b recomputes its distance vector (DV) and sends out its new DV (as needed). At t=1 this new DV is received at b's neighbors, who then perform their calculation and send out their new DVs (as needed); these new DVs arrive at their neighbors at t=2, and so on. What is the last time in this network at which a DV calculation will take place as a result of the link change at t=0? a. 1 1 at t=0 the link (with a cost of 1) between nodes b and c goes down 2 8 1 6 b- compute 1 e 1 -h- 1 1 an essentially infinite amount of time; this is the count-to-infinity problem 1 Not quote. This answer is incorrect.
In a network of N nodes, how many iterations are required for Dijkstra's algorithm to completes its execution. Hint: Section 5.2.1 has the pseudo code for Dijkstra's link state algorithm that finds the shortest path from a source node to every node in the network. Professor Kurose shows the pseudo code in his video. The pseudo code in the text shows an initialization step and then a loop. How many times would the loop be executed for a network of N nodes? O N+1 times ON-1 times ON times O N² times
5.03-3. Dijkstra's Algorithm (3, part 3). Consider the network shown below, and Dijkstra’s link-state algorithm. Here, we are interested in computing the least cost path from node E to all other nodes using Dijkstra's algorithm. Using the algorithm statement used in the textbook and its visual representation, complete the "Step 2" row in the table below showing the link state algorithm’s execution by matching the table entries (i), (ii), (iii), (iv) and (v) with their values.
5.03-3. Dijkstra's Algorithm (3, part 3). Consider the network shown below, and Dijkstra's link-state algorithm. Here, we are interested in computing the least cost path from node E to all other nodes using Dijkstra's algorithm. Using the algorithm statement used in the textbook and its visual representation, complete the "Step 2" row in the table below showing the link state algorithm's execution by matching the table entries (i), (ii), (iii), (iv) and (v) with their values. Write down your final [correct] answer, as you'll need it for the next question. Step (i) (iii) (iv) (v) A 012 3 2 4 (В 8 D N' E (i) 4 10 4 E 4 (ii) 2 F A D(A),p(A) D(B [Choose ] 6,F 1,E 8,F 4,E EFB 8,D 6,D EFD 9,D [Choose ] [Choose ] [Choose ] [Choose ] [Choose ] < F D(F),p(F) 2,E
5.06-1. Bellman Ford Algorithm (3, part 1). Consider the grid network shown below. All links have a cost of 1. Let's focus on the distance vector (DV) in node L. A (B (E) (K) DL(G) H (M) W X Y When the DV algorithm first begins, what are the initial values of the DV entries in node L for destinations G and H? Enter these components of L's initial DV,below by matching a DV entry to its value in the pull-down menu. DL(H) R [Choose ] [Choose ] 1 OT 0 2 infinity
5.01-1. Dijkstra's Algorithm (1, part 1). Consider the network shown below, and Dijkstra's link-stat algorithm to find the least cost path from source node U to all other destinations. Using the algorithm statement and its visual representation used in the textbook, complete the first row in the table below showing the link state algorithm's execution by matching the table entries (a), (b), (c), an (d) with their values. Write down your final [correct] answer, as you'll need it for the next question. Step 0 (a) (b) (c) (d) 3 8 V 2 X N' u 4 2 6 -W 3 D(v),p(v) D(v).p(v) (a) 1 SZ 1 W X D(w),p(w) D(x).p(x) (b) (c) [Choose ] [Choose ] 5,x 6,v 3,u 4,v 1,u 8,u 2,u infinity 7,u [Choose ] Z D(y).p(y) D(z).p(z) (d) ∞
PLEASE USE PYTHONGiven a jungle matrix NxM:jungle = [ [1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1,]]Where 0 means the block is dead end and 1 means the block can be used in the path fromsource to destination.Task:Starting at position (0, 0), the goal is to reach position (N-1, M-1).Your program needs to build and output the solution matrix – a 4x4 matrix with 1’s inpositions used to get from the starting position (0,0) to the ending position (N-1,M-1)with the following constraints:You can only move one space at a timeYou can only in two directions: forward and down.You can only pass thru spaces on the jungle matrix marked ‘1’If you cannot reach the ending position – print a message that you’re trapped in thejungleAlgorithm:If destination is reachedprint the solution matrixElseMark current cell in the solution matrixMove forward horizontally and recursively check if this leads to a solution If there is no solution, move down and recursively check if this leads to a solution If…
a. Build an adjacency matrix ? for this map. b. How many paths of length 2 from V5 to V1 exist? c. How many paths of length 3 from V5 to V1 exist?