Search the whole station

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

120

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

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

414

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 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
• 算法分析作业代写 Algorithms and analysis代写 JAVA代写

561

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
• 机器学习课业代做 CSE 158/258代写 cs代写 cs作业代写

424

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
1