COT 5507: Analytic Methods in Computer Science
(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:


8:00AM to 9:15AM: 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:

Sharanya Jayaraman

Office: 106B MCH

Office Hours: T 2:00PM-4:00PM, W 12:30PM-2:30PM

E-mail: jayarama@cs.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 attednance, 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 Student Disability Resource Center; (2) bring a letter to the instructor indicating the need for accommodation and what type. This should be done during the first week of class.

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:

  1. N. J. A. Sloan's On-Line Encyclopedia of Integer Sequences
  2. Sequences from Graham, Knuth and Patashnik's Concrete Mathematics
  3. Sage, a free open-source mathematics software system
  4. The Shodor Sage server