Homework 4 Theoretical
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Homework 4 Theoretical
Homework Instructions.
1. For all algorithms that you are asked to “give” or “design”, you should
• Describe your algorithm clearly in English.
• Give pseudocode.
• Argue correctness, even if you don’t give an entirely formal proof.
• Give the best upper bound that you can for the running time.
You are also encouraged to analyze the space required by your algorithm but we will not remove marks if you don’t, unless the problem explicitly asks you to analyze space complexity.
2. If you give a DP algorithm, you should follow the instructions in hw2-theoretical.
3. If you give a reduction, you should do so as we did in class, that is
(a) Give the inputs to the two problems.
(b) Describe in English the reduction transformation and argue that it requires polynomial
time. (You do not need to give pseudocode.)
(c) Prove carefully equivalence of the original and the reduced instances.
4. You should submit your assignment as a pdf file on Gradescope. Other file formats will not be graded, and will automatically receive a score of 0.
5. I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly. If you do not type your solutions, make sure that your hand-writing is very clear and that your scan is high quality.
6. You should not use any external resources for this homework. Failure to follow this instruction might have a negative impact on your performance in the second exam and interviews. For the same reason, you should avoid collaborating with your classmates unless you have thought through the problems on your own for a long time and are unable to make any further progress. I also encourage you to work on all the recommended exercises.
7. You should write up the solutions entirely on your own. Collaboration is limited to discussion of ideas only and you should adhere to the department’s academic honesty policy (see the course syllabus). Similarity between your solutions and solutions of your classmates or solutions posted online will result in receiving a 0 in this assignment and possibly further disciplinary actions. You should list your collaborators on your write-up.
Homework Problems
1. (12 points) Stingy SAT is the following problem.
On input a SAT formula φ, return a truth assignment that satisfies φ and minimizes the number of variables that are set to 1, or no if φ is unsatisfiable.
Give a polynomial time algorithm for Stingy SAT, or prove that no such algorithm exists unless P = NP .
2. (25 points)
Suppose you had a polynomial-time algorithm A for the decision version of the maximum independent set problem IS(D). That is, on input a graph G = (V,E) and an integer k , A answers yes if and only if G has an independent set of size at least k, and A runs in worst-case polynomial time.
Design a polynomial-time algorithm that takes as input a graph G and an integer k, and returns an independent set of size at least k if one exists in G, or no otherwise.
3. (30 points) A large store has m customers and n products and maintains an m ⇥ n matrix A such that Aij = 1 if customer i has purchased product j; otherwise, Aij = 0.
Two customers are called orthogonal if they did not purchase any products in common. Your task is to help the store determine a maximum subset of orthogonal customers.
Give a polynomial-time algorithm for this problem or prove that no such algorithm exists unless P = NP .
4. (38 points) Formulate linear or integer programs for the following optimization problems. (Full-credit will be given to LP solutions, when they are possible.)
(a) (10 points) Min-cost flow: Given a flow network with capacities ce and costs ae on
every edge e, and supplies si on every vertex i, find a feasible flow f : E ! R+—that is, a flow satisfying edge capacity constraints and node supplies—that minimizes the total cost of the flow.
(b) (14 points) The assignment problem: There are n persons and n jobs that have to be
matched on a one-to-one basis. There is a given set A of ordered pairs (i,j), where a pair (i,j) indicates that person i can be matched with job j. For every pair (i,j) 2 A, there is a value aij for matching person i with job j. Our goal is to assign persons to jobs so as to maximize the total value of the assignment.
(c) (14 points) Exact-3SAT: Given a formula φ with n variables and m clauses where each clause consists of exactly three distinct literals, is the formula satisfiable?
2021-12-04