代写Algorithms程序、Python程序调试、代写Python编程

日期：2021-05-16 10:28

Assignment: Graph Algorithms - I

1. Write BFS and DFS for a graph: What would be BFS and DFS traversal for the below graphs.

Write the nodes for BFS and DFS. Start at node A.

2. Apply BFS/DFS to solve a problem

You are given a 3-D puzzle. The length and breadth of the puzzle is given by a 2D matrix

puzzle[m][n]. The height of each cell is given by the value of each cell, the value of

puzzle[row][column] give the height of the cell [row][column]. You are at [0][0] cell and you

want to reach to the bottom right cell [m-1][n-1], the destination cell. You can move either

up, down, left, or right. Write an algorithm to reach the destination cell with minimal effort.

How effort is defined: The effort of route is the maximum absolute difference between two

consecutive cells.

Example if a route requires us to cross heights: 1, 3, 4, 6, 3, 1

The absolute differences between consecutive cells is: |1-3| = 2, |3-4|=1, |4-6|=2,

|6-3|=3, |3-1|=2; this gives us the values: {2, 1, 2, 3, 2}. The maximum value of

these absolute differences is 3. Hence the effort required on this path will be: 3.

Example:

Input: puzzle[][] = [[1, 3, 5], [2, 8, 3], [3, 4, 5]]

Output: 1

Explanation: The minimal effort route would be [1, 2, 3, 4, 5] which has an effort of

value 1. This is better than other routes for instance, route [1, 3, 5, 3, 5] which has

an effort of 2.

1 3 5

2 8 3

3 4 5

a. Describe the solution to the problem

b. Write pseudocode for your solution

c. Implement the algorithm. Name your function minEffort(puzzle). Name your file

MinPuzzle.py

d. What is the time complexity of your implementation?

3. Analyze Dijkstra with negative edges: Analyze with a sample graph and show why Dijkstra

does not work with negative edges. Give the sample graph and write your explanation why

Dijkstra would not work in this case.

4. (Extra Credit): What would be BFS and DFS traversal in below puzzle. Start at node A.

A B C

D E

F G

H I J

Debriefing (required!): --------------------------

Report:

1. Approximately how many hours did you spend on this assignment?

2. Would you rate it as easy, moderate, or difficult?

3. How deeply do you feel you understand the material it covers (0%–100%)?

4. Any other comments?

Note: ‘Debriefing’ section is intended to help us calibrate the assignments.