DSC 40B实验编程辅导、写作algorithm语言程序

” DSC 40B实验编程辅导、写作algorithm语言程序DSC 40B – Homework 07Due: Friday, December 4Write your solutions to the following problems by either typing them up or handwriting them on anotherpiece of paper. Unless otherwise noted by the problems instructions, show your work or provide somejustification for your answer. Homeworks are due via Gradescope on Friday at 11:59 p.m.Problem 1. (Eligible for Redemption)For the following problems, recall that (u, v) is a tree edge if node v is discovered while visiting node uduring a breadth-first or depth-first search. Assume the convention that a nodes neighbors are produced inascending order by label. You do not need to show your work for this problem.a) Suppose a breadth-first search is performed on the graph below, starting at node 1. Mark every BFStree edge with a bold arrow emanating from the predecessor.1 2 34 5 67 8 9b) Suppose a depth-first search is performed on the graph below, starting at node 1. Mark every DFStree edge with a bold arrow emanating from the predecessor.1 2 34 5 67 8 91c) Fill in the table below so that it contains the start and finish times of each node after a DFS isperformed on the above graph using node 1 as the source. Begin your start times with 1.Node Start FinishProblem 2. (Eligible for Redemption)Draw a directed graph With three nodes u, v, w such that: 1) v is reachable from u; 2) in a DFS started atw, the finish time of v is larger than the finish time of node u.Problem 3. (Eligible for Redemption)Run Bellman-Ford on the following graph using node s as the source. Below each node u, write the shortestpath length from s to u. Mark the predecessor of u by highlighting it or making a bold arrow.2Problem 4.Topologically sort the vertices of the following graph. Note that there may be multiple, equally-correcttopological sorts.1 2 34 5 67 8 9Programming Problem 1.You are given a directed graph representing a tree and a dictionary value which contains a value for eachnode. Define the biggest descendent value of a node u to be the largest value of any node which is a descendentof u in the tree (for this problem, you should consider u to be a descendent of itself.For instance, given the following tree where each nodes label is replaced by its value:In a file named biggest_descendent.py, write a function biggest_descendent(graph, root, value)3which accepts the Graph, the label of the root node, and the dictionary of values and computes a dictionarymapping each node in the graph to its biggest descendent value.The input graph will be an instance of dsc40graph.DirectedGraph().Programming Problem 2.In a file named modified_Bellman_ford.py, create a function modified_bellman_ford(graph, weights, source)which takes in the same arguments as the function from lecture and returns one thing: the dictionary of estimateddistances. But unlike the function in lecture, your function should set est[v] = -float(infty)if there is a negative cycle anywhere along the path from the source to node v.Programming Problem 3.In a file named make_change.py, create a function named make_change(amount) which returns the numberof ways of making Amount dollars out of pennies, nickels, dimes, and quarters.For example, there are 4 ways of making amount = 0.10 (ten cents): ten pennies, five pennies and onenickel, two nickels, and one dime.Hint: This can be solved by modifying a graph algorithm that we have learned! But there is no graphmentioned in the problem above… Youll need to model this problem as a graph problem. What are thenodes? What are the edges? What algorithm should be modified?如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“