辅导AMPL code、data留学生辅导、讲解c/c++，Python，Java编程语言 辅导Python程序|讲解Python程序
- 首页 >> Algorithm 算法 First Homework Set
Take home exam. Submit solutions via email, preferably in pdf format. Scanned images are OK.
Solutions are due by midnight of Sunday, March 22, 2020 (SHARP!)
Feel free to use an AMPL code when it is helpful!
Problem 1: Let a ∈ R
n
+ and b ∈ R+ be given parameters. Let us call a subset
S ⊆ E = {1, 2, ..., n} independent if a(S) = P
j∈S
aj ≤ b.
• Show that this defines an independence system F ⊆ 2
E.
• Consider n = 6, a = (1, 1, 1, 4, 4, 5), b = 8, E = {1, 2, 3, 4, 5, 6}, and
S = {1, 2, 3, 4, 5}. What are the values of r(S) and ρ(S)? How much is
q(E, F) for this example?
• For an arbitrary n find a ∈ Rn+ and b ∈ R+ such that q(E, F) ≤1n−1.
Problem 2: Consider the problem of processing a set E of n jobs on a single
machine. Each job j ∈ E needs one unit of (uninterrupted) time for processing,
has a due date dj , and brings a profit of pj , if it is finished before its due date.
Let us call a subset S ⊆ E of the jobs independent, if all the jobs in S can be
processed, in some order, such that all of them are finished on time (before their
respective due dates). Let F be the collection of all independent job subsets.
• Consider n = 7, and the following list of (dj , pj ) pairs: (3, 2), (2, 3), (4, 4),(1, 3), (4, 3), (4, 6), (6, 7). What is the ”Best-in-Greedy” solution?
• Prove that (E, F) is a matroid.
Problem 3: Let G be a graph on 5 vertices, V (G) = {1, 2, 3, 4, 5}, defined by
the set of edges E(G) = {(1, 2),(2, 3),(2, 5),(3, 4),(4, 5),(5, 1)}. Let F ⊆ 2V (G)
be the family of independent (stable) sets of G, that is vertex subsets that do
not contain an edge inside.
• Is (V (G), F) a matroid? Why?
• Recall that the associated independence polytope is defined as
Write down the defining inequalities for PV (G),F in this case, and eliminate
the redundant ones.
• How much is the maximum of 5x2 + 3x5 over PV (G),F ?
Problem 4: Consider the graph G on n = 7 vertices V = {1, 2, 3, 4, 5, 6, 7} with
edges E = {(1, 2),(1, 4),(2, 3),(2, 5),(2, 7),(3, 4),(3, 5),(4, 5),(4, 6),(4, 7),(5, 6),(6, 7)},
and with edge weights (in the previous order of edges) w1,2 = 9, w1,4 = 7,
w2,3 = 9, w2,5 = 10, w2,7 = 7, w3,4 = 8, w3,5 = 9, w4,5 = 9, w4,6 = 8, w4,7 = 8,
w5,6 = 7, w6,7 = 7.
1
• What is the weight of the maximum-weight spanning tree?
• Compute the sequence of edges chosen by Kruskal’s algorithm.
Problem 5: Let us consider a bipartite graph G = (A ∪ B, E) where set A
has 15 vertices of degree 3, 18 vertices of degree 5, and 12 vertices of degree 15
(that is |A| = 45 = 15 + 18 + 12.) Every vertex in set B is connected to exactly
1 vertex of degree 3, 2 vertices of degree 5, and 4 vertices of degree 15.
• How large is B?
• How large is a maximum cardinality matching in this graph? Why?
Problem 6: Consider the following cutting stock problem, with input length
L = 21. These 21-foot pieces are to be cut into smaller ones to fulfill the
following orders:
What is the optimal solution?
Problem 7: A company has 100M to invest in several possible projects. They
can either fund a project fully, or do not fund it at all. For each of the 12
possible projects we list in the table below the cost of the project and the net
profit the project is expected to generate (in millions of dollars.) Which projects
to fund so that the company maximizes its net profit?
P rojects
A B C D E F G H I J K L
P rof it 30 25 5 9 11 7 14 19 40 29 30 34
Cost 16 15 2 4 4 3 9 12 29 20 18 25
Solve the problem by the dynamic programming algorithm or by using an AMPL
model. Submit the optimal solution, and the corresponding AMPL .mod and
.dat files, if you worked with AMPL.
Problem 8: Consider a graph G = (V, E) (not necessarily bipartite), nonnegative
weights c : E → R+ on the edges, and the problem of finding a maximum
weight matching. How good (bad) is the greedy algorithm on this problem type?
Figure 1:
[Hint: What is the corresponding independence system F? How small q(E, F)
can be?]
Problem 9: Consider the instance of the Chinese Postman problem shown in
Figure 1. The edge traversing times are shown along the edges in minutes.
• Assume that the post office is in vertex 1. What is the optimal, time
minimizing tour of the postman? How much time does he need to deliver
all letters and get back to the post office?
• Assume that he starts at the post office and wants to finish in his house
in vertex 8. How much time does he need then to deliver all letters and
arrive home? What is his optimal tour in this case?
Problem 10: You are the manager of a consulting firm that has 5 co-workers
(A, B, C, D, and E) and 5 projects (P1, P2, P3, P4, and P5) to complete.
3
The table below shows the expected profit if a worker is assigned to a project.
For instance, if worker A is assigned to project P2, then the company earns $7K
as profit. What is the optimal, profit maximizing assignment of workers to
projects? Use the Hungarian algorithm to solve this, and document each step
of it.
4
Take home exam. Submit solutions via email, preferably in pdf format. Scanned images are OK.
Solutions are due by midnight of Sunday, March 22, 2020 (SHARP!)
Feel free to use an AMPL code when it is helpful!
Problem 1: Let a ∈ R
n
+ and b ∈ R+ be given parameters. Let us call a subset
S ⊆ E = {1, 2, ..., n} independent if a(S) = P
j∈S
aj ≤ b.
• Show that this defines an independence system F ⊆ 2
E.
• Consider n = 6, a = (1, 1, 1, 4, 4, 5), b = 8, E = {1, 2, 3, 4, 5, 6}, and
S = {1, 2, 3, 4, 5}. What are the values of r(S) and ρ(S)? How much is
q(E, F) for this example?
• For an arbitrary n find a ∈ Rn+ and b ∈ R+ such that q(E, F) ≤1n−1.
Problem 2: Consider the problem of processing a set E of n jobs on a single
machine. Each job j ∈ E needs one unit of (uninterrupted) time for processing,
has a due date dj , and brings a profit of pj , if it is finished before its due date.
Let us call a subset S ⊆ E of the jobs independent, if all the jobs in S can be
processed, in some order, such that all of them are finished on time (before their
respective due dates). Let F be the collection of all independent job subsets.
• Consider n = 7, and the following list of (dj , pj ) pairs: (3, 2), (2, 3), (4, 4),(1, 3), (4, 3), (4, 6), (6, 7). What is the ”Best-in-Greedy” solution?
• Prove that (E, F) is a matroid.
Problem 3: Let G be a graph on 5 vertices, V (G) = {1, 2, 3, 4, 5}, defined by
the set of edges E(G) = {(1, 2),(2, 3),(2, 5),(3, 4),(4, 5),(5, 1)}. Let F ⊆ 2V (G)
be the family of independent (stable) sets of G, that is vertex subsets that do
not contain an edge inside.
• Is (V (G), F) a matroid? Why?
• Recall that the associated independence polytope is defined as
Write down the defining inequalities for PV (G),F in this case, and eliminate
the redundant ones.
• How much is the maximum of 5x2 + 3x5 over PV (G),F ?
Problem 4: Consider the graph G on n = 7 vertices V = {1, 2, 3, 4, 5, 6, 7} with
edges E = {(1, 2),(1, 4),(2, 3),(2, 5),(2, 7),(3, 4),(3, 5),(4, 5),(4, 6),(4, 7),(5, 6),(6, 7)},
and with edge weights (in the previous order of edges) w1,2 = 9, w1,4 = 7,
w2,3 = 9, w2,5 = 10, w2,7 = 7, w3,4 = 8, w3,5 = 9, w4,5 = 9, w4,6 = 8, w4,7 = 8,
w5,6 = 7, w6,7 = 7.
1
• What is the weight of the maximum-weight spanning tree?
• Compute the sequence of edges chosen by Kruskal’s algorithm.
Problem 5: Let us consider a bipartite graph G = (A ∪ B, E) where set A
has 15 vertices of degree 3, 18 vertices of degree 5, and 12 vertices of degree 15
(that is |A| = 45 = 15 + 18 + 12.) Every vertex in set B is connected to exactly
1 vertex of degree 3, 2 vertices of degree 5, and 4 vertices of degree 15.
• How large is B?
• How large is a maximum cardinality matching in this graph? Why?
Problem 6: Consider the following cutting stock problem, with input length
L = 21. These 21-foot pieces are to be cut into smaller ones to fulfill the
following orders:
What is the optimal solution?
Problem 7: A company has 100M to invest in several possible projects. They
can either fund a project fully, or do not fund it at all. For each of the 12
possible projects we list in the table below the cost of the project and the net
profit the project is expected to generate (in millions of dollars.) Which projects
to fund so that the company maximizes its net profit?
P rojects
A B C D E F G H I J K L
P rof it 30 25 5 9 11 7 14 19 40 29 30 34
Cost 16 15 2 4 4 3 9 12 29 20 18 25
Solve the problem by the dynamic programming algorithm or by using an AMPL
model. Submit the optimal solution, and the corresponding AMPL .mod and
.dat files, if you worked with AMPL.
Problem 8: Consider a graph G = (V, E) (not necessarily bipartite), nonnegative
weights c : E → R+ on the edges, and the problem of finding a maximum
weight matching. How good (bad) is the greedy algorithm on this problem type?
Figure 1:
[Hint: What is the corresponding independence system F? How small q(E, F)
can be?]
Problem 9: Consider the instance of the Chinese Postman problem shown in
Figure 1. The edge traversing times are shown along the edges in minutes.
• Assume that the post office is in vertex 1. What is the optimal, time
minimizing tour of the postman? How much time does he need to deliver
all letters and get back to the post office?
• Assume that he starts at the post office and wants to finish in his house
in vertex 8. How much time does he need then to deliver all letters and
arrive home? What is his optimal tour in this case?
Problem 10: You are the manager of a consulting firm that has 5 co-workers
(A, B, C, D, and E) and 5 projects (P1, P2, P3, P4, and P5) to complete.
3
The table below shows the expected profit if a worker is assigned to a project.
For instance, if worker A is assigned to project P2, then the company earns $7K
as profit. What is the optimal, profit maximizing assignment of workers to
projects? Use the Hungarian algorithm to solve this, and document each step
of it.
4