DSC 40B代写编程代写、代做algorithm语言程序、代写Python设计程序

日期：2020-12-06 06:36

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