# CSE 417 Assignment #4

Winter 2001

### Due: Wednesday, February 28, 2001.

- Karatsuba's algorithm was defined for multiplying two polynomials.
Modify it to handle binary integers with asymptotically the same running time.
(The main new thing you will need to concern yourself with is the impact
of carries.) Set up the recurrence you would get for doing it this way.
- Build a pattern matching finite automaton for the string
010010011 over the alphabet {0,1}.
- Describe how you might simulate a Turing machine in your favorite
programming language.
- Let B be the set of all infinite sequences of 0's and 1's.
Show that B is uncountable.
- (Bonus) Modify Karatsuba's algorithm based on splitting the
polynomials into 3 pieces instead of two. (You will probably end up with
a worse algorithm on your first try since log
_{3}6 is worse than
log_{2}3. There are extra bonus points for getting an algorithm
with running time exponent log_{3}5.)