Search the whole station

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

276

## 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代写-有留学生找澳洲CS代写被发现的么？想了解一下

781

有留学生找澳洲CS代写被发现的么？想了解一下代写的靠谱程度 澳洲CS代写 有不少外出留学的留学生就能够发现，国外的作业可以说是多到离谱，基本上不是在写作业就是在写作业的路上，但是这些作业如果不做也不...

View details
• #### 算法分析作业代写 Algorithms and analysis代写 JAVA代写

827

Assignment 2 算法分析作业代写 IMPORTANT NOTES • If you are asked to develop/design an algorithm, you need to describe it in plain English first, say a paragraph, IMPORTANT NOTES •...

View details
• #### cs图论代写 CS420/520代写 Graph Theory代写 cs作业代写

270

CS420/520: Graph Theory with Applications to CS Homework 1 cs图论代写 Homework Policy: 1. Students should work on group assignments in groups of preferably three people. Each group submits ...

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

951

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
1