COMP 360 Fall 2023 Assignment 3
Due: Thursday, November 2nd, 2023 at 8:00pm
Please submit the assignment on Crowdmark by the due date. In all problems below where you are asked to give an efficient algorithm, you must also prove that your algorithm is correct and analyze its running time. If you use any sources other than the course textbook or the lecture notes (e.g. other textbooks, online notes, friends) please cite them for your own safety. Do not upload this assignment to any online repository. Also, a reminder that direct copying from sources is not permitted, and solutions must be in your own words.
Questions 算法作业课业代做
1. [10]
Consider the following linear program.
min 3x1 + 2x2 − 4x3 − 10x4
subject to x1 + 2x3 + x4 ≥ 10
−2x3 − 3x4 ≥ −12
−x2 + 5x3 + x4 ≥ 20
2x2 − 3x3 − 3x4 ≥ −36
x1, x2, x3, x4 ≥ 0
a.Write down the dual of this linear program. [5]
b.The optimal solution to this linear program is (0, 0, 4.5, 1). Use this optimal solution and thecomplementary slackness conditions to find an optimal solution for the dual linear program. [5]
2.[15]
A bakery creates three different products: fruit pies, bread, and chocolate cakes. It is trying to plan out how to buy common ingredients in order to maximize its revenue. The ingredients required to make, and the revenue generated by selling, one unit of each product is recorded in the following table:
a.[10]
Suppose you are running a rival bakery, and you want to buy all of the ingredients that the above bakery currently has. In order to do so you must set a price for each ingredient. However, the above bakery will not sell you its ingredients immediately (you are a rival, after all). In fact, it will only sell the ingredients to you if it can make at least as much money selling the ingredients to you as it would have made if it baked the ingredients into goods and sold the goods for profit.
Write a linear program that will find the optimal setting of prices for each ingredient (i.e. flour, butter, sugar, milk, fruit, chocolate, yeast) so that the first bakery will sell you all of its ingredients, but, so that you will minimize the amount you spend to buy the ingredients. Your linear program should have one variable for each ingredient, representing the price of buying one unit of that ingredient (e.g. $/gram, etc.). Briefly justify the definition of your linear program.
b.[5] 算法作业课业代做
Prove that the minimum cost to buy all ingredients from the first bakery is equal to the maximum profit that the original bakery could make by baking its ingredients into goods and selling them.
3.[10]
Give a polynomial-time reduction from SAT to the following problem. Given a boolean formulaF which has 2n variables appearing in it, denoted x1, x2, . . . , xn, y1, y2, . . . , yn, decide if F has a satisfying assignment (x, y) where additionally x1 = y1, x2 = y2, . . . , xn = yn.
4.[30] 算法作业课业代做
For each of the following variations on the Vertex Cover problem, either prove that the variation isin P by giving a polynomial-time algorithm solving it, or, give a polynomial-time reduction from Vertex Cover to that variation. Briefly justify that your algorithms and reductions are correct.
(a) Given a graph G, decide if it is possible to delete no more than 100 edges from G such that the resulting graph has a vertex cover of size 10.
(b) Given a graph G and two positive integers d, k, decide if it is possible to delete d edges from G such that the resulting graph has a vertex cover of size at most k.
(c) Given a graph G and a positive integer k, decide if the smallest vertex cover on G has size at most k. 算法作业课业代做
(d) Given a graph G with at most 1, 000 vertices and a positive integer k, decide if G has a vertex cover of size k.
(e) Given a tree T and a positive integer k, decide if T has a vertex cover of size at most k.
(f) Given two graphs G1 = (V1, E1) and G2 = (V2, E2), define a new graph G1 ∨ G2 as follows. The vertices of G1 ∨ G2 are ordered pairs of vertices (v1, v2) ∈ V1 × V2 — for instance, if V1 = {a, b} and V2 = {1, 2} then V1 × V2 = {(a, 1),(a, 2),(b, 1),(b, 2)}. The edges of G1 ∨ G2 are defined as follows. An edge ((u1, u2),(v1, v2)) is in G1 ∨ G2 if and only if either (u1, v1) ∈ E1 and u2 = v2, or, (u2, v2) ∈ E2 and u1 = v1.
The variation of vertex cover is then as follows. Given G1, G2, and a positive integer k, decide if G1 ∨ G2 has a vertex cover of size at most k.
更多代写：cs澳洲代网课 多邻国网考 英国微积分网课托管推荐 北美essay润色 澳洲report代写 电影分析essay代写
