Search the whole station

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

271

## Homework 1

cs图论代写 Homework Policy: 1. Students should work on group assignments in groups of preferably three people. Each group submits to CANVAS a typeset report in

### Homework Policy:

1. Students should work on group assignments in groups of preferably three people. Each group submits to CANVAS a typeset report in pdf format.

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. cs图论代写

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. More items might be added to this list.

(A) Jeff lecture notes on basic graph algorithms: http://jeffe.cs.illinois.edu/teaching/algorithms/book/05-graphs.pdf.

(B) Jeff lecture notes on basic graph algorithms: http://jeffe.cs.illinois.edu/teaching/algorithms/book/06-dfs.pdf.

### Problem 1.

Let G be a directed acyclic graph with no parallel edges or self-loops. Suppose we know that G has n vertices and at least k sinks. What is the minimum and maximum number of edges of G?

### Problem 2.

Let G be a directed graph with exactly one edge between every two vertices. Show that there exists a vertex u of G, from which there is a directed path to every other vertices.

### Problem 3. cs图论代写

Suppose you are given a directed graph G = (V, E) and two vertices s and t. Describe and analyze an algorithm to determine if there is a walk in G from s to t (possibly repeating vertices and/or edges) whose length is divisible by 3. For example, given the graph shown below, with the indicated vertices s and t, your algorithm should return T rue, because the walk s → w → y → x → s → w → t has length 6.

### Problem 4. cs图论代写

Consider the longest increasing subsequence problem: given a sequence of n distinct numbers A[1, . . . , n], we would like to find the longest increasing subsequence of A. For example, A = (5, 2, 6, 7, 1, 9) has an increasing subsequence of length four as marked; note that the longest increasing subsequence is not necessarily unique. Reduce the longest increasing subsequence to the problem of finding the longest path in a directed graph: suppose you have a black box that can find the longest path of any DAG in O(1) time, how would you use it to solve the longest increasing subsequence. Analyze the running time of your algorithm, and prove that it is correct assuming the black box correctly returns the longest path of any DAG.

The prev:

### Related recommendations

• #### 图论代写 Graph Theory代写 Assignment代写

847

MT4514 Graph Theory Assignment 1 图论代写 This assignment forms 5% of the assessment for this module. The assignment will be marked out of 20 marks. Please answer all questions, This assi...

View details
• #### 机器学习课业代做 CSE 158/258代写 cs代写 cs作业代写

654

CSE 158/258: Homework 3 机器学习课业代做 Instructions These homework exercises are intended to help you get started on potential solutions to Assignment 1. We’ll work directly with the Instr...

View details
• #### 运行中的算法代写 CSCI 570代写 算法作业代写 cs作业代写

651

CSCI 570 Homework 3 运行中的算法代写 For all divide-and-conquer algorithms follow these steps: 1. Describe the steps of your algorithm in plain English. 2. Write a recurrence equation For al...

View details
• #### 澳洲CS代写-有留学生找澳洲CS代写被发现的么？想了解一下

783

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

View details
1