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, and subsequently a professor of Computer and Information Science at the University of California in San Diego. Sadly, Ron passed away during the summer of 2020. 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:
This course will be taught in HCB 315.
Meeting Time:
Tuesdays and Thursdays: 8:00AM-9:15AM
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.
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
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:
Office hours will be M at 8:30-9:30: https://fsu.zoom.us/my/mascagni. Email me if you are waiting and I am not there, I sometimes forget.
Teaching Assistant: N/A
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: