CSE 417 Assignment #4
Winter 2001

Due: Wednesday, February 28, 2001.

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

2. Build a pattern matching finite automaton for the string 010010011 over the alphabet {0,1}.

3. Describe how you might simulate a Turing machine in your favorite programming language.

4. Let B be the set of all infinite sequences of 0's and 1's. Show that B is uncountable.

5. (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₃6 is worse than log₂3. There are extra bonus points for getting an algorithm with running time exponent log₃5.)