Bryn Mawr College
CS231/Math231: Discrete Mathematics
Fall 2014
| 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/fall2014/ |
| Lecture: |
Mondays & Wednesdays, 1:10-2:30pm |
| Room: | Park 338 |
| Office Hour: | Thursdays 3:50-5:30pm |
| TAs: |
Angela Mastrianni: Thursdays 8:30pm-9:30pm Park 231 Harry Okun: Fridays 4pm-5pm Hilles 110 (Haverford) Maggie Xiao: Fridays 3-4pm Park 231 Ziye Lin: Fridays 11:30-12:30pm Hilles |
| Week | Date | Topic | Assignments | Collected |
|---|---|---|---|---|
| 1 |
9/1 |
No Class |
|
|
| 9/3 |
Introduction, Deductive Reasoning and Logical Connectives, Truth Tables Reading: 2.1 |
2.1: 5, 8, 10, 13, 17, 36, 46, 54 | ||
| 2 |
9/8 |
Logical Equivalences, Variables and Sets Reading: 2.3(pp51-53), 1.1-2 |
6.1(I): 1, 3, 7, 12, 16, 17, 18, 20, 25 |
|
| 9/10 |
Rational Numbers, Operations on Sets Reading: 1.1-2, 4.2, 6.1(pp336-346) |
4.2: 7,10,18,25,30 Exercise 1-2 from Propositional Logic notes |
||
| 3 |
9/15 |
Conditional and Biconditional Connectives Reading: 2.2 Digital Logic Circuits Reading: 2.4 |
2.2: 10,14,15,16,18,20,35,41,43,50 Exercise 3-5 from Propositional Logic notes 2.4: 21,23 |
2.1, 6.1(I), 4.2, Exercises 1-2 |
| 9/17 |
Proof Techniques,
Direct Proofs, Divisibility Reading: 2.3, 4.3, 4.4 |
2.3: 10,13,23,28,29,32,37,39,42 4.3: 13,16,21,33,39,43,49 4.4: 24,30,37,50 |
||
| 4 |
9/22 |
Proof by Contradiction, Predicates and Quantified Statements Reading: 4.6, 4.7, 3.1, 3.3(pp117-122) |
4.6: 4,7,22,28,29 4.7: 2,6,15,17,24 3.1: 4c,8,13,18,20,29,32 Exercise 1 from Predicate Logic notes |
2.2, 2.3, 2.4, 4.3, 4.4, Exercises 3-5 from Propositional Logic notes |
| 9/24 |
Equivalences Involving Quantifiers Reading: 3.2-3 |
3.2: 2,8,10,14,25c,46,47 3.3: 4c,11f,12d,21e,24b,36,38,57,58 Exercise 2-3 from Predicate Logic notes |
||
| 5 |
9/29 |
More Operations on Sets, Set Identities Proofs Involving Quantifiers Reading: 3.4, 6.1-6.2, 6.3(pp370-372) |
3.4: 11,12,13,14,15,19,20,24,32 6.1(II): 27e, 33c, 35d 6.2: 14,19,22 6.3: 7,20,37 Review Exam1 |
4.6,4.7,3.1, Exercise 1, 3.2, 3.3 |
| 10/1 |
More Examples of Proofs Reading: 4.1 |
4.1: 28,36,41,42,56 | ||
| 6 |
10/6 |
Halting Problem and Diagonalization, Sequences and Summation, Number Systems Reading: 6.4, 5.1, 2.5 |
5.1: 15,28,50,79,87 Exercise 1 from Mathematical Induction notes 2.5: 6,12,26,36,37,40,46 |
Exercise 2,3 (Predicate), 3.4, 6.1(II), 6.2, 6.3, 4.1 |
| 10/8 |
Exam1 | |||
| 7 |
10/13 |
Fall Break! | ||
| 10/15 |
||||
| 8 |
10/20 |
Mathematical Induction Reading: 5.2-5.3 |
5.2: 7,11,26 5.3: 5,7,15,28 Exercise 2-5 (induction notes) |
5.1, Exercise 1 (induction) |
| 10/22 |
Strong Induction Reading: 5.4 |
5.4: 2, 15, 18, 19, 21, 27 | ||
| 9 |
10/27 |
Algorithms, Correctness of Algorithms Reading: 4.8,5.5 |
4.8: 8b, 16, 20, 24,28 5.5: 5, 9, 11 |
2.5, 5.2,5.3,5.4, Exercise 2-5 |
| 10/29 |
Recurrence Relation Reading: 5.6-5.7 |
5.6: 14, 20, 21, 30 5.7: 11, 36, 44, 51 |
||
| 10 |
11/3 |
Recursion Reading: 5.8-5.9 |
5.8: 9, 15, 24 5.9: 8, 11, 14(b), 18, 23 Exercise 6-7 (induction) |
4.8, 5.5, 5.6, 5.7 |
| 11/5 |
Counting, Basic Principles Reading: 9.1 |
9.1: 6, 13(b), 19, 22, 25 |
||
| 11 |
11/10 |
Combination and Permutation, Pascal's Triangle Reading: 9.7 |
9.7: 7, 15, 16, 40, 42 Exercise 1 (Counting) |
5.8, 5.9, Exercise 6-7, 9.1 |
| 11/12 |
Exam 2 | |||
| 12 |
11/17 |
Generalized Permutation and Combination Reading: 9.2, 9.5, 9.6 |
9.2: 2, 15, 18, 33, 40, 42 9.5: 7, 14, 16, 20, 28, 34, 37 9.6: 4, 7, 15, 18 |
9.7, Exercise 1 |
| 11/19 |
Inclusion/Exclusion rule, Pigeonhole Principle Reading: 9.3-9.4 |
9.3: 2, 7, 12, 17, 22, 30, 43, 44 9.4: 11, 18, 21, 28, 34 |
||
| 13 |
11/24 |
Probability Reading: 9.8-9.9 |
9.8: 6, 15, 18, 21, 22, 23 9.9: 15, 24, 29, 30, 32, 33 |
9.2, 9.5, 9.6, 9.3, 9.4 |
| 11/26 |
Relations, Properties of Relations, Equivalence Relations Reading: 8.1-8.3 |
8.1: 2, 11, 18, 23 8.2: 13, 21, 26, 38, 39, 52 Exercise 1 (Relations) 8.3: 26, 30, 33 |
||
| 14 |
12/1 |
Graphs, Representations of Graph, Reading: 10.1-3 |
10.1: 1,3,5,12,31,32,46 10.2: 4,12,14,19,23,28 10.3: 2a,3a,5a,6a,15,20 |
9.8, 9.9, 8.1, 8.2, Exercise 1, 8.3 |
| 12/3 |
Isomorphisms of Graphs, Trees Reading: 10.4-5 |
10.4: 1, 14 10.5: 3,8,10,22,26 |
||
| 15 |
12/8 |
Rooted Trees, Binary Trees Reading: 10.6 |
10.6: 1,8,10,11 | |
| 12/10 |
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 Mondays.
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 Aug 8, 2014.