Week 1, 2 and 3.
Click on the Help menu (on the right at the top of the Maple window), select Introduction, and click on the "New User's Tour". This also contains useful information for new users. Spend a few hours this week to find out what kind of commands are available in Maple. Every hour you spend now will save you a lot of time in the programming exercises later in the semester.
We will look at this worksheet number systems in class. Write an implementation of Karatsuba multiplication. Turn it in on Friday September 17.We will study this worksheet on gcd's and Extended Euclidean Algorithm in class. We have covered most of chapters 1 and 2 of the book. Study these two chapters carefully, and make sure you understand them. If some things are not clear please let me know. Note that some of the algorithms are different from the ones in the worksheets, the ones in the worksheets tend to have fewer loops and more recursion. The actual computations will be equivalent though.
Week 4, 5, 6, 7 and 8.
We will study this worksheet on FFT and worksheet on p-adic numbers in class.
Turn in homework:
Use the Maple procedure "Factors(f) mod p" and the HenselLift procedure in the worksheet on p-adic numbers to factor the following polynomial in the same way as in the worksheet:
More turn in homework:
Write an algorithm for Hensel lifting in the ring Q[[x]]. Do this in the same way as in the worksheet on p-adic numbers. The following worksheet contains an algorithm for Hensel lifting in Q[[x]] that only works when the factors have degree 1: worksheet on x-adic Hensel lifting, i.e. Hensel lifting with formal power series.
Turn in the following assignment about the evolute and these three assignments. Turn in date: Friday Oct 29.
Week 9 and 10.
Factorization in Fp[x].
Other method of factorization in Q[x].So far we have covered the material in chapters 1, 2, 3, 4 and 5.
Group work: Implement factorization in Fp[x], square-free factorization in Q[x] and Hensel lifting (these two can be copied from the worksheets above), the Landau-Mignotte bound, and factorization in Q(alpha)[x] where alpha is the RootOf an irreducible polynomial (the easiest is to use evala(Norm(..)) but you can also use a resultant).
Study the following worksheet on Polynomial Ideals and Groebner Basis. Assignment: implement the Buchberger algorithm, which is described in the last section of this worksheet.
Can you think of any reason why the Buchberger algorithm should terminate? Think about that question for a while, and after that read this worksheet on monomial ideals to find the answer.
Week 12-15. Applications of Groebner basis.
Some applications .