Page 223 - Discrete Mathematics and Its Applications

202 3 / Algorithms

If H(P, P) = “halts,”
P as program then loop forever
Program Program
Input Output
H(P, I) K(P)
Program P H(P, P)
P as input If H(P, P) = “loops forever,”
then halt

FIGURE 2 Showing that the Halting Problem is Unsolvable.

is “halt,” then by the definition of K we see that K(K) loops forever, in violation of what H
tells us. In both cases, we have a contradiction.
Thus, H cannot always give the correct answers. Consequently, there is no procedure that
solves the halting problem.

Exercises

1. List all the steps used byAlgorithm 1 to find the maximum 8. Describe an algorithm that takes as input a list of n dis-
of the list 1, 8, 12, 9, 11, 2, 14, 5, 10, 4. tinct integers and finds the location of the largest even
integer in the list or returns 0 if there are no even integers
2. Determine which characteristics of an algorithm de- in the list.
scribed in the text (after Algorithm 1) the following pro-
cedures have and which they lack. 9. A palindrome is a string that reads the same forward
and backward. Describe an algorithm for determining
a) procedure double(n: positive integer)
whether a string of n characters is a palindrome.
while n> 0
n
10. Devise an algorithm to compute x , where x is a real
n := 2n
number and n is an integer. [Hint: First give a procedure
b) procedure divide(n: positive integer) n
for computing x when n is nonnegative by successive
while n ≥ 0
multiplication by x, starting with 1. Then extend this pro-
m := 1/n −n n n
cedure, and use the fact that x = 1/x to compute x
n := n − 1
when n is negative.]
c) procedure sum(n: positive integer) 11. Describe an algorithm that interchanges the values of the
sum := 0 variables x and y, using only assignments. What is the
while i< 10 minimum number of assignment statements needed to do
sum := sum + i this?
d) procedure choose(a, b: integers) 12. Describe an algorithm that uses only assignment state-
x := either a or b ments that replaces the triple (x,y,z) with (y,z,x).
3. Devise an algorithm that finds the sum of all the integers What is the minimum number of assignment statements
in a list. needed?
13. List all the steps used to search for 9 in the sequence 1,
4. Describe an algorithm that takes as input a list of n in- 3, 4, 5, 6, 8, 9, 11 using
tegers and produces as output the largest difference ob-
tained by subtracting an integer in the list from the one a) a linear search. b) a binary search.
following it. 14. List all the steps used to search for 7 in the sequence given
in Exercise 13 for both a linear search and a binary search.
5. Describe an algorithm that takes as input a list of n inte- 15. Describe an algorithm that inserts an integer x in the ap-
gers in nondecreasing order and produces the list of all propriate position into the list a 1 ,a 2 ,...,a n of integers
values that occur more than once. (Recall that a list of that are in increasing order.
integers is nondecreasing if each integer in the list is at
least as large as the previous integer in the list.) 16. Describe an algorithm for finding the smallest integer in
a finite sequence of natural numbers.
6. Describe an algorithm that takes as input a list of n in- 17. Describe an algorithm that locates the first occurrence of
tegers and finds the number of negative integers in the the largest element in a finite list of integers, where the
list.
integers in the list are not necessarily distinct.
7. Describe an algorithm that takes as input a list of n inte- 18. Describe an algorithm that locates the last occurrence of
gers and finds the location of the last even integer in the the smallest element in a finite list of integers, where the
list or returns 0 if there are no even integers in the list. integers in the list are not necessarily distinct.