DSC 40B编程辅导、讲解algorithm语言程序、辅导Python设计程序辅导Database|讲解R语言程序

项目预算：开发周期：发布时间：要求地区：

DSC 40B - Homework 07
Due: Friday, December 4
Write your solutions to the following problems by either typing them up or handwriting them on another
piece of paper. Unless otherwise noted by the problem’s instructions, show your work or provide some
justification 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 u
during a breadth-first or depth-first search. Assume the convention that a node’s neighbors are produced in
ascending 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 BFS
tree edge with a bold arrow emanating from the predecessor.
1 2 3
4 5 6
7 8 9
b) Suppose a depth-first search is performed on the graph below, starting at node 1. Mark every DFS
tree edge with a bold arrow emanating from the predecessor.
1 2 3
4 5 6
7 8 9
1
c) Fill in the table below so that it contains the start and finish times of each node after a DFS is
performed on the above graph using node 1 as the source. Begin your start times with 1.
Node Start Finish
Problem 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 at
w, 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 shortest
path length from s to u. Mark the predecessor of u by highlighting it or making a bold arrow.
2
Problem 4.
Topologically sort the vertices of the following graph. Note that there may be multiple, equally-correct
topological sorts.
1 2 3
4 5 6
7 8 9
Programming Problem 1.
You are given a directed graph representing a tree and a dictionary value which contains a value for each
node. Define the biggest descendent value of a node u to be the largest value of any node which is a descendent
of 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 node’s label is replaced by its value:
In a file named biggest_descendent.py, write a function biggest_descendent(graph, root, value)
3
which accepts the graph, the label of the root node, and the dictionary of values and computes a dictionary
mapping 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 estimated
distances. 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 number
of 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 one
nickel, two nickels, and one dime.
Hint: This can be solved by modifying a graph algorithm that we have learned! But there is no graph
mentioned in the problem above... You’ll need to model this problem as a graph problem. What are the
nodes? What are the edges? What algorithm should be modified?
4

DSC 40B编程辅导、讲解algorithm语言程序、辅导Python设计程序 辅导Database|讲解R语言程序

DSC 40B编程辅导、讲解algorithm语言程序、辅导Python设计程序辅导Database|讲解R语言程序