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

CS420/520: Graph Theory with Applications to CS, Winter 2022

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.

Readings: CS算法代写

(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 = v₀, v₁, . . . , v_k = t where (v_i , v_i+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.

更多代写：Cs网上考试作弊  雅思线上代考  英国business model怎么写  科技论文翻译  美国大学抄袭被抓  cs图论代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写