Search the whole station

# 算法分析代写 Analysis of Algorithms代写 Practice Exam代写

## Practice Exam – 2

### True/False Problems

1. For every graph G and every maximum flow on G, there always exists an edge such that increasing the capacity on that edge will increase the maximum flow that’s possible in the graph.

2. The problem of deciding whether a given flow f of a given flow network G is maximum flow can be solved in linear time.

3. In any maximum flow there are no cycles that carry positive flow.(A cycle < e1, . . . , ek > carries positive flow iff f(e1) > 0, . . . , f(ek) > 0.)

4. If X is any search problem, then X can be reduced to INDEPENDENT SET.

#### 5. 算法分析代写

An linear program cannot have an unbounded objective function value.

6. The problem of finding the length of the shortest path between two nodes in a directed graph (which we would normally solve using Dijkstra’s algorithm) can be expressed as a linear program. (An ordinary, continuous linear program; we’re not talking about integer linear programs.) Assume that there is only one shortest path

7. Given a flow network where all the edge capacities are even integers, the Ford-Fulkerson algorithm will require at most C/2 iterations, where C is the total capacity leaving the source s.

8. Suppose f is a flow of some value X from s to t in a flow network G and there is an s-t cut of capacity X. Then there are no s to t paths in the residual graph Gf.

9. A graph flow is a max flow if and only if there exists no cut with the same capacity as the flow’s value.

10. Adding a constraint to a linear programming problem increases the size of the feasible region.

### Multiple Choice算法分析代写

1. The problem 3-SAT and 2-SAT are

(A) both in P

(B) both NP complete

(C) NP-complete and in P respectively

(D) undecidable and NP-complete respectively

2. Which of the following statements are TRUE? (1) The problem of determining whether there exists a cycle in an undirected graph is in P. (2) The problem of determining whether there exists a cycle in an undirected graph is in NP. (3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

(A) 1, 2 and 3

(B) 1 and 3

(C) 2 and 3

(D) 1 and 2

3. Which of the following is true about NP-Complete and NP-Hard problems.

(A) If we want to prove that a problem X is NP-Hard, we take a known NP-Hard problem Y and reduce Y to X

(B) The first problem that was proved as NP-complete was the circuit satisfiability problem.

(C) NP-complete is a subset of NP Hard

(D) All of the above

#### Answer the following questions based on:算法分析代写

A company manufactures two products X and Y. Each product has to be processed in three departments: welding, assembly and painting. Each unit of X spends 2 hours in the welding department, 3 hours in assembly and 1 hour in painting. The corresponding times for a unit of Y are 3, 2 and 1 hours respectively. The employee hours available in a month are 1,500 for the welding department, 1,500 in assembly and 550 in painting. The contribution to profits are £100 for product X and £120 for product Y.

4. What is the objective function (Z) to be maximised in this linear programming problem (where Z is total profit in £s)?

(A)Z = 1500X + 1500Y

(B)Z = 120X + 100Y

(C)Z = 2X + 3Y

(D)Z = 100X + 120Y

5. Total profits are maximised when the objective function (as a straight line on a graph) is:

(A)Furthest from the origin irrespective of the ‘feasible region’

(B)Nearest to the origin and tangent to the ‘feasible region’

(C)Furthest from the origin and tangent to the ‘feasible region’

(D)Nearest to the origin irrespective of the ‘feasible region’

#### 6. 算法分析代写

What is the equation of the labour constraint line for the welding department in this linear program?

(A)3X + 2Y = 1,500 hours

(B)3X + 2Y = 550 hours

(C)2X + 3Y = 1,500 hours

(D)2X + 3Y = 550 hours

7. What is the equation of the labour constraint line for the assembly department in this linear program?

(A)1X + 1Y = 1,500 hours

(B)2X + 2Y = 1,500 hours

(C)1X + 1Y = 550 hours

(D)3X + 2Y = 1,500 hours

8. What is the solution to this linear programming problem in terms of the respective quantities of X and Y to be produced if profits are to be maximised?

(A)X = 150, Y = 400

(B)X = 0, Y = 500

(C)X = 400, Y = 150

(D)X = 550, Y = 0

### Problem LP算法分析代写

Given the following linear program

max(3x1 + 8x2)

subject to

x1 + 4x2 20

x1 + x2 7

x1 ≥ −1

x2 5

1. Rewrite it in the standard form. You don’t need to write in matrix form.

2. Write the dual.

### Problem NPC

Suppose that after your graduation, you move to a new city. The city is defined by a directed graph G = (V, E) and for each edge e E, there is a non-negative cost ce associated to it. Your living place is represented as a node s V . In addition, there are a set of landmarks X V , which you want to visit. Therefore, you want to choose a subgraph that spans all vertices in X (and possibly some other in V ) and contains a path from s to each x X with the minimum total edge cost.

1. Phrase the above optimization problem as a decision problem and show that it belongs to NP.

2. Show a polynomial time construction using a reduction from 3-SAT.

3. Write down the claim that the 3-SAT problem is polynomially reducible to the original problem.

4. Prove the claim in the direction from 3-SAT to the reduced problem.

5. Prove the claim in the direction from the reduced problem to 3-SAT.

### Problem DP算法分析代写

Given a sequence of n coins of values v1, . . . , vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the sequence, removes it, and receives the value of that coin. Use dynamic programming to determine the maximum possible amount of money we can win if we move first.

1. Define (in plain English) subproblems to be solved.

2. Write the recurrence relation for subproblems. Also write the base cases.

3. Use plain English explain how you use that recursive relation to obtain a solution. You don’t need to prove the correctness.

### Problem Network Flow 1

In the network below, the demand values are shown on vertices. Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge.

1. Describe how to reduce the circulation problem into a maximum flow problem.

2. Compute the maximum flow of the reduced problem.

3. Determine if there is a feasible circulation in the original graph.

### Problem Network Flow 2

Suppose we have a binary matrix A ∈ {0, 1} of size m × n. Our goal is to select rows and columns that contain 1’s. That is, each 1 should be covered by either a column or a row. Each row have a cost ri and each column have a cost cj . Design an algorithm to find the lowest total cost:

The prev:

### Related recommendations

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

631

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
• #### 信息检索代写 XML代写 XML document代写 CS代写

961

XML 信息检索代写 Question 1. Choose concept(s) from below that are useful in discretionary access control. Explain their usefulness. (a) roles, (b) security classes, Question 1. C...

View details
• #### 算法分析作业代写 Algorithms and analysis代写 JAVA代写

807

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
• #### 高性能计算机架构代写 Computer Architecture代写

807

ECE/CS 570 – High Performance Computer Architecture Homework #2 高性能计算机架构代写 1.Consider a shared-memory multiprocessor that consists of three processor/cache units and where cache co...

View details
1