Computer Science CSC478/2412 Spring 1997

St. George Campus University of Toronto

Homework Assignment #2

Due: Tuesday, 11 February 1997

Mark: 15%

**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.

**References**

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.

Wed Jan 29 17:11:27 EST 1997