Meetings: MWF 12:10pm-1:00pm, PHYSICS 140.

Instructor: Jesús A. De Loera.

email: deloera@math.ucdavis.edu

http://www.math.ucdavis.edu/~deloera/TEACHING/MAT165/

Phone: (530)-554 9702

Office hours: Monday and Wednesday 1:10pm-2:00pm or by appointment. My office is 3228 Mathematical Science Building (MSB). The TA for this class is Mr. Mohamed Omar. His office hours are Thursdays 10am-11am at room 2125 MSB. We will be glad to help you with any questions, concerns, or problems.

Prerequisites and expectations: This class is intended for Math and CS majors in their junior or senior year. It is necessary that you have a solid idea of how to write proofs and true familiarity with computer programming (say as in ECS 30). In particular you will have to learn MAPLE. If in doubt please ask me about it.

You are expected to work outside the classroom programming, thinking about the theorems and exercises, etc. I estimate a minimum of 3 hours work at home per lecture. The most important thing is what YOU learn by doing. Math and CS are not spectator sports!

Text: The only mandatory text for this course is

• Ideals, Varieties and Algorithms , by Cox, Little and O'Shea, Springer UTM.

• Using Algebraic Geometry, by Cox, Little and O'Shea, Springer, GTM.

• Modern Computer Algebra, by von zur Gathen and Gerhard, Cambridge Univ,

• Solving Polynomial Equations, by Sturmfels, CBMS 97, American Math Soc.

Software: This class will use MAPLE as the software for class discussion, tests, homeworks, projects, etc. Due to logistic reasons, no other software will be allowed. A very useful resource, an e-book about MAPLE, is accessible to all UC Davis students for free in the electronic book (you do not need to buy this book!):

Maple and Mathematica :a problem solving approach for mathematics by Inna Shingareva and Carlos Lizarraga-Celaya, Springer, 2009, online resource (xviii, 483 p.).

To access the book there is a SpringerLink free to all UC campuses e-book about MAPLE

If you wish to access the book from outside campus internet, then you can do this using the VPN link of the library (go to the UCD library link).

Finally (NOT required) but a great text for all about MAPLE is

``An introduction to MAPLE'', by A. Heck, Springer, 2006.

Description of this Course: : This course has two goals:

1) To introduce undergraduate students to Algebraic/Symbolic Computation. This is the part of mathematics dedicated to algorithms where the answer is to be computed exactly. This is complementary to the area of numerical analysis (MATH 128ABC) where answers are computed with limited precision and error.

2) It is now undeniable that computers are useful tools for finding counterexamples, discover patterns, and even proof theorems! For example, the proof of the four color theorem, investigation of fractals, etc. Thus, the second goal of the course is to learn how computers are useful tools for mathematical research, experimentation and can even help to generate formal proofs automatically. In fact, knowing how to use computers can go a long way toward solving a math problem (e.g. see the wonderful site of Project Euler ).

Course outline: In general what I will try to do is to cover the first four chapters of the text book, plus some scientific applications.

(weeks 1-2) Motivation, Introduction to MAPLE and Symbolic Computation. The algebra of univariate polynomials,
Euclid's algorithm and GCD of polynomials. Real and rational roots of univariate polynomials (Sturm sequences and Descartes's rule of signs).

FIRST PROJECT DUE.

(week 3-4) Ideals and Varieties, Multivariate systems of polynomial equations, monomial ideals, term orders and Multivariate Division Algorithm.

FIRST MIDTERM

(week 5-6) Groebner bases and Buchberger's algorithm

SECOND PROJECT DUE

(week 7-8) Solving systems of multivariate polynomial equations. Elimination theory, Hilbert's Nullstellensatz and unsolvable systems.

SECOND MIDTERM

(week 9-10) Applications. Engineering problems (e.g. Robotics), Automatic Theorem proving.

THIRD PROJECT DUE (last day of classes)

FINAL EXAM

Grading policy:

• There will be 2 midterms, first on April 22, the second on May 20, each counting 35 points. Several questions will come from homework assignments. There are also three projects (they will include programming for sure but also thinking and reading researching etc). Each project is worth 15 pts. For both midterms and projects I will drop the lowest score. problems. Finally there will be a final exam (or final project if the class is of reasonable size) is worth 35 points. The final exam will take place June 4th at 8:00AM!!

  Important: Each week I assign 5-10 problems for you to practice what is being covered. Although we wont collect those problems, you can count some will appear in each midterm and the final!!

• As you see, there are 100 points possible in this course. I will assign grades based on the statistical information obtained (I compute the mean, standard deviation, etc.) and set letter grades according with those numbers. Nevertheless, it is my rule that at least 60 points are required to pass the class.

• Please remember there are NO make-up exams or late homeworks, instead I am dropping the lowest scores as a compensation of possible problems or emergencies.

• I will handle all grades via the smartsite grade system. You can access grade information for this class via the internet. You can see your standing in the class, important statistics on exams, and your final grade there.

Class Computer Accounts

To provide you with free access to MAPLE please open an account at the mathematics department. Please go to:

http://www.math.ucdavis.edu/comp/class-accts

and follow the instructions. These accounts expire at the end of the quarter.

Homeworks and Handouts

homework 1

Here is the maple worksheet I showed in my introduction on the first day of the class.

Please read Computers and the meaning of Proof this article from Scientific American (a bit old now)

Here is the second MAPLE worksheet that I showed to introduce you to MAPLE on our first LAB session. maple_crashcourse.

Here is a third MAPLE worksheet about univariate polynomials.. Here you can also download more code to manipulate univariate polynomials, but not as a worksheet.

Here is pseudocode of the extended euclidean algorithm Also you can find a step by step example computation with some suggestion of MAPLE commands that will be useful when you implement it.

homework 2 Contains more problems for the first midterm

Here is a piece of MAPLE code that should help you with using Groebner bases
and solving systems of polynomials Groebner MAPLE code .

Here is a list of some review problems for the first midterm

----------------MIDTERM 1 up to here-----------------------------

homework 3 contains problems for the second midterm.

homework 4 last set of problems to be covered in second midterm

Here are two pieces of MAPLE code that were demonstrated in class. The first is on how to use Groebner bases to solve system of equations Groebner commands and applications. You can also download code for the cyclohexane equations. Finally here is a second worksheet with applications to Graph theory and Logic

We are having our second Midterm on Friday May 20, at the computer laboratory. Here are some review problems for second midterm. Solutions for the computational problems using MAPLE are posted here Here is the MAPLE code that solves the numerical problems, first in mw format,
then in a text version (not for xmaple) text .

----------------MIDTERM 2 up to here-----------------------------

homework 5 Final homework!

We learned about Hilbert's Nullstellensatz and its applications to logic, graph theory, automatic theorem proving. Here are the lecture transparencies used in class to discuss the Linear Algebra approach to decide feasibility of polynomial systems

Here are the MAPLE solutions for problems 3, 2B,2A of midterm 2. Here is the text version.

-----------------------------------------------------------------

Our final exam will be a final project. You can choose from one of the 2 projects proposed in class (logic computation or integer programming) OR you can make your own project! For details and rules please consult the MAPLE worksheet about the final projects . NOTE: You must receive my approval if you are doing a project you designed.

You can find my transparencies about the logic satisfiability problem Davis Putnam and NP-completeness . Even ore information about the Davis-Putnam algorithm implementation to solve logic satisfiability problem is also available. You can also download the brilliant survey lecture by Bernd Sturmfels about Groebner bases . It includes our short introduction to integer programming.

All final Projects are due at 12:00noon June 9. They MUST be submitted in a single maple worksheet that will run at least 3 examples when executed.