Home Page > > Details

Assignment 3

CMPT307

Summer 2020

Assignment 3

Due Wed July 15 at 23:59

4 problems, 40 points.

** For questions 1, 3, and 4, please describe your algorithm in pseudocode,

then use several sentences to explain your idea.

1. Describe an algorithm to compute the reversal (also called transpose)

rev(G) of a directed graph in O(V + E) time. (10 points)

2. Given a directed graph G. Let v denote a vetex of G, and S(v) be the

strong component of G that contains v. For two arbitrary vertices u, v ∈

G, prove that u can reach v if and only if S(u) can reach S(v) in scc(G).

(10 points)

3. Given an undirected graph G with weighted edges and a minimum spanning tree T of G, describe an algorithm (use pseudocode) to update the

minimum spanning tree T when the weight of a single edge e is increased.

The input to your algorithm is the edge e and its new weight value. You

shold modify the spanning tree T so that it is still a minimum spanning

tree. (10 points)

Hint: Consider the cases e ∈ T and e 6∈ T separately.

4. Given a directed graph G with weighted edges, describe an algorithm to

find the shortest path from one vertex s to another vertex t. There is

exactly one edge in G that is with negative weight. (10 points)

Hint: Consider modifying Dijkstra’s algorithm. Of course other ideas

could also be great.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp2
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Cis 484 Assignmenthelp With ,Ghostwrit... 2020-09-27
- Ghostwriter Kit206 Course Assignment,H... 2020-09-27
- Comp2100 Assignmenthelp With ,Ghostwri... 2020-09-27
- Msbd5015 Assignmentghostwriter ,Python... 2020-09-27
- Programming Assignmentghostwriter ,Jav... 2020-09-27
- Cisc 360 Assignmenthelp With ,Ghostwri... 2020-09-27
- Cs 570 Assignmenthelp With ,Java Progr... 2020-09-27
- Help With Isys 1108 Assignment,Help Wi... 2020-09-27
- Data Assignmentghostwriter ,Java，C++ ... 2020-09-26
- Csc220 Assignmenthelp With ,Data Assig... 2020-09-26
- Ghostwriter Csc220 Assignment,Help Wit... 2020-09-26
- Bridging Coursework 2020-09-26
- Comp Sci 3004/7064 Operating Systems ... 2020-09-26
- Comp9311 20T2 - Assignment 2 2020-09-26
- Ipal Capstone Project 2020-09-26
- Ipal Programming In R - Week 2 Assign... 2020-09-26
- Csc 503/Seng 474 Data Mining Assignmen... 2020-09-26
- Assignment 1 Cmpt 307 2020-09-26
- Csci 2300 Lecture Exercise 5 2020-09-26
- Csci 2300 Lab 4 2020-09-26

Contact Us - Email：99515681@qq.com WeChat：codinghelp2

© 2014 www.asgnhelp.com

Programming Assignment Help！