CS 64 Home Page

This is the Fall 2009 home page for the course CS 64: Discrete Structures: Introduction to analytic and formal methods of computer science with practical examples, including analysis of data structures, recursion relations, proof methods, and logic programming, (Credit not given for more than one of CS 64, MATH 52 opr 54.) Corequisite: One semester of programming, MATH 20 or 22.

(N.B., the content of this page changes frequently.)

General Information:

Instructor: Robert R. Snapp (e-mail).
Office Hours (in 353 Votey): Tues. 1:30 – 2:30 p.m., Wed. 1:30 – 3:00 p.m., Fri. 10:00 – 11:00 a.m., and by appointment.
Teaching Assistant: Tianyu Cao. Office hours, Wednesday 3:00–4:00 pm. and Friday, 9:30–10:30am. in Room 369 Votey. (e-mail).
Lectures on Monday, Wednesday and Friday, in Room 209 Votey, 4:05pm–4:55pm.
Pop quizzes can occur on any day!
Midterm Exams (in class): Wednesday, October 7, and Friday, November 13.
Final Exam: 3:30 – 6:30 p.m., Friday, December 18, 2009.

Required Textbooks:

During the first twelve weeks of the course we will discuss topics described in Edward Bender's and Gill Williamson's text books, listed below. During the last three weeks (or so), we will study one of the most influential papers in computer science: Alan Turing's “On computable numbers, with an application to the Entscheidungsproblem,” published in 1936. Although, this paper is normally only accessible to graduate students, Petzold's recent commentary helps explain this scientific landmark to the general reader.

Edward A. Bender and S. Gill Williamson, A Short Course in Discrete Mathematics, Dover, Mineola, NY, 2005. (The entire content of this book can be downloaded from the first author's web site: http://math.ucsd.edu/~ebender/DiscreteText1/index.html)
Edward A. Bender and S. Gill Williamson, Mathematics for Algorithm and Systems Analysis, Dover, Mineola, NY, 2005. (The entire content of this book can also be downloaded from the first author's web site: http://math.ucsd.edu/~ebender/DiscreteText2/index.html)
Charles Petzold, The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computatbility and the Turing Machine, Wiley, New York, 2008,

(available at the UVM Bookstore, and from amazon.com, barnesandnoble.com, and borders.com.)

Assigned Reading:

Download the two textbooks by Bender and Williamson in their entirety, and read I:BF1, that is, Section 1 of Unit BF (Boolean Functions) in the first textbook: A Short Course in Discrete Mathematics, by Wednesday, September 2, 2009.
Read I:BF2 by Wednesday, September 9, 2009.
Read the syllabus for CS 64 and UVM's Code of Academic Integrity and I:Lo1 by Friday, September 11, 2009.
Read I:Lo2 by Monday, September 14, 2009.
Read I:SF1 and I:SF2 by Friday, October 2, 2009.
Read Aaron F. Archer's ``A Modern Treatment of the 15 Puzzle.'' [ps], by Friday, October 16, 2009. (Also available from www.jstore.org, via this link. If you are on a computer in UVM's network domain, you should be able to download a pdf image of the published article from the previous site by clicking PDF on the right menu.)
To complete our unit on functions please read II:Fn1, II:Fn2. and II:Fn3, if you have not already done so.
For our discussion on counting tricks review I:SF1 and I:SF2 (Example 12), and read II:CF1, II:CF2 and II:CF3. (The latter section is essentially a rewording of I:SF1 with the addition of multinomial coefficients.) Please try to read these sections by Friday, Oct. 30, 2009.
Read Unit I:NT1 and I:NT2 by Friday, Nov. 6, 2009.

Homework Assignments:

Homework 1: Download my Notes on Boolean Functions, and solve the ten exercises in Section 5. Your complete and clear solutions are due at the beginning of class on Friday, September 11, 2009. Please show all of your work for full credit. Good Luck!.
Homework 2: Download hw2.pdf and complete all ten exercises. Written solutions are due at the beginning of class on Wednesday, September 23, 2009. Please show all of your work for full credit. Good Luck!
Homework 3 Download settheory.pdf and complete all ten exercises that appear at the end of the document. Written solutions are due at the beginning of class on Wednesday, October 7, 2009. Please show all of your work for full credit. Good Luck!
Homework 4 Complete the assignment hw4.pdf by Friday, October 30, 2009.
Homework 5 Complete the assignment hw5.pdf by Friday, December 4, 2009. Also, by this date, please turn in your corrected solutions to the problems that you answered incorrectly on Midterm 2.

Handouts:

Most handouts are availabe in pdf format, a page description language supported by Adobe Acrobat. If you do not have Acrobat Reader for your personal computer, you can download it for free from Adobe.

syllabus [pdf].
UVM's Code of Academic Integrity [pdf] (10 pages).
Notes on Boolean Functions [pdf]
Notes on Set Theory [pdf]

Scheme Programming:

Although the emphasis of this course is analytic, it will be convenient on occasion to illustrate our findings with short computer programs. In this regard, I recommend the DrScheme implementation of the scheme programming language.

www.drscheme.org has free versions of the Dr. Scheme programming environment, for Mac OS X, Unix, and Microsoft Windows, that you can download.
How to Design Programs is an introduction to computer programming, written by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi, the developers of Dr. Scheme. The full text is available on line. Highly recommended!
The syntax of the scheme programming language is concisely described in R. Kent Dybvig's The Scheme Programming Language, second edition, Prentice-Hall, Upper Saddle River, NJ, 1996. (The link should direct you to an on-line copy of the textbook.)
The textbook Structure and Interpretation of Computer Programs, by Harold Abelson and Jay and Julie Sussman, is available on line. It is used as an "introductory" textbook at MIT, and is based on scheme.