Computer Science 582/482
Maple Flavored Concrete Mathematics
Summer 2012

[ Concrete Math | Maple | Problems | Links | Schedule ]

Grad Students: Do you use discrete mathematics in your research?

Undergrad Students: Do you want to learn more about symbolic computation packages?

Discrete mathematics, in one form or the other, makes its way into almost every computer science thesis. Most computer science students have taken a discrete math course as part of their undergraduate training, but quite often they find that they've forgotten this material and now need some part of it for their thesis research or simply want to go into it in further depth, particularly with regard to computational tools. In the past, some grad students have sat through Math 222 and other mathematics courses, but this is often not a satisfactory solution because of the slow pace and elementary treatment. This course is designed as a thorough introduction, at the graduate / advanced undergraduate level, to those areas of discrete mathematics (exclusive of graph theory), that are most useful to the average computer science researcher. There are many software tools available to aid in discrete mathematical computations, and among the best of these is Maple. An up-and-coming open source program that has many of the same features as Maple is Sage. We will use Maple and/or Sage as a resource throughout the course, and try to uncover some of the internal algorithms that these symbolic computation programs use. There will be some guest lecturers who are experts on Maple and Sage. The course will also be of great use to highly motivated mathematically mature undergraduate students who want a more in-depth coverage of topics in discrete mathematics, particularly those who plan to go on to graduate studies. But be forwarned, the treatment is advanced; you will be seeing and doing proofs, and you must do proofs in order to pass the course.

The only prerequisites for this course are some previous exposure to discrete mathematics (combinations, permutations, induction, etc.) and a beginning programming course (including recursion). You will be expected to do proofs and write little programs.

Concrete Mathematics

The text for this course is Concrete Mathematics by Graham, Knuth, and Patashnik. It is one of the finest Mathematics textbooks ever (imho). It has its own Wikipedia entry (rather sparse). The best description of this text is the one given by the authors themselves in the preface, a copy of which has been placed outside my office door (ECS 564). The following chapter headings should give you an idea of the contents of the book and the course: Recurrent Problems, Sums, Integer Functions, Number Theory, Binomial Coefficients, Special Numbers, Generating Functions, Discrete Probability, Asymptotics. You are advised to obtain the second edition of the book and not the first edition.

Maple

Maple is a wonderful symbolic computation system, developed in Canada. Many of our graduate students have found it extremely useful in their research. On the other hand, I've read several theses that contained page after page of detailed (and error prone) algebraic manipulation that could have been handled quite easily by a small Maple program. The use of a symbolic computation system like Maple should be in the bag of tricks of every graduate student. Maple costs money, but the student version is around $100 and Maple 15 has been installed in the linux lab (ECS 242) for you to use.

There is no text for this portion of the course. There may be some handouts and some books on reserve. Here's a picture of those books: .

A collection of Maple examples relevant to the course will be maintained.

Sage

Sage is an open source alternative to Maple. It is based on python, and is sometimes part of python distributions. You should install it on your machine. There are several Sage gurus in our geographical area and some of these will come to the class to tell us about the latest Sage developments.

Some Relevant Links:

OEIS

 The Online Encyclopedia of Integer Sequences (OEIS) is another tool that we will be using extensively in the course. Several students from previous incarnations of this course have the results appearing in the OEIS. If you are really serious about integer sequences, then you should consider subscribing to seqfan. Good student projects are sometimes found by extending sequences that are in OEIS (search with "keyword:more").

Please note that this course is being taught as a compressed summer course in the May-June term. Thus it meets 6 hours per week for approximately 7 weeks.

Instructor

Instructor: Frank Ruskey
Office: ECS 564
Office hours: TWF 2:00-3:00 or by appointment
Phone: 472-5794

Grading

Course grading is based on six 20 minute in-class quizes (6.5% each, 50% total marks), and 6 homework problem sets (39% of mark). You are allowed to collaborate on solving homework problems, but what is turned in must be individually prepared and you must identify your collaborators on your submission. A tentative schedule of due dates for homework and dates of quizes are shown below and on the schedule. All students will have to undertake a project based on some aspect of the course material, and graduate students will be required to make a brief presentation to the class based on their project. Marks will be converted to grades using the standard computer science conversion scale.

Time

The class is scheduled TWF 10:30-12:30, in CLE B315 DSB C126.

Assignment List

Answers

Project ideas

Where to find Maple

In the linux lab (ECS 242) you will find Maple 15. (The latest version of Maple is Maple 16, but this will not affect us). Here is what the systems person had to say about using it: "As usual, Maple can be started as 'maple' at the command line or as 'xmaple' for the GUI".

Probable Schedule

Click here .

Important Notes

Term marks, provisional final grades and final grades will be posted by student number minus the first two digits with no name. These postings are for your information and for your validation of the data entry. If you do not wish your term marks and grades publicaly posted in this manner, please notify the course instructor by e-mail no later than May 25, 2012.

Note also the departmental guidelines on fraud, computer account usage and accommodation for religious observances.