CMP337: Discrete Mathematics

Syllabus

Fall 2003

"When I use a word," Humpty Dumpty said, in a rather scornful tone, "it means just what I choose it to mean -- neither more nor less."
"The question is," said Alice, "whether you can make words mean so many different things."
"The question is," said Humpty Dumpty, "which is to be master-- that's all."
-- Lewis Carrol, "Through the Looking Glass"

Instructor

Nancy Griffeth

Department of Mathematics and Computer Science

Gillet 201C

Email: ngriffet@lehman.cuny.edu

Telephone: 718 960-8787

Office Hours: Tuesday and Thursday, 2-3 pm, and by appointment

You can also leave messages for me in my mailbox in the department office, Gillet 211.

Exams

Two midterms and a final

Midterms are tentatively scheduled for:

October 14

November 18

Please do not miss a scheduled exam. The makeup will be harder.

Assignments and Quizzes

There will be weekly assignments. I will not collect the assignments, but I will give occasional pop quizzes using questions from the assignments.

Textbook

Richard Johnsonbaugh, Discrete Mathematics, Fifth Edition, Prentice-Hall, 2001.

Course Description and Objectives

This course will introduce the mathematical material that all computer scientists should know.

The objectives of the course are:

To study mathematical structures and topics that are frequently used in computer science;

To examine some of the applications in computer science; and

To develop a basis for studying more advanced topics.

Class Attendance

I will take attendance in every class. Please e-mail, phone, or leave me a note if you have to miss a class.

Course Outline

This represents my best guess at how we will approach the course, but we may modify it as the term progresses.

Week	Topic	Reading
Sep 2	Logic and Proofs	Sections 1.1-1.3
Sep 9	Mathematical Induction	Sections 1.4, 1.6
Sep 16	Sets, sequences, number systems, relations	Sections 2.1-2.4
Sep 23	Equivalence relations, relational databases, functions	Sections 2.5, 2.7, 2.8
Sep 30	Exam I Introduction to Algorithms	Sections 3.1, 3.2
Oct 9	Algorithm Examples	Sections 3.3, 3.4
Oct 16	Algorithm Complexity, Counting	Sections 3.5, 4.1
Oct 23	Permutations and Combinations	Sections 4.2, 4.6
Oct 30	More combinatorics	Sections 4.7, 4.8
Nov 6	Exam II Introduction to Recurrence relations	Section 5.1
Nov 13	Solving and Using Recurrence Relations	Sections 5.2, 5.3
Nov 20	Graph Theory	Sections 6.1-6.3
Dec 2	Trees	Sections 7.1, 7.2
Dec 9	Finite State Automata	Sections 10.1-10.2