代写数据结构和算法网络流代写算法代写

HW3

代写数据结构和算法 1 Assigning lecturers to coursesThe ISE department has n lecturers who must collectively teach m courses. Each lecturer i has a subset of courses

1 Assigning lecturers to courses

The ISE department has n lecturers who must collectively teach m courses. Each lecturer i has a subset of courses S_ithat they can teach. For each course j, a minimum of c_j different lecturers must be assigned. For each lecturer i, there is a bound a_i on the maximum number of courses that they can be assigned to. Show how to find a feasible assignment of lecturers to courses, assuming such an assignment exists.

2 Special instances of bipartite matching 代写数据结构和算法

In parts (a) and (b), describe the solutions and the optimal objective values to the following special cases of the minimum cost perfect bipartite matching problem on 2n vertices.

a) The cost matrix C satisfies c_ij= a_i+ b_j , for given vectors a, b ∈ Rⁿ.

b) The cost matrix C satisfies c_ij= a_i/a_j, for a given (strictly positive) vector a ∈ Rⁿ with unique entries (you can make use of whatever well-known inequalities might be useful here).

c) Your friend shows you a “magic trick” involving the grid shown below:

3 Covering points on a line

Let P be a set of points on the real line, with each point colored white or black. Consider the problem of drawing a collection of intervals of minimal total length, such that each interval contains at least one black point and one white point, and such that each point is covered by an interval. The picture below illustrates one possible solution with 10 points, whose solution ends up consisting of three intervals:

4 Reductions to bipartite matching 代写数据结构和算法

Suppose you have an algorithm A that is capable of solving the minimum cost perfect matching problem in a complete bipartite network. Explain how you could use this algorithm to solve the following problems:

You can assume that all edge weights are unique. For full marks, show how to find the optimal bottleneck matching by calling A exactly once. You can make the edge weights as large as you like (like, really really big).

5 The permutation graph 代写数据结构和算法

Consider an undirected network G with n! vertices in it, in which each vertex corresponds to a permutation of {1, . . . , n}. We connect two vertices with an undirected edge (u, v) if the permutation associated with u can be transformed into the permutation associated with v if we exchange a pair of adjacent elements; for example, the permutation (14253) can be transformed into (12453) by exchanging the 2 and the 4. Note that we would not make an edge between (for example) (14253) and (15243), because we would have to exchange the 4 and the 5, which are not adjacent to each other.

Prove that G is connected. If you like, you are welcome to assume that the first entry and the last entry are also adjacent (although G is connected either way).

6 Combining two matchings 代写数据结构和算法

Let G = (V ∪ W, E) be a bipartite network, and suppose that V and W are further decomposed into two sets so that V = V₁ ∪ V₂ and W = W₁ ∪ W₂. Suppose that there exists a matching that matches every vertex in V₁ to some vertex in W, and there also exists a matching that matches every vertex in W₁ to some vertex in V . Prove that there exists a matching such that every vertex in V₁ is matched to a vertex in W and every vertex in W₁ is matched to a vertex in V .

7 Extra credit

Suppose you are given an n × n grid, with n ≥ 2, and you want to fifind a path that starts in the upper left corner, visits every other grid cell exactly once, and ends in the cell immediately to the right of where you started (in the upper left corner). The diagram below shows a solution to this problem for the case n = 4:

For every n, either give an algorithm for finding this path, or prove that none exists.

合作平台：essay代写论文代写写手招聘英国留学生代写

HW3