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 upandcoming 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 indepth 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.
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 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.
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 MayJune term. Thus it meets 6 hours per week for approximately 7 weeks.
Instructor
Instructor: Frank Ruskey
Office: ECS 564
Office hours: TWF 2:003:00 or by appointment
Phone: 4725794
Grading
Course grading is based on six 20 minute inclass 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:3012:30, in CLE B315 DSB C126.
Assignment List
Answers
Project ideas

Feline
Josephus problem.

Neil wants help

Odd Enumeration

Transfer Matrix Method. See the book:
Stanley, Enumerative Combinatorics, Volume 1.

WZ method. See the book: A=B.

Automatic Sequences. See the book by Allouche and Shallit.

Algebraic generating functions.

The ThueMorse Sequence
(paper).

Contribute to Sage.

Euler zigzag numbers and the boustrophedon transform.

Counting trees; labelled trees, rooted trees, free trees.
For counting labelled trees there is a very nice book by John Moon.

Lagrange inversion and its use in combinatorics.

Fast algorithms for finding the longest increasing subsequence
(e.g., in a permutation). See Knuth vol 3, etc.

John Conways Fractran Game. E.g., as used to generate primes.
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 email no later than May 25, 2012.
Note also the departmental
guidelines
on fraud, computer account usage and accommodation for
religious observances.