Bryn Mawr College
CS231/Math231: Discrete Mathematics
Spring 2015
| General Information | Syllabus and Schedule | Text |
Gradings |
| 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) |
| 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 Reading: 1.1-2, 4.2 |
4.2: 7, 25, 30 Exercise 1-4 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.1-3.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 1-5, 2.2 | |
| 4 |
2/10 |
Equivalences Involving Quantifiers Reading: 3.3 |
3.3: 11f, 12d, 21e, 24b, 36, 38 Exercise 2-3 from Predicate Logic notes |
|
| 2/12 |
More Operations on Sets Reading: 6.1-6.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(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 |
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 2-5 from induction notes |
|
| 3/5 |
Class canceled because of bad weather |
|
||
| 8 |
3/10 |
Spring Break! | ||
| 3/12 |
||||
| 9 |
3/17 |
Strong Induction, Well-ordering Principle, Classic Theorems about Irrationality Reading: 5.4, 4.7 Recurrence Relation Reading: 5.6-5.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 2-5(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.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 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.3-9.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 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.
Lectures in Discrete Mathematics by Bender and Williamson
Created by Jia Tao on Jan 8, 2015.