CSCI 570 Exam III Review Session Hanpeng Liu TRUE or FALSE If NP doesn t equal NP complete then P doesn t equal NP TRUE or FALSE If NP doesn t equal NP complete then P doesn t equal NP True Consider 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 Complete Linear Programming Problem A 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 Problem Variables 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 week Objective 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 week Constraints 50x 24y 40 60 machine A time constraint 30x 33y 35 60 machine B time constraint x 75 30 so production of X demand 75 initial stock 30 which ensures we meet demand y 95 90 so production of Y demand 95 initial stock 90 which ensures we meet demand Algorithm Problem Let 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 2 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 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 Problem Let 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 Problem Let 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