MATH 250: Discrete Mathematics

Kalamazoo College

Spring 2009

Readings & Assignments

Reading Assignments, Projects and Presentations will be listed here in chronological order, i.e., with the most recent ones at the bottom of the list.

All reading assignments are from the textbook, Mathematical Structures for Computer Science by Gersting, unless specified otherwise.

This document was last modified on May 29, 2009.

Date assigned Reading
(to discuss next time)		 Problems to try
(for next time)		 Problems to hand in
(Well written)		 Due Date
(for hand-in problems)
March 30 
 1.1
Section 1.1 Practice Problems 1-8 (in the reading)
 Write a one-page introduction of yourself, including your background in both mathematics and computer science, why you are taking this course, and what you hope to learn in this course.
Be ready to rank the presentation choices and/or propose another topic. 		April 1
April 1
 1.2 A pair of sentences that mean the same thing, one using "if . . . then" and the other NOT using this connective.

1.1: 3, 4, 5, 6, 7, 8, 13a, b, 29a, b, 31, 35, 36, 42 (Do you recognize 35 & 36 as anything in particular?)

1.2: Practice Problems 9 - 14

The presentation schedule is now available. Presentations will be at the beginning of class on Fridays, unless other arrangements are made in advance.

 1.1: 6, 14, 17c, g, i, 20d, 28, 32, 43, 44 April 6
April 3 
 1.3 1.2: 1, 4, 7, 10, 13, 33, 45

Which of the rules listed in Table 1.14 on p. 33 are in fact equivalence rules? Can you justify your answers?

1.3: Practice Problems 15 - 21

Given that p implies q is false, is (p' V q') implies q true or false?

1.2: 6, 11, 14, 17, 28, 36, 40, 42, 49

Challenge Problems: Prove or disprove any of the arguments listed.

 April 8
April 6
 1.4 1.3, 1.4: See these exercises on quantifiers.
Carefully read p. 40.
Translate the following statements into predicate wffs:
  1. For every positive integer n there exists a prime p such that p > n.
  2. There exist two primes p and q whose sum is also prime.
  3. For all rational numbers x and y, the sum x+y is rational.
  4. Every even integer n >= 4 is the sum of two primes p and q.
1.3: 2e-h, 11, 18, 21, 26 April 10
April 8
 Keep reading 1.4 See "To try" problems from April 6.    
April 10   Calvin's presentation

Code examples used in presentation: example 1, example 2, example 3, example 4, example 5, example 6, example 7, example 8

 1.4: 6, 9, 11, 19, 31, 34

Calvin's problems

April 15
April 13 & 15
 2.1 2.1: Practice Problems 1-6 2.1: 5, 8, 18, 21, 29, 31, 36, 57, 59, 69 April 20
April 17
 2.2

Kristap's presentation on Boolean Algebra and Circuits

 2.2: Practice 8, Exercises 1, 15, 33 2.2: 2, 6, 30, 51, Kristaps's two questions.

Challenge: Section 2.2 #64

 April 22
April 20
 3.1 3.1: Practice Problems 1-21

2.2: 12, 26, 40, 44, 70

Exam 1 is going to be Wednesday of 5th week.

 April 24
April 22
 Keep reading 3.1 3.1: Exercises 9, 13, 28, 52 3.1: 6, 7, 19, 29, 34b, c, f, 36, 46d-g, 62 April 27
April 24
Brad's presentation on Euclidean algorithm   Brad's two problems: Section 2.3 #6, 7 May 1
May 1
4.1 4.1: Practice Problems 1-16 3.1: 75, 89

4.1: 3, 7, 11, 12d, f, h, 13d, f, h, 26, 33, 35, 39, 41

Project 1 will be due Wednesday, May 6 instead of Monday, May 4.

May 6
May 4
4.4 - pp. 331-342, 348-354 4.4: 2, 6, 7, 8, 12, 28, 33 4.4: 10g-l, 11, 16, 27, 36 May 8
May 8
2.4 2.4: Practice Problems 16, 17, 21 4.4: 61, 62, 71

Eric's two questions on fuzzy logic and fuzzy sets: Section 1.1 #38, Section 3.1 #76

Show that 1k+2k+...+nk = theta(nk+1).

May 13
May 11
2.5 2.4: 32, 35 2.4: 17, 24 (Challenge), 27, 34, 41, 43, 45, 51

2.5: 3, 32, 35

May 18
May 13
3.2 3.2: Practice Problems 22-25 3.2: 4, 6, 23, 34, 35, 36, 42, 43, 44, 46, 52, 56, 58, 63, 71 May 22 (Note the date change!)
May 18
3.3, 3.4 3.4, 3.4: Practice Problems 26-35 3.3: 3, 7, 11, 16, 20, 23, 26 May 22
May 22
Vince's Chinese Remainder Theorem Presentation   3.4: 4, 12, 13, 21, 22, 24, 28, 31, 36, 47, 50, 56, 57, 72, 76, 83(Challenge)

Vince's two problems on the Chinese Remainder Theorem

May 27
May 27
3.5, 3.6 3.5, 3.6: Practice Problems 36 - 43 3.5: 7, 10, 12, 28, 31, 36, 38, 39-42, 61(Challenge - uses conditional prob.)
Report your results from playing "Let's Make a Deal" 10 times, twice. For the first 10 times, do not switch which door you want. For the second 10 times, switch your choice every time. 		June 1
May 29
5.1

Dan's Coin Weighing Presentation

Read pp. 366 - 377 Jay's two problems:
  1. Use Pascal's Triangle to evaluate C(8,6).
  2. Expand (x + y)7 using the Binomial Theorem.

Dan's problem: There is exactly one counterfeit coin among thirteen coins, you have a balancing scale and a 14th coin which you know to be real. Devise a weighing scheme to determine the counterfeit coin and whether or not it is lighter or heavier than the other coins in 3 measurements. (Hint: use the Association Method used in the presentation)

4.5: 14a, 15b, 21, 23

 June 3
June 1
 5.2, 5.3 5.2, 5.3: Practice problems 18-26 5.1: 7, 12, 15, 16, 26, 64, 75b, 81

5.2: 6, 18, 23, 52

June 5
June 3
 5.4, 6.2 5.4: Practice problems 27-29

6.2: Practice problems 7-11