Bryn Mawr College
CS231/Math231: Discrete Mathematics
Spring 2015

 General Information Syllabus and Schedule Text Gradings

### General Information

 Instructor: Jia Tao E-Mail: jtao@cs.brynmawr.edu When you e-mail 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:55pm-2:15pm Room: Park 338 Office Hour: Wednesdays 10am-12:30pm or by appointment TAs: Angela Mastrianni (amastriann@brynmawr.edu): Thursdays 8:30-10:00pm Park 231 Mary Boman (mboman@brynmawr.edu): Tuesdays 6:00-7:30pm Park 231 Ziyan Yang (zyang@brynmawr.edu): Wednesdays 7:00-8:30pm Park 231 Daniel Lugano (dlugano@haverford.edu): Sundays 4:00-5:30pm Yarnall House Common Room (Haverford)

### Syllabus and Schedule

This is a tentative syllabus and schedule. Topics, reading assignments, and due dates are subject to change.
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(pp51-53), 1.1-2, 6.1(pp336-346)
2.1: 5, 8, 10, 13
6.1(I): 7, 12, 17, 18, 20
1/22
2
1/27 Rational Numbers, Operations on Sets
4.2: 7, 25, 30
Exercise 1-4 from Propositional Logic notes
1/29
Conditional and Biconditional Connectives
2.2: 10, 15, 18, 20, 35, 41, 43, 50
Exercise 5 from Propositional Logic notes
2.1, 6.1(I)
3
2/3
Proof Techniques, Direct Proofs, Indirect Proofs, Proof by Contradiction, Proof by Contraposition
2.3: 10, 13, 23, 37, 38
Exercise 6-7 from Propositional Logic notes
2/5
Predicates and Quantified Statements, Equivalences Involving Quantifiers
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 1-5, 2.2
4
2/10
Equivalences Involving Quantifiers
3.3: 11f, 12d, 21e, 24b, 36, 38
Exercise 2-3 from Predicate Logic notes
2/12
More Operations on Sets
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(pp370-372), 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 2-3,
6.1(II), 6.2, 6.3, 3.4, 4.1
6
2/24
Exam1
2/26
Review of Exam 1 Sequences and Summation
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 2-5 from induction notes

3/5
Class canceled because of bad weather 5.1, Exercise 1(Induction)
8
3/10
Spring Break!
3/12
9
3/17
Strong Induction, Well-ordering Principle, Classic Theorems about Irrationality
Recurrence Relation
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 2-5(induction)
10
3/24
Recursion, Strong induction and Structural Induction
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
Exam 2
Counting, Basic Principles, Combination and Permutation, Combination, Pascal's Triangle
Reading: 9.1-9.2, 9.5(pp565-571), 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
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
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
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
10.6: 1,8,10,11
4/30
Exam 3

### Important Dates

January 20: First lecture
April 30: Last lecture

### Text & Software

 Discrete Mathematics with Applications, 4th Edition by Susanna Epp, Thomson Learning 2010. Errata (Please check here if you think you found a mistake in the text or have undue confusion)

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 610-526-7351 in Guild Hall, as soon as possible, to verify their eligibility for reasonable accommodations. Early contact will help avoid unneccessary inconvenience and delays.