Problem 30
Charlie Programmer is given the problem of dividing a group (of an even number of people) into two disjoint subgroups of equal size so that the difference between the total ages of each subgroup is as large as possible. He proposes the solution of forming all possible subgroup pairs, computing the difference between the age totals of each pair, and selecting the pair with the largest difference. Mary Programmer, on the other hand, proposes that the original group first be sorted by age and then divided into two subgroups by forming one subgroup from the younger half of the sorted group and the other from the older half. What is the complexity of each of these solutions? Is the problem itself of polynomial, NP, or nonpolynomial complexity?
Problem 31
Prove that if \(L\) is recognized by a Turing Machine with a two-way infinite tape, it can be recognized by a Turing Machine with a one-way infinite tape.
Problem 32
Suppose a lottery is based on correctly picking four integer values, each in the range from 1 to 50 . Moreover, suppose that the jackpot grows so large that it becomes profitable to buy a separate lottery ticket for each possible combination. If it takes one second to buy a single ticket, how long would it take to buy one ticket for each combination? How would the time requirement change if the lottery required picking five numbers instead of four? What does this problem have to do with the material from this chapter?
Problem 37
Which of the following problems are in the class P? a. For a given set \(\mathrm{S}\) of \(\mathrm{n}\) integers, sort \(\mathrm{S}\). b. The traveling salesperson problem. c. The Hamilton Path problem. d. The Node Cover problem.
Problem 40
Suppose you are given two algorithms for solving the same problem. One algorithm has time complexity \(n^{4}\) and the other has time complexity \(4 \mathrm{n}\). For what size inputs is the former more efficient than the latter?
Problem 41
Suppose we were faced with solving the traveling salesperson problem in a context involving 15 cities in which any two cities were connected by a unique road. How many different paths through the cities would there be? How long would it take to compute the length of all of these paths assuming that the length of a path can be computed in one microsecond?
Problem 42
How many comparisons between names are made if the merge sort algorithm (Figures \(12.9\) and \(12.8\) ) is applied to the list Alice, Bob, Carol, and David? How many are required if the list is Alice, Bob, Carol, David, and Elaine?
Problem 43
How does a universal Turing machine function? Explain with an example.
Problem 44
Design an algorithm for finding integer solutions for equations of the form \(x^{2}+y^{2}=n\), where \(n\) is some given positive integer. Determine the time complexity of your algorithm.
Problem 45
Another problem that falls in the NP-complete category is the knapsack problem, which is the problem of finding which numbers from a list are the ones whose sum is a particular value. For example, the numbers 257,388 and 782 are the entries in the list \(\begin{array}{llllll}642 & 257 & 771388391 & 782 & 304\end{array}\) whose sum is 1427 . Find the entries whose sum is 1723 . What algorithm did you apply? What is the complexity of that algorithm?
