Homework 2
homework | Algorithm – 这个题目属于一个Algorithm的代写任务, 是比较有代表性的Algorithm等代写方向, 这个项目是homework代写的代写题目
Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed or not compliant with the specification. Submit your homework via Blackboard as one PDF or Word document. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
- ( 25 ) [Depth-first search: Algorithm tracing] Consider the recursive depth-first search algorithm, the graph, and its adjacency list representation shown below. Consider the nodes in a linked list of the adjacency list in the order from left to right exactly as shown. Do algorithm tracing on the graph twice, once for the start vertex 2 and once for the start vertex 6, and show the tracing output. The tracing output should include the sequence of recursive calls and returns from those calls in the following format: call DFS(a); call DFS(b); call DFS(c); return from DFS(c); call DFS(d); return from DFS(d); return from DFS(b); return from DFS(a). Additionally, show the depth-first search tree resulting from each run of the algorithm; use the format shown in Figure 3.5(g) of the textbook (page 85). Note this is not a programming exercise.
- (25) [Connected graph with a distant node pair] Textbook Exercise 9 in Chapter 3. Use the BFS algorithm as the base of your algorithm design. Consider the following hints to prove the existence of a hot spot node v without which there is no path between two distant nodes s and t: (i) BFS always finds the shortest path to every node from the source; (ii) the shortest path
length to any node equals the number of BFS layers to the layer containing the node; (iii) property (3.4) on page 81 of the textbook.
Last modified: January 25, 2019