Bryn Mawr College
CS231/Math231: Discrete Mathematics
Spring 2015
General Information  Syllabus and Schedule  Text 
Gradings 
Instructor:  Jia Tao 
EMail: 
jtao@cs.brynmawr.edu
When you email me, make sure you put "CS231" at the start of the subject line to ensure a quicker response. 
Website:  http://cs.brynmawr.edu/Courses/cs231/spring2015/ 
Lecture: 
Tuesdays & Thursdays, 12:55pm2:15pm 
Room:  Park 338 
Office Hour:  Wednesdays 10am12:30pm or by appointment 
TAs: 
Angela Mastrianni (amastriann@brynmawr.edu): Thursdays 8:3010:00pm Park 231 Mary Boman (mboman@brynmawr.edu): Tuesdays 6:007:30pm Park 231 Ziyan Yang (zyang@brynmawr.edu): Wednesdays 7:008:30pm Park 231 Daniel Lugano (dlugano@haverford.edu): Sundays 4:005:30pm Yarnall House Common Room (Haverford) 
Week  Date  Topic  Assignments  Collected 

1 
1/20 
Introduction, Deductive Reasoning and Logical Connectives, Truth Tables,
Logical Equivalences, Variables and Sets Reading: 2.1, 2.3(pp5153), 1.12, 6.1(pp336346) 
2.1: 5, 8, 10, 13 6.1(I): 7, 12, 17, 18, 20 

1/22 

2 
1/27 
Rational Numbers, Operations on Sets Reading: 1.12, 4.2 
4.2: 7, 25, 30 Exercise 14 from Propositional Logic notes 

1/29 
Conditional and Biconditional Connectives Reading: 2.2 
2.2: 10, 15, 18, 20, 35, 41, 43, 50 Exercise 5 from Propositional Logic notes 
2.1, 

3 
2/3 
Proof Techniques, Direct Proofs, Indirect Proofs, Proof by Contradiction, Proof by Contraposition Reading: 2.3 
2.3: 10, 13, 23, 37, 38 

2/5 
Predicates and Quantified Statements, Equivalences Involving Quantifiers Reading: 3.13.2 
3.1: 4c, 8, 18, 32 Exercise 1 from Predicate Logic notes 3.2: 2, 10, 25c, 46, 47 
6.1(I), 4.2, Exercise 15, 2.2  
4 
2/10 
Equivalences Involving Quantifiers Reading: 3.3 
3.3: 11f, 12d, 21e, 24b, 36, 38 Exercise 23 from Predicate Logic notes 

2/12 
More Operations on Sets Reading: 6.16.2 
6.1(II): 33c, 35d 6.2: 14, 19, 22 
2.3, 3.1, Exercise 1, 3.2  
5 
2/17 
Set Identities, Proofs Involving Quantifiers Reading: 6.3(pp370372), 3.4, 4.1, 
6.3: 7, 20, 37 3.4: 13, 15, 19, 20, 24 4.1: 28, 41, 42 

2/19 
More Examples of Proofs Involving Quantifiers, Divisibility Reading: 4.3, 4.4, 4.6 
4.3: 13, 21, 33, 39 4.4: 24, 30, 37 4.6: 4, 7, 28, 29 6.1(III): 27e 
3.3, Exercise 23, 6.1(II), 6.2, 

6 
2/24 
Exam1  
2/26 
Review of Exam 1
Sequences and Summation Reading: 5.1 
5.1: 15, 28, 50, 79, 87 Exercise 1 from induction notes 
6.3, 3.4, 4.1, 4.3, 4.4, 4.6, 6.1(III)  
7 
3/3 
Number Systems, Mathematical Induction
Reading: 2.5, 5.2, 5.3, 
2.5: 6, 12, 36, 40, 46 5.2: 7,11,26 5.3: 5,7,15,28 Exercise 25 from induction notes 

3/5 
Class canceled because of bad weather 


8 
3/10 
Spring Break!  
3/12 

9 
3/17 
Strong Induction, Wellordering Principle, Classic Theorems about Irrationality Reading: 5.4, 4.7 Recurrence Relation Reading: 5.65.7 
5.4: 2, 15, 18, 19, 21, 27 4.7: 2, 6, 15, 17 5.6: 14, 20, 21, 30 5.7: 11, 36, 44, 51 

3/19 
5.1, Exercise 1(Induction), 2.5, 5.2, 5.3, Exercise 25(induction) 

10 
3/24 
Recursion, Strong induction and Structural Induction Reading: 5.9 
5.9: 8, 11, 14(b), 18, 23 Exercise 6 from induction notes 

3/26 
5.4, 4.7, 5.6, 5.7, 5.9, Exercise 6  
11 
3/31 
Counting, Basic Principles, Combination and Permutation, Combination, Pascal's Triangle Reading: 9.19.2, 9.5(pp565571), 9.7 
9.2: 15, 18, 33, 40, 42 9.7: 7, 15, 40, 42 Exercise 1 from Counting notes 

4/2 
Exam2 
No assignment due today


12 
4/7 
Combination, Pascal's Triangle  
4/9 
Generalized Permutation and Combination Reading: 9.5, 9.6 
9.5: 7, 14, 16, 20, 28 9.6: 4, 7, 14, 18 
9.2,9.7, Exercise 1  
13 
4/14 
Inclusion/Exclusion rule, Pigeonhole Principle Reading: 9.39.4 
9.3: 2, 7, 12, 17(a)(b), 24 9.4: 11, 18, 28, 34 

4/16 
Probability, Conditional Probability, Bayes' Formula Reading: 9.1, 9.8, 9.9 
9.1: 6, 13(b), 19, 22 9.8: 6, 15, 18, 21, 22 9.9: 15, 24, 29, 30 
9.5, 9.6  
14 
4/21 
Graphs, Representations of Graph Trails, Paths, Circuits Reading: 10.1, 10.3, 10.2 
10.1: 1,3,5,12,31,32,46 10.3: 2a,3a,5a,6a,15,20 10.2: 4,12,14,19,23,28 

4/23 
Trees, Characterizing Trees Reading: 10.5 
10.5: 3,8,10,22,26 
9.3,9.4,9.1,9.8,9.9 No submission is accepted after today. 

15 
4/28 
Rooted Trees, Binary Trees Reading: 10.6 
10.6: 1,8,10,11  
4/30 
Exam 3  

There are three exams. Homeworks consist of problem sets. All homeworks and exams will receive a numerical score. Guidelines of letter grades corresponding to lab/exam score levels will be given during the semester. At the end of the semester, a total score (to which the corresponding final grade is assigned) will be calculated from a weighted average of all scores according to the following weights:
Homeworks: 25%
Exams: 25% each
Total: 100%
Homework: You are encouraged to work together on the homework, but you should write up your own solutions. Homework that is more than a week late will not be graded. You are allowed two late homeworks (late = after the due date, but less than or equal to one week after the due date!). Homeworks are collected once a week, on Thursdays.
Extensions: Tests may not be taken late without advanced permission. Extensions are usually granted ONLY for family emergencies, infirmary or hospical stays, or similiar major crises.
Special Accommodations: Students who think they may need accommodations in this course because of the impact of disability are encouraged to meet with us privately early in the semester. Students should also contact Deb Alder, Coordinator of Accessibility Services, at 6105267351 in Guild Hall, as soon as possible, to verify their eligibility for reasonable accommodations. Early contact will help avoid unneccessary inconvenience and delays.
Lectures in Discrete Mathematics by Bender and Williamson
Created by Jia Tao on Jan 8, 2015.