MAD 2502 (sec 13301): Introduction to Computational Mathematics
The course provides an introduction to the use of computers for solving mathematical problems. The course explains the basics of the Python Programming Language and demonstrates how a programming language can enable and support the solution of mathematical problems. The course does not assume prior programming experience and does not aim at an in-depth understanding of the details of Python. Rather the focus is on understanding concepts and techniques of how programming can help to expand the spectrum of tractable mathematical problems.
The course will not follow a particular book, but parts of the introduction to Python will be based on tbe book J. Campell, P. Gries, J. Montojo, G. Wilson: Practical Programming. An Introduction to Computer Science Using Python. (The Pragmatic Programmers, 2009).
More information on the course is available in the syllabus, and comments are welcome.
Topics Discussed in Class
- 01/12/10: computer algebra systems vs. general purpose programming languages, Python as a calculator
References: Python Programming Language -- Official Website, The Python Tutorial -- Section 3
- 01/14/10: using IDLE; working with if, for and while
References: One Day of IDLE Toying, The Python Tutorial -- Section 4.1-4.4
- 01/19/10: Python's slice notation, examples of simple algorithms: exponentiation with square and multiply, evaluating polynomials with the Horner scheme; Homework 1 is available
References: The Python Tutorial -- Section 3.1.2, [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 4.3, Ch. 5.2]
- 01/21/10: functional programming tools in Python: filter(), map(), reduce(), algorithm example: sieve of Eratosthenes
References: The Python Tutorial -- Section 5.1.3, [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 18.4]
- 01/26.10: importing functions and modules, making use of methods to work with lists and strings, introduction to the Miller-Rabin primality test
References: The Python Tutorial -- Section 5.1, Section 6.1 and Section 6.6.1, [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 18.3]
- 01/28/10: review of if, for and while; implementing the Euclidean algorithm with a while loop; Miller-Rabin primality test
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 3.1, Ch. 18.3]
- 02/02/10: Miller-Rabin primality test; solution of Homework 1; Homework 2 is available
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 3.1, Ch. 18.3]
- 02/04/10: ElGamal encryption
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 3.1, Ch. 18.3, Ch. 20.4]
- 02/09/10: ElGamal encryption; reading and writing files in Python
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 3.1, Ch. 18.3, Ch. 20.4], The Python Tutorial -- Section 7.2
- 02/11/10: accessing internet resources by URL in Python; examples for solving a problem by means of recursion (Fibonacci numbers,, Tower of Hanoi)
References: The Python Standard Library -- Section 21.5
- 02/16/10: sorting recursively I: Quicksort; Homework 3 is available
- 02/18/10: sorting recursively II: Merge sort; applying sorting to a problem in mathematics: baby-step giant-step algorithm
References: [A. Menezes, P. van
Oorschot, and S. Vanstone: Handbook of Applied Cryptography, CRC Press: Ch. 3.6.2]
- 02/23/10: Big Oh notation, Master Theorem for Recurrences
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 25.7], Master Theorem: Practice Problems and Solutions
- 02/25/10: Karatsuba's multiplication algorithm
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 8.1]
- 03/02/10: solution of Homework 3, review of exponentiation with square and multiply; Exam 1 is available
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 4.3]
- 03/04/10: Strassen algorithm for matrix multiplication; sets and dictionaries in Python
References: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 12.1], The Python Tutorial -- Section 5.4 and Section 5.5
- 03/16/10: errors and exception handling in Python
References: The Python Tutorial -- Section 8
- 03/18/10: computing with permutations in Python: representation, composition
- 03/23/10: computing with permutations in Python: inverse, cycle notation
- 03/25/10: introduction to Python classes; Homework 4 is available
Reference: The Python Tutorial -- Section 9
- 03/30/10: an example for writing a class in Python -- rational numbers
Reference: J. W. Shipman's rational.py: An example Python class
- 04/01/10: writing a Python function to find the periodic part in the decimal expansion of a rational number
- 04/06/10: implementing Floyd's cycle-finding algorithm ("tortoise and the hare") in Python
Reference: [J. von zur Gathen, J. Gerhard: Modern Computer Algebra, Cambridge University Press: Ch. 19.4]
- 04/08/10: exceptions as classes, writing a program to invert a matrix; Homework 5 is available
Reference: The Python Tutorial -- Section 9.8
- 04/13/10: writing a program to invert a matrix
- 04/15/10: making use of iterators and generators in Python
Reference: The Python Tutorial -- Section 9.9 and Section 9.10
- 04/20/10: implementing polynomial division in Python
- 04/22/10: exercise for the final exam: printing terms of a polynomial with free choice of variable names
- 04/27/10: exercise for the final exam: a recursive variant of the extended Euclidean algorithm
The final exam will take place on Thursday, April 29, 1:15-3:45 pm in room SE 271 (computer lab).
You can bring any books, manuscripts, and printouts you like. Internet access will be restricted to the domain python.org. Windows versions of IDLE with Python 2.6 are available in the lab, but you can work with your own laptop as well.
For questions or comments, please feel free to contact me anytime
(see my homepage for email, phone number, etc.).
Apr 28, 2010