Computer Algebra I (CS 680-503)

 Announcments  Lectures  Programs  Course Resources   Assignments  Grading Policy
Course Announcement
The department of Mathematics and Computer Science is offering a two term graduate sequence (Computer Algebra I & II) in computer algebra algorithms during the Winter 99-00 and Spring 99-00 terms. The first course is numbered CS680 section 503 and meets on Wed. from 6-9.

This course is of interest to computer science, mathematics, science, and engineering students who are interested in understanding the algorithms underlying computer algebra systems such as Maple. It is also of interest to students interested in computational mathematics, algorithm design and analysis, and complexity theory.

This course is open to advanced undergraduates and may be used for either the numeric computing or the algorithms tracks.

See syllabus fo more details.

Course Description
This course serves as an introduction to the foundations of symbolic mathematical computation, drawing from both computer science and mathematics. Topics to be covered typically include: the algebraic definition of numerical, polynomial and rational function domains, notation for computing time analysis, arithmetic with large integers, rational numbers and multivariate polynomials, modular number arithmetic, greatest common divisors of polynomials (rational function simplification), computing with homomorphic images and the Chinese Remainder Theorem, the modular GCD algorithm.
Audience
Graduate computer science, mathematics, engineering, and science students interested in learning about the algorithms underlying computer algebra systems such as MAPLE. The course is appropriate for students interested in computational mathematics, algorithm design and analysis, and complexity theory.

This course is also open to upper level undergraduates interested in algorithms design and analysis and computational mathematics. The course counts towards either the numeric and scientific computing track or the algorithms and data structures track for computer science students.
Prerequisites
Algorithms and Data Structures I (CS 557 or equivalent)
Courses in calculus, linear algebra. Some knowledge of abstract algebra is helpful but not necessary.
Instructor
Jeremy Johnson
Office: 271 Korman Center
phone: 895-2893
e-mail: jjohnson@mcs.drexel.edu
office hours: MW 1-3, and T 4-6. Additional hours by appointment.
Meeting Time
W 6:00-9:00 in Randell 329
Textbook
  1. Keith Geddes, Stephen Czapor, and George Labahn Algorithms for Computer Algebra. Kluwer Academic Publishers, 1992.
  2. Maple V Computer Algebra System. The student edition is available for purchase. Access to Maple is available through department and university computers.
  3. The text will be supplemented by several journal articles and readings from texts available in the library.

Topics

  1. Algebra of polynomials, Rational functions, and power series.
  2. Data structures and algorithms for polynomial arithmetic.
  3. Homomorphisms, modular algorithms, interpolation and the Chinese Remainder Theorem.
  4. Newton's iteration and Hensel lifting.
  5. Polynomial greatest common divisors.
  6. Polynomial factorization.

Grading

  1. Homework assignments (five @ 10%) (50%)
  2. Programming projects (50%)

Resources

Reference Books
  1. to be added.
Web Pages
  1. Waterloo Maple
  2. Maple V Application Center
  3. SymbolicNet -- Symbolic Mathematical Computation Information Center
  4. IMACS Conferences on Applications of Computer Algebra

Look Here for Important Announcemen ts

Announcements (Last posted Feb. 25 @ 10:00 am)

Lectures

This list is tentative and may be modified at the instructor's discretion.
  1. Jan. 5, 2000 (The Integers, Modular Arithmetic, and the Euclidean Algorithm - Chapter 2)
  2. Jan. 12, 2000 (Polynomial Algebra - Chapters 2)
  3. Jan. 19, 2000 (Polynomial Representations and Data Structures - Chapters 3)
  4. Jan. 26, 2000 (Basic Arithmetic Algorithms - Chapter 4)
  5. Feb. 2, 2000 (Computing Time Analysis of Basic Arithmetic Algorithms- Chapter 4)
  6. Feb. 2, 2000 (Computing Time Analysis of the Euclidean Algorithm- Chapter 4)
  7. Feb. 17, 2000 (Chinese Remainder Theorem and Modular Algorithms - Chapter 5)
  8. Feb. 24, 2000 (Computing Time Analysis of Polynomial Arithmetic - Chapter 7)
  9. Mar. 1, 2000 (Polynomial Remainder Sequences - Chapter 7)
  10. Mar. 8, 2000 (Modular Polynomial GCD Algorithm - Chapter 7)
  11. Mar. 15, 2000 (Final project due)

Programs and Worksheets

Assignments
Created: 12/22/99 by jjohnson@mcs.drexel.edu