1) For each problem listed below, state if it is NP complete. If it is NP complete, explain which NP complete it is most similar to. If it is not NP completed, either explain the similarity to another problem or explain how to solve it. - Find an ice cream truck route that drives every road exactly twice, once in each direction. (U-turns at intersection are permitted.) - Find the quickest fire truck route from the fire station to the fire site. - Select a set of intersection on which to place mail boxes so that nobody lives more than one block away from a mail box. Find the smallest set possible. - Plan an order for a politicians speaking engagement that has the least possible total driving distance - At the 10 pounds for a dollar book sale, select as many books as possible without exceeding the weight limit. (Think carefully about this one.) - A thief is robbing the Each Item cost one dollar store. The thief has a knapsack that can hold at most 50 pounds worth of items. The thief wants to select a set of items with maximal value but whose total weight does not exceed 50 pounds. - In order to support intra-state commerce, the state has agreed to plow a subset of roads that allow reaching any city center from any other city center in state. Find the cheapest subset of roads that satisfy this agreement. - You are at Toys-R Us trying to select a set of present to satisfy a greedy child. You have a long list of requested presents, each marked from 1 to 10 on a desirability scale. You must get at least 50 desirability points worth of presents, and you also must minimize cost. - You have found someone in Portland who will sell you an Oculus Rift and also someone in Augusta. You decided to buy both. You wish to find the fastest way to drive to these two locations and return to your starting point. - You wish to assign team members to a set of sports teams such that the sum of the rankings of the players on each team are close to equal as possible.

2) What is the worst case time complexity of the following algorithm. Show your work and simplify your answer! Int func (int n) { if (n <= 1) return 1; else return func (n/2) + func (n/2); }

3 ) a) Explain a fast algorithm to verify that an array of N elements is in sorted order. How many comparisons does it take ? (Give an exact answer) b) Prove that the best case for any possible sorting algorithm cannot be less than this number of comparisons. ( Hint: this os not a decision tree proof.) c) What comparisons based sorting algorithm that we have seen in class uses this number of comparisons in the best case? Describe a best case input for this algorithm d) How many possible input orders are there for sorting N keys ? Explain why. In class we analyzed the worst-case execution time for comparison based sorting algorithm. In this problem we are going to consider the BEST-CASE execution time. e) Only a very small portion of the input orders can possibly be finished in the best case time. Use a decision tree argument to determine a bound on the maximum number of input ordering that can be sorted by any possible sorting algorithm in the case time determined above.