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
CS420/520: Graph Theory with Applications to CS
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
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.
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?
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.