CSCI 570 Exam III Review SessionHanpeng LiuTRUE or FALSEIf NP doesn’t equal NP-complete, then P doesn’t equal NPTRUE or FALSEIf NP doesn’t equal NP-complete, then P doesn’t equal NPTrueConsider “if P = NP, then NP = NP-Complete”TRUE or FALSE- Linear Programming can be solved in polynomial time.- Integer programming can be solved in polynomial time.TRUE or FALSE- Linear Programming can be solved in polynomial time.True- Integer programming can be solved in polynomial time.False, Integer Programming is NP-CompleteLinear Programming ProblemA company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B. At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours.The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximise the combined sum of the units of X and the units of Y in stock at the end of the week.Formulate the problem of deciding how much of each product to make in the current week as a linear program.Linear Programming ProblemVariables - x be the number of units of X produced in the current week, - y be the number of units of Y produced in the current weekObjective: maximise (x+30-75) + (y+90-95) = (x+y-50), i.e. to maximise the number of units left in stock at the end of the weekConstraints50x + 24y <= 40 * 60, machine A time constraint30x + 33y <= 35 * 60, machine B time constraintx >= 75 - 30, so production of X >= demand (75) - initial stock (30), which ensures we meet demandy >= 95 - 90, so production of Y >= demand (95) - initial stock (90), which ensures we meet demandAlgorithm ProblemLet P1,P2,…,Pn be N programs to be stored on a disk with capacity D megabytes. Program Pi requires si megabytes of storage. We cannot store them all because D<∑si.1. Does a greedy algorithm that selects programs in order of nondecreasing si maximize the number of programs held on the disk? Prove or give a counter-example.2. Does a greedy algorithm that selects programs in order of nonincreasing order si use as much of the capacity of the disk as possible? Prove or give a counter-example.Algorithm ProblemLet P1,P2,…,Pn be N programs to be stored on a disk with capacity D megabytes. Program Pi requires si megabytes of storage. We cannot store them all because D<∑si.1. Does a greedy algorithm that selects programs in order of nondecreasing si maximize the number of programs held on the disk? Prove or give a counter-example.Yes. It is a special case of the Knapsack problem where the value of each item is the same.Algorithm ProblemLet P1,P2,…,Pn be N programs to be stored on a disk with capacity D megabytes. Program Pi requires si megabytes of storage. We cannot store them all because D<∑si.2. Does a greedy algorithm that selects programs in order of nonincreasing order si use as much of the capacity of the disk as possible? Prove or give a counter-example.No. Consider D = 7 and P = { 4, 3, 1, 1, 1, 1