Computer Science CSC478/2412 Spring 1997
St. George Campus University of Toronto
Homework Assignment #2
Due: Tuesday, 11 February 1997
1. Problem 5, page 106 of the textbook. Put f(x,y) and g(x,y) into the four normal forms discussed in Section 3.5 of the textbook, that is, factored/factored, factored/expanded, expanded/factored, expanded/expanded, with numerator and denominator relatively prime in each case.
2. Problem 6, page 107 of the textbook.
3. Prove that the extended Euclidean algorithm for over Z the and alternate in sign, that is, and are positive, and and are negative, for all . Prove that and are monotonically increasing for .
4. This exercise gives the cost of the EEA over the integers. Let us represent the integers in binary with leading bit equal to 1. The binary length of a positive number a is the number of bits in the binary representation of a, that is, .
a. Show that the bound is exponential in the input size .
b. Prove the polynomial upper bound . Hint: first show that for ; then, consider the product on both sides of the previous inequality for ; finally, conclude that . [In fact, it is possible to prove a better upper bound for : using Fibonacci numbers. The average length is also known: (see Knuth 1981; §4.5.3).]
c. Consider the number of bit operations as the cost measure. This concept can be formally defined as the number of steps in a Turing machine or the number of gates of a Boolean circuit implementing the algorithm (for instance, see Aho, Hopcroft and Ullman, Ch. 1). Give the cost of one division step using the ``school" division. The cost should be analogous to the one proven in class for division of polynomials with the only difference of possible carries during subtractions.
d. Prove the following theorem.
Theorem. The EEA for integers of binary length at most n bits can be performed with bit operations.
Hint: use the same proof as the one for polynomials.
5. This exercise shows an application of the Chinese remainder algorithm.
a. Develop an algorithm for solving systems of linear equations with integer and rational coefficients by using the Chinese remainder algorithm. Implement your algorithm in MAPLE. You are allowed to use the MAPLE procedure Solve mod p, but not Solve over the integers or rational numbers. Test your algorithm with the examples in pages 151 and 404 of the textbook.
b. Apply your algorithm to solve the following linear equations for n=4,5,6,7:
c. Use your algorithm and interpolations to solve:
where a is a parameter.
6. Problem 14, page 332 of the textbook.
A. V. AHO AND J. E. HOPCROFT AND J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading MA, 1974.
K. O. GEDDES AND S. R. CZAPOR AND G. LABAHN, Algorithms for Computer Algebra, Kluwer Academic Publishers, Boston, 1992.
D.E. KNUTH, The Art of Computer Programming, vol.2: Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading MA, 1981.