a. What is the value of q(7,2)?
b. Can we determine q(0,0)?
c. Can we determine q(-3, -4)?
2. Let a be an array of type float and i and n be positive integers. The function
m(a,i,n) is defined by
a. Find m(a,i,n) if i = 1, n = 6, and a is
b. What does m(a,i,n) do?m(a,i,n) = a[i] if i = n and max(m(a,i + 1,n) ,a[i]) if i < n
0. 6.8
1. 3.2
2. -5.0
3. 14.6
4. 7.8
5. 9.6
6. 3.2
7. 4.0
?/FONT>(i + n)/2?/FONT> means, "Do an integer divide of (i + n)/2."
a. Find m(a,i,n) for i = 1, n = 6, and a the array of Exercise 2.
b. What does m(a,i,n) do?
4. Let i be a nonnegative integer. Find b(4) where
5. Write a recursive function max corresponding to Exercise 2.
6. Write a recursive function max corresponding to Exercise 3.
7. a. Why does the recursive solution to the Towers of Hanoi problem use the minimum number of moves?
b. What is the number of moves it uses?
8. Consider the following nonrecursive algorithm for the Towers of Hanoi problem.
1. Label the disks 1, 2, . . ., n in increasing order of size.
2. Label the pegs i, a, and ?/FONT>, respectively, n + 1, n + 2, and n + 3.
3. Move the smallest disk onto another disk with an even label or onto an empty peg with an even label.
4. If all disks are on the same peg, then terminate. Move the second smallest top disk onto the peg not containing the smallest disk. Go to 1.
a. Convince yourself that this correctly solves the Towers of Hanoi problem.
b. Is the recursive solution or this nonrecursive version easier to understand.
9. Suppose a fourth peg is added to the Towers of Hanoi problem.
a. Write a recursive solution for this problem.
b. Can you find a recursive solution that uses the minimum number of moves for this problem?
10. Mark any n distinct points on the circumference of a circle. How many triangles may be drawn whose vertexes lie on three of the n points?
11. How many ways may k distinct points be selected from the n points of Exercise 10?
12. Given a permutation of 1, 2, . . ., n, let ni be the number of integers to the right of i which exceed i. For the permutation 2134, n1 = 2, n2 = 3, n3 = 1, n4 = 4. Write a process function that will turn permutations into a program that prints n1, n2, . . ., nn for each permutation.
13. Suppose 1 is implemented as a two-way list. Write a recursive function to reverse 1.
14. Implement the function of Exercise 5.
15. Implement the function of Exercise 6.
16. Compare the requirements for the stack storage required during execution for the implementations of Exercises 5 and 6.
17. Why are the more efficient versions of Section 4.4 more efficient?
18. The Fibonacci sequence is defined by
a. Write a recursive function fibonacci(n) to compute and print ?/FONT>(n).
b. Analyze its time and storage requirements.
19. a. Translate the program of Exercise 18 and obtain as efficient a version as you can.
b. Analyze its time and storage requirements.
20. Write a nonrecursive program fibonacci(n), which takes O(n
21. a. Write a function element with parameter k, which returns the value of the kth element on the stack of integers implemented as in Figure 4.8. For instance, if k is 1, it returns the value of the current first element. It does not disturb the stack at all. Assume you do not have access to the stack directly, but only through the push, pop, and empty routines.
b. Same as Exercise 21(a), except assume you do have direct access to the stack.
22. Two stacks are implemented in one array of length 1,000 as shown. The tops of the stacks are pointed to by top1 and top2 and grow toward each other. Write a procedure push that pushes the contents of v onto the stack indicated by s. s will have a value of 1 or 2. If the stack to which v is to be added is full, then push should not add it, but should return with s set to 0.
23. Write a function maxstack that returns in m the maximal element on a stack of integers implemented with pointer variables. Maxstack will return true when the stack is not empty, and false otherwise.
24 What does the following do?
25. Why are parentheses not needed when prefix or postfix notation is used?
26. How do conventions eliminate ambiguity in infix notation?
27. Evaluate the postfix expression 3 6 + 6 2 / *8+.
28. Simulate the execution of the algorithm of Section 4.6.2 for evaluation of an infix expression on (a * b/(c + d)) + e ** ?/FONT>.
29. Simulate the execution of the translation algorithm of Section 4.6.3 on (a * b/(c + d)) + e ** ?/FONT>.
30. What priority must be given to the assignment operator, =, if the evaluation and translation algorithms for infix to postfix are to work on assignment statements as well as arithmetic expressions?
31. Write the function evaluate.
32. Describe how evaluate must be modified if arithmetic expressions are allowed to include function calls.
33. What will the pairing generated by the function determine be for the input sequence aa([[]()])zz?
34. Modify the function determine so that it outputs the pairs as follows:
35. Modify function determine so that it also outputs ( ( ( ) ) ( ) ), for example, if the input is ( ( ( ) ) ( ) ).
4 2 1 1 2 3 3 4
36. How must determine be modified if some left characters may also be right characters, and they will always match each other? For example, let the left characters be a, (, [,b, with the "right" characters being a, ), ], b. Here a is matched with a, b with b, "("with ")," and "[" with "]." Then a[a] is not valid, but a[CC](aa)a and ab()aab[]a are.
37. Write the remove function for the array implementation of a queue.
38. Write the insert function for the pointer variable implementation of a queue.
39. Write the remove function for the pointer variable implementation of a queue.
40. Suppose function buffer has three parameters, q of type queue, e of type whatever, and op of type character. If op is r, then buffer returns after removing the top record of the queue and copying its value into e. If op is n, then buffer returns after inserting the value in e at the bottom of the queue. Write an implementation of buffer, assuming that access to the queue is only through the empty, remove, and insert routines.
41. A deque (pronounce like "deck") is a data abstraction that retains ordered information, but allows insertion and deletion at both its front and rear.
a. Develop an array-based implementation of a deque and write corresponding setdeque, insertf, insertr, removef, remover, and empty routines.
b. Do the same as in Exercise 41(a), except use pointer variables with dynamic storage allocation for the deque implementation.
42. Suppose there is a program to keep track of the current board configuration in a game of Monopoly by using a circular array of records, each record representing a board position (such as Boardwalk), and queues for Community Chest and Chance. Discuss how the records should be defined, what pointers to records will be convenient, and how these pointers and the circular array should be processed on each turn.
b(0) = 1
b(n) = b(0) ?/FONT> b(n - 1) + b(1) ?/FONT> b(n - 2)
+ b(2) ?/FONT> b(n - 3) + . . . + b(n - 1) ?/FONT> b(0) n>0
?/FONT>(0) = 0, ?/FONT>(1) = 1
?/FONT>(n) = f(n - 1) + ?/FONT>(n - 2) for n = 2,3,4 . . .
pop(&s,&value);
push(&value,&s)
1 2 3 4 5 6 7 8
if ( ( ( ) ) ( ) ) is the input sequence,
then the output will be the pairs 3 4, 2 5, 6 7, 1 8.