(A Foundation for Computer Science)

**Purpose of the course:**

This course presents mathematical
material necessary for the Computer Science student to approach
the study of many advanced topics in Theoretical Computer
Science at the graduate level. This course is modeled
after a similar course, called "Concrete Mathematics," taught at
Stanford for many years, a course that was originally developed
by Don Knuth as a mathematical complement to his "Algorithms"
course. This latter course was originally taught out notes
that became the almost sacred *The Art of Computer
Programming* book series. "Concrete Mathematics"
is thus a compendium of mathematical results required for
students to approach the subject of the "Analysis of Algorithms"
with the mathematical maturity of Knuth. In short,
"Concrete Mathematics" contains the mathematical results
required for Theoretical Computer Science minus the graph
theory.

**Textbook:**

*Concrete Mathematics: A Foundation
for Computer Science*, 2nd Edition by Ronald L.
Graham, Donald E. Knuth, and Oren Patashnik

Addison-Wesley, Boston, 1994, ISBN: 0201558025

**Background on the
Textbook/Authors:**

Don Knuth is now Professor Emeritus
of the Art of Computer Programming at Stanford University.
He is best known for his obsessive three-volume set *The Art
of Computer Programming*. During his many years at
Stanford, he was known to lurk among the shelves of the math
library collecting mathematical results on index cards for
further use. While much of the material collected could be
viewed as eclectic, the codification of those results of
singular applicability to Computer Science are what *Concrete
Mathematics* as a book and course is. Ron Graham is a
well known discrete Mathematician who was at AT&T Bell
Laboratories for many years. Ron and Don are long time
collaborators, and they co-developed the original course called
"Concrete Mathematics" that lead to this book. Oren
Patashnik was a student of Knuth's at Stanford, and helped with
the final codification of the book. The instructor has met
both Don and Oren: Don at Stanford, and Oren at the Institute
for Defense Analyses' Center for Communications Research, La
Jolla. Don and Oren are the __ultimate__
TeXperts.

**Meeting Place:**

499 Dirac Science Library

Meeting Time:

9:30AM to 10:45AM:
Tuesday and Thursday

** Prerequisites:**

The students taking this course
should either be Computer Science students, or students
extremely motivated to study mathematical foundations of
Computer Science. Students are expected to have had a
classical undergraduate course in "Analysis of Algorithms" from
a typical text book, such as *Introduction to Algorithms *by
Cormen, Leiserson, and Rivest. Such a course is Analysis
and Complexity of Data Structures and Algorithms, COP 4531,
taught at FSU. In addition, students are expected to have
had undergraduate Discrete Math I (MAD 2014) and Discrete Math
II (MAD 3105), or it's equivalent. When in doubt, please
contact Prof. Mascagni for an interview to determine a student's
suitability for this class.

**Instructor:**

Michael Mascagni, Ph.D.

Director of Graduate Studies and Professor of Computer Science

Professor of Mathematics (Courtesy)

Professor of Scientific Computing (Courtesy)

Faculty in the Graduate Program in Molecular Biophysics

Florida State University

Tallahassee, FL 32306-4530

E-mail: mascagni@fsu.edu

Office: Dirac Science Library 498/Love 207A

Telephone: +1.850.644.3290

For the curious, here are links to a brief biography of the Professor, and the Professor's home page. Also, here's a tribute to one of the authors of our textbook.

**Office Hours:**

I am either in my 498 DSL office or
my Love 207A office and my office hours are 9-10AM on Mondays
and Wednesday.

**Teaching Assistant:
**

Ms. Mukadder Sodek

Office: 102C MCH

Office Hours: M&W:
9:00-10:00AM

E-mail: ms13aj@my.fsu.edu

**Grading Policy:**

The grade will be based on examinations; however, attendance is expected. Thus, the exams will count for 90% of the final grade, and attendance, based on periodic and unannounced taking of attendance, will be the basis of the remaining 10% of the grade. All five exams will be take-home exams consisting of several problems. Each problem will be assigned points based on its difficulty, and the final grade will be based on total points earned.

**Academic Honor Code****:**

Students are expected to uphold the Academic Honor Code published in The Florida State University Bulletin and the Student Handbook. The Academic Honor System of The Florida State University is based on the premise that each student has the responsibility (1) to uphold the highest standards of academic integrity in the student's own work, (2) to refuse to tolerate violations of academic integrity in the university community, and (3) to foster a high sense of integrity and social responsibility on the part of the university community.

Please see the following web site for a complete explanation of
the Academic Honor Code.

http://www.fsu.edu/Books/Student-Handbook/codes/honor.html

http://www.fsu.edu/Books/Student-Handbook/

**Americans with Disabilities Act:**

Students with disabilities needing academic accommodation should:
(1) register with and provide documentation to the

For more information about services available to FSU students with disabilities, contact the

Student Disability Resource Center

Dean of Students Department

08 Kellum Hall

Florida State University

Tallahassee, FL 32306-4400

+1.850.644.9566 (voice)

+1.850.644.8504 (TDD)

SDRC@admin.fsu.edu

http://www.fsu.edu/~staffair/dean/StudentDisability/(This syllabus and other class materials are available in alternative format upon request.)

**Course Outline:**

Note: This outline is most likely too ambitious, and is based on the analogous chapters in the text. Thus a jaundiced eye is called for and perhaps only the ordering should be respected. Also, the links to the chapters point to

I. | Recurrent Problems and Introduction |

II. | Sums |

III. | Integer Functions |

IV. | Elementary Number Theory |

V. | Binomial Coefficients |

VI. | Special Numbers |

VII. | Generating Functions (time permitting) |

**Extra Material:**