Search the whole station

# CS算法代写 Graph Theory代写 algorithm代写 cs作业代写

105

## Homework 2

CS算法代写 Homework Policy: 1. Students should work on homework assignments in groups of preferably three people. Each group submits to TEACH one set of typeset

### Homework Policy:CS算法代写

1. Students should work on homework assignments in groups of preferably three people. Each group submits to TEACH one set of typeset solutions, and hands in a printed hard copy in class or slides the hard copy under my door before the midnight of the due day. The hard copy will be graded.

2. The goal of the homework assignments is for you to learn solving algorithmic problems. So, I recommend spending sufficient time thinking about problems individually before discussing them with your friends.

3. You are allowed to discuss the problems with other groups, and you are allowed to use other resources, but you must cite them. Also, you must write everything in your own words, copying verbatim is plagiarism.

4. I don’t know policy: you may write ”I don’t know” and nothing else to answer a question and receive 25 percent of the total points for that problem whereas a completely wrong answer will receive zero.

5. Algorithms should be explained in plain english. Of course, you can use pseudocodes if it helps your explanation, but the grader will not try to understand a complicated pseudocode.

6. Every statement that is made should be proved unless stated otherwise. For any algorithm that is proposed, its running time analysis must be included.

7. Solutions must be typeset.

(A) Jeff lecture notes on single source shortest paths: http://jeffe.cs.illinois.edu/teaching/algorithms/book/08-sssp.pdf.

(B) Jeff lecture notes on all pairs shortest paths: http://jeffe.cs.illinois.edu/teaching/algorithms/book/09-apsp.pdf.

#### Problem 1.

Given a directed graph G = (V, E) and two nodes s, t, an st-walk is a sequence of nodes s = v0, v1, . . . , vk = t where (vi , vi+1) is an edge of G for 0 ≤ i < k. Note that a node may be visited multiple times in a walk; this is how it differs from a path. Given G, s, t and an integer k ≤ n, design a linear time algorithm to check if there is an st-walk in G that visits at least k distinct nodes including s and t.

• Solve the problem when G is a DAG (Hint: this is somewhat similar to the last problem of the previous homework assignment).

• Solve the problem when G is a an arbitrary directed graph. (Hint: If G is strongly connected then there is always such a walk even for k = n).

#### Problem 2. CS算法代写

A directed graph G is semi-connected if, for every pair of vertices u and v, either u is reachable from v or v is reachable from u (or both).

(a) Give an example of a directed acyclic graph with a unique source that is not semi-connected.

(b) Describe and analyze an algorithm to determine whether a given directed acyclic graph is semi-connected.

(c) Describe and analyze an algorithm to determine whether an arbitrary directed graph is semi-connected.

#### Problem 3.

Let G = (V, E) be a weighted graph with exactly two negatively weighted edges and no negative cycle, and let s and t be two vertices in G. Describe and analyze an algorithm to find the shortest path from s to t in O(E + V log V ) time. [Hint: Dijsktra works in O(E + V log V ) time for a non-negatively weighted graph, and Bellman-Ford works in O(EV ) time for a graph that possibly has negative edges but no negative cycle.]

#### Problem 4.

Consider the generic single source shortest path algorithm:

• while there is a tense edge u v, relax(u v).

Show that for any graph G, there is an order of the edges for which the generic algorithm ends in V − 1 iteration. Note that you do not need to compute this order efficiently; just prove that it exists.

### Related recommendations

• #### cs计算机体系结构作业代做 I218代写 计算机体系结构代写

65

I218 Computer ArchitectureReport 2 cs计算机体系结构作业代做 (1)How is the instruction “sub \$t9, \$s4, \$s7” translated to a machine instruction code? Answer the rs, rt, and rd fields in binary n...

View details
• #### 算法作业代写 Algorithm代写 CS代写 cs算法课业代写

639

Algorithm in Action CSCI-570 Homework 4 算法作业代写 1 Compute Max-Flow And Min-Cut 2 Escape From the Building In this problem, we need to decide whether there is a feasible plan for all th...

View details
• #### 算法课业代写 CS 6212代写 algorithm代写 cs算法作业代写

388

CS 6212 Homework 3 算法课业代写 Problem 1: (15 points) Let a1 < a2 < a3 < a4 < a5 < a6 be 6 numbers accessible with the following probabilities: p1 = 1/20, p2 = 5/20, p3 = 2/20, ...

View details
• #### 计算机网络课业代做 CS 158A代写 计算机网络代写 cs作业代写

76

CS 158A Computer Networks Problem Set 2 计算机网络课业代做 Problem 1 Read the following statements on reinforcement learning. Indicate if the statement is True or False and write a brief ju...

View details
1