CS420/520: Graph Theory with Applications to CS, Winter 2022
Homework 4
算法代码代写 Homework Policy: 1.Students should work on group assignments in groups of preferably three people. Each group submits to CANVAS a typeset report
Homework Policy: 算法代码代写
- Students should work on group assignments in groups of preferably three people. Each group submits to CANVAS a typeset report in pdf format.
- 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.
- 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.
- 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.
- 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.
- Every statement that is made should be proved unless stated otherwise. For any algorithm that is proposed, its running time analysis must be included.
- More items might be added to this list.
Problem 2. 算法代码代写
A cycle cover in a directed graph G is a set of directed cycles that contain all vertices of G. Let G be an directed unweighted graph, and suppose that we have an algorithm that can compute the permanent of any matrix in polynomial time. Design an algorithm to compute the number of cycle covers of G. Show that your algorithm works in polynomial time, assuming that the permanent can be computed in polynomial time. Prove that your algorithm is correct.
Problem 3. 算法代码代写
We saw an example of the Gaussian elimination for computing the determinant of a matrix in class. In this exercise, you develop the pseudocode for computing the determinant of an n × n matrix A using Gaussian elimination. Suppose that you have the following three procedures each return in O(n) time.
- SwapRows(A, i, j): Here i and j are integers between 1 and n. This procedure will swap row i and row j of the matrix A.
- CombineRows(A, α, i, j): Here α is a real number, and i and j are integers between 1 and n. This procedure adds α times row i to row j.
- DiagonalProduct(A): This procedure returns the product of all the numbers on the diagonal of A.
(1) Write a pseudocode to compute the determinant of a matrix A using the procedures above.
(2) Analyze the running time of your pseudocode.
(3) Explain the property of determinant that you are using in each step of your algorithm.
