# Spring, 2000

John Smith
Carney 316
552-3763
smithj.@bc.edu

## Class Meetings

The class will meet  Monday, Wednesday and Friday at 12:00 in Carney 310

## Course Content

We will cover the basic ideas from the first eight chapters.  The following schedule is tentative, but should give a pretty good idea of what the course is about.

 1 W Jan. 19 1.1 Log ic 2 F 21 1.2 Propositional calculus 3 M 24 1.3 Predicates and quantifiers 4 W 26 1.4 Sets 5 F 28 1.5 Set operations 6 M 31 7 W Feb 2 1.6 Functions 8 F 4 4 2 Divisibility 9 M 7 3.1 Methods of proof 10 W 9 3.2 Induction 11 F 11 12 M 14 3.3 Recursive definitions 13 W 16 14 F 18 Exam 15 M 21 4.1 Basics of counting 16 W 23 17 F 25 4.2 Pigeon hole 18 M 28 4.3 Permutations and combinations 19 W March1 20 F 3 4.4 Discrete probability 21 M 13 22 W 15 5.1 Recurrence relations 23 F 17 24 M 20 5.2 Solving recurrences 25 W 22 Exam 26 F 24 6.1 Relations on sets 27 M 27 28 W 29 6.4 Closures 29 F 31 6.5 Equivalence relations 30 M April 3 6.6 Partial orderings 31 W 5 32 F 7 7.1 Introduction to graphs 33 M 10 7.2 Terminology 34 W 12 7.3 Representing graphs and graph isomorphism 35 F 14 7.4 Connectivity 36 W 19 8.1 Introduction to trees 37 W 26 Exam 38 F 23 General review 39 M May 1

## Textbook

Text: Discrete Mathematics and its Applications, Kenneth Rosen

For a collection of interesting links organized according to chapter of the text by the author, try. http://www.mhhe.com/math/advmath/rosen/.
For an amusing game related to Example 10, page 248 try http://www.dbai.tuwien.ac.at/proj/ramsey/.

## Required Work

Homework Homework will be assigned most days.  Unless another date is specified, homework is due two class days after it is assigned.  This provides an intermediate day for questions--you should take advantage of this by looking at the homework soon enough to determine whether you know how to do it or need to ask questions.
Solutions to problems should be written out in sufficient detail that a person familiar with the course material can follow the reasoning.  This may involve some calculations, a bit of English prose, a diagram or two, or maybe some combination.  Answers substantially identical to those in the back of the book are worthless.
Students are encouraged to work together on problems, but what is submitted must reflect each student's understanding of the problem.

The final grade will be 1/6 for each of the 50 minute exams, 1/3 for the final, and 1/6 for the homework

Homework assignments

Assignment  8

Assignment 9 p. 185, Solutions p 185

Assignment 10. p 200, Assignment 10 solutions

Assignment 11. p 242:  16, 18,24,25,26  Solutions

Assignment 12 p. 242: 21,22,28,38, p. 248 9,13,14,25 Solutions p 242 p 248

Assignment 13 p 257 9,12,13,16,18,26  Solutions

Assignment 14. p 257  20,22,30,32,39,50 Solutions

Assignment 15 p 265 Solutions

Assignment 16 p 316 Solutions

Assignment 17 p 329  Solutions

Assignment 18  382: 5,22,23

Assignment 19  395 9,10,14.

Assignment 20  p 407 16,17,18,19,25,29 p413: 14,17

Assignment 21 p 248: 26,35,50

Exam 3 Solutions Problems 1, 2, 3, 4,5