About Coursera:
Coursera Inc. is a U.S.-based massive open online course provider founded in 2012 by Stanford University computer science professors Andrew Ng and Daphne Koller. Coursera works with universities and other organizations to offer online courses, certifications, and degrees in a variety of subjects.
Advanced Algorithms and Complexity Week 1 Quiz Answers
Flow Algorithms
Q1) Which of the statements below is true ?
The Edmonds-Karp algorithm is always faster than the Ford-Fulkerson algorithm.
The Ford-Fulkerson algorithms runs in polynomial time on graphs with unit edge capacities.
The sum of the capacities of the edges of a network equals the sum of the capacities of the edges of any residual network.
Q2) Which vertices are in the minimum S-T cut in the network below?
A
B
C
D
E
T
S
Q3) What is the augmenting path that will be used by the Edmonds-Karp algorithm to increase the flow given below?
S-B-T
S-A-C-T
S-B-D-C-T
S-B-A-C-D-T
S-B-A-C-T
Q4) What is the size of the maximum matching of the following graph?
Write answer
4
Q5) Consider the image segmentation problem on a picture that is given by an n by n grid of pixels. Suppose that separation penalties are imposed only for adjacent pairs of pixels. If we use the Edmonds-Karp algorithm to solve this problem as described in class, the final runtime is O(n^a) for some a. What is the best such a?
5
Also Check: Coursera Python Data Structures (Chap 6-10) Quiz Answers
Advanced Algorithms and Complexity Week 2 Quiz Answer
Linear Programming Quiz
Q1) What is the minimum number of linear inequalities needed to define the figure pictured below?
Enter answer here
8
Q2) Given a solution to a linear program, one could try to show that it is optimal by finding a matching solution to the dual program. Which of the following theorems will make it easier to do so?
Complementary slackness.
Polytopes achieve optimum values at vertices.
Separation of convex sets from outside points by hyperplanes.
Q3) Which of the following statements are true?
A system of linear equations has always 0, 1, or infinitely many solutions.
A system of n linear equations in n variables always has a unique solution.
A system of linear equations has a solution unless they can be combined in some combination to give the equation 0=1.
Q4) Suppose that you are trying to solve the optimization problem:
Maximize v\cdot xv⋅x subject to Ax \geq bAx≥b for some A\in \mathbb{R}^{m\times n}A∈R
m×n (i.e. trying to solve an optimization problem in nn variables with mm linear inequality constraints).
This problem can be reduced to running a solution finding algorithm on a different system of linear equations in kk variables. What is the smallest value of kk for which this can be done?
Enter math expression here
K=0
Q5) What is the largest possible value of x+y achievable by pairs x,y of real numbers satisfying the constraints:
x <= 7
y <= 10
2x+y <= 21
-x + 2y <= 12
5x-y <= 30
15
Advanced Algorithms and Complexity Week 3 Quiz Answer
NP-complete Problems
Q1) How many satisfying assignments does the following formula have?
(x_1 \lor \overline{x}_2 \lor \overline{x}_3)(x_1 \lor x_2) (\overline{x}_1 \lor \overline{x}_2)(x
1
Enter answer here
3
Q2) How many integer solutions does the following linear program have?
x_1 \ge 0,\quad x_2 \ge 0,\quad 4x_1+3x_2 \le 12,\quad 3x_1+5x_2\le 15x
1
Enter answer here
10
Q3) Consider the following graph
It has 6 different independent sets: empty set, \{A\}{A}, \{B\}{B}, \{C\}{C}, \{A, C\}{A,C}, \{B, C\}{B,C}.
How many different independent sets does the following graph have?
Enter answer here
7
Q4) In the 3-coloring problem, you are given an undirected graph and the goal is to assign one of three available colors to its vertices such that the ends of each edge of the graph receive different colors. This is clearly a search problem: given a graph and a coloring of its vertices, one can check in polynomial time whether there are only three different colors and that no edge is monochromatic. This problem is known to be NP-complete. Do we have a polynomial time algorithm for this problem?
This is an open problem.
Yes, this problem can be solved in polynomial time.
No, this problem cannot be solved in polynomial time for sure.
Q5) In the lectures, we constructed a reduction from 3-SAT to Independent Set. Now, we show the reverse reduction. For this, we are going to reduce Independent set to SAT. We can then use the fact that SAT reduces to 3-SAT.
In the Independent Set problem we are given a graph GG with nn vertices \{1,2,\dotsc,n\}{1,2,…,n} and a positive integer bb. Our goal is to check whether the graph has bb vertices \{u_1,u_2,\dotsc,u_b\} \subseteq \{1,2,\dotsc,n\}{u
is equal to some vertex of the graph: for all 1 \le i \le b1≤i≤b, (x_{i1} \lor x_{i2} \lor \dotsb \lor x_{in})(x
.
The resulting formula is satisfiable if and only if the initial graph has an independent set of size bb.
Is this reduction correct?
No, it is not correct, because it might produce an unsatisfiable formula for a graph that has an independent set of size bb.
No, it is not correct, because it is not a polynomial time reduction.
Yes, the reduction is correct.
No, it is not correct, because for a graph that does not have an independent set of size bb it might produce an a satisfiable formula.
Q6) How many satisfying assignments does the following circuit have?
3
Advanced Algorithms and Complexity Week 4 Quiz Answer
Coping with NP-completeness
Q1) What is the weight of a minimum traveling salesman cycle in the following graph?
Enter answer here
110
Q2) Recall that the dynamic programming algorithm for the traveling salesman problem uses O(n^2 \cdot 2^n)O(n2⋅2n) time and O(n \cdot 2^n)O(n⋅2n) space (as usual, nn is the number of vertices). You are going to run this algorithm on a graph with 50 vertices. Roughly how much space is needed for this assuming that each cell of the dynamic programming table occupies 8 bytes? (See How much is 1 megabyte, gigabyte, etc?)
Petabyte
Exabyte
Zettabyte
Yottabyte
Kilobyte
Megabyte
Gigabyte
Terabyte
Q3) What is the maximum size of an independent set in the following tree?
Enter answer here:
10
Post a Comment