Syllabus

Math S-104 - Discrete Mathematics with Computer Science Applications

Summer, 2005
Last Updated 6/1/2005

Instructor

Dr. William Robinson, Research Advisor, ALM in IT program
robinson@fas.harvard.edu
617-496-9736

Course Assistant

Text

K. H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill (5th edition), 2003

Just as calculus is a core requirement for studies in engineering and physics, discrete mathematics provides a critical set of tools for anyone working in Information Technology or Computer Science.

This course has three primary goals:

To provide you with a set of mathematical principles and techniques that are applicable to all the areas we discuss
To provide you with a set of basic information in the topics we have selected for coverage
To provide you with exercises that will develop your skill at applying the principles and techniques to concrete problems in computer science.

In broad terms, the areas to be covered include:

Logic and proof techniques, including induction and recursion
Sets and functions
Combinatorics
Graph Theory

Each of these could be a course in itself, and we will follow a narrow path through them.

Homework, Examinations, and Grading

Graded Work	Points
There will be weekly homework assignments, each due at the beginning of class each Monday (except July 4). No assignments will be accepted late.	100
There will be three one-hour exams. Exams are closed book. The tentative dates are listed below.	100 each
There will be one three-hour final exam, also closed book.	200
Students taking the class for graduate credit are required to write a set of programs. All programs must be turned in on time. Instructions will be given in the assignments.	100 each

Caution: Summer School is very fast-paced. Since the topics we cover build on previous topics, falling behind a class or two can be disastrous.

Note for distance students

This course has classroom-based hourly and final examinations. Distance education students residing in the six-state New England area (Connecticut, Maine, Massachusetts, New Hampshire, Rhode Island, and Vermont) must take all classroom examinations on-campus as scheduled. Distance education students residing outside the New England area must make arrangements through Academic Services to take their examinations in absentia in a proctored setting in a school local to the student. To do so students must submit a completed Distance Education Proctored Examination Form at least one week in advance of the examination. The table below shows the course schedule, including tentative hourly examination dates. We will let you know a week in advance if any of the hourly exam dates change. The final exam date is fixed.

Additional information and forms regarding examinations may be downloaded from the Summer School website [https://ac-web.dce.harvard.edu/procx/]. Students should direct their questions about this procedure to Academic Services, (617) 495-0977.
) Homeworks are due on Mondays. Distance education students can either fax their solutions to 617-384-8395 or scan them into a document and email the solutions to robinson@fas.harvard.edu. In the latter case, please zip the file to reduce its size, and name the file with your last name and date (e.g., robinson0707.zip)

Course Sections

There will be a review section each Thursday at 4:30 in Room L01 at 53 Church Street. The teaching assistant will lead the sections.

Topic Coverage

Topic	Sections of the Text	Lectures
Foundations: -Logic, sets, and functions -Growth rates of functions	1.1-1.8 2.1-2.3	1,2,3
Mathematical induction and recursion	3.1-3.6	4,5
Combinatorics	4.1-4.5, 6.5, 6.6	6,7, (8)
Relations	7.1, 7.3-7.5	(8), 9
Graphs	8.1-8.7	10, 11, (12)
Trees	9.1-9.5	(12), 13

We will omit Chapters 5, 10, and 11, as well as selected topics within the sections above.

Class Timeline

The boxes on the right emphasize the rapid nature of the Summer School curriculum by indicating the 'Virtual Months' in a more traditional Fall Term. Each Summer School lecture corresponds to a week for a Fall course that meets three times a week.

Lecture	Day of Week	Date	Comment
1.	Monday	6/27	First Lecture
2.	Wednesday	6/29	First Section
	Monday	7/4	Holiday
3.	Wednesday	7/6	First Assignment Due
4.	Monday	7/11	Next Assignment Due
5.	Wednesday	7/13	First one-hour test
6.	Monday	7/18
7.	Wednesday	7/20
8.	Monday	7/25	Second one-hour test
9.	Wednesday	7/27
10.	Monday	8/1
11.	Wednesday	8/3
12.	Monday	8/8	Third one-hour test
13.	Wednesday	8/10	Last Lecture
	Monday	8/15	Examination Period Begins - No class. The S-104 Final will be a 3-hour exam given on Wednesday, 8/17 at 6 pm.