MATH 355: Discrete Mathematics

  Winter 2020



Professor: Yevgeniy Kovchegov
e-mail: kovchegy @math. oregonstate.edu
Office: Kidder 60
Office Phone No: 7-1379
Office Hours: MW 11:00 am - 11:50 am in MSLC (Kidder 108)



Homework 20%
Midterm I 20%
Midterm II 20%
Final Exam 40%
Place and time: MWF 1:00 pm to 1:50 pm in Bexell Hall 412.

Course Content:

Textbook: Discrete Mathematics: An Open Introduction (Third Edition) by Oscar Levin.

Syllabus:  PDF file

Prerequisites: MTH 253 with a minimum grade of C-.



Timeline:

1. Logic (Sections 0.2 and 3.1) covered in lectures 1-4

2. Proof techniques and strategies (Sections 3.2) covered in lectures 5-7

3. Sets and functions (Sections 0.3 and 0.4) covered in lectures 8-10

4. Mathematical induction and recursion (Section 2.5) covered in lectures 11-12

5. Basic counting and combinatorics (Chapter 1) covered in lectures 13-16

6. Recurrence relations (Section 2.4) covered in lecture 17

7. Graph theory (Chapter 4) covered in lectures 18-25



Homework: The homework is collected at the beginning of the class. Late homework will not be accepted.

Homework #1 (due Friday, January 17):  Sec. 0.2 #11;  Sec. 3.1 #7, 9, 17   HW 1 solution key (PDF)

Homework #2 (due Friday, January 24):  Sec. 3.2 #6, 7(a), 8, 9   HW 2 solution key (PDF)

Homework #3 (due Friday, January 31):  Sec. 0.3 #10, 14, 16;  Sec. 0.4 #3, 4, 8   HW 3 solution key (PDF)

Homework #4 (due Friday, February 7):  Sec. 2.5 #10, 22;   Sec. 2.6 #14(a,b,c), 15, 16   HW 4 solution key (PDF)

Homework #5 (due Friday, February 14):  Sec. 2.6 #14(d)   HW 5 solution key (PDF)

Homework #6 (due Friday, February 21):  Sec. 1.4 #6, 8, 13;   Sec. 1.5 #9   HW 6 solution key (PDF)

Homework #7 (due Friday, February 28):  Sec. 2.4 #8, 13   HW 7 solution key (PDF)

Homework #8 (due Friday, March 6):  Sec. 4.5 #4, 5, 6, 7, 9, 10, 12   HW 8 solution key (PDF)

Homework #9 (due Friday, March 13):  Sec. 4.3 #10, 11, 14   HW 9 solution key (PDF)

Midterms: There will be two midterm exams.
Midterm 1 is scheduled for Monday, February 10 in class. The midterm is closed books. However, an 8.5 by 11 inch sheet of notes is allowed with HANDWRITTEN notes on both sides. Calculators are allowed. Midterm 1 will test what we covered in the first four weeks of the quarter. Specifically, the material in sections 0.2, 0.3, 3.1, and 3.2 that was covered in class. For preparation, it is advised that you read section 3.3 and work on the review problems in this section.

Midterm 2 is scheduled for Wednesday, February 26 in class. The midterm is closed books. However, an 8.5 by 11 inch sheet of notes is allowed with HANDWRITTEN notes on both sides. Calculators are allowed. Midterm 2 will cover the material in sections 2.5, 1.1, 1.2, 1.3, 1.4, and 1.5. For preparation, it is advised that you read sections 2.6 and 1.7 and work on the review problems in these sections.

Final Exam: Monday, March 16th. Due to COVID-19, the exam is going to be proctored on Canvas. You will need to select a two hour block that starts after 10:00 am and ends before 5:00 pm on Monday, March 16th. As the exam will be short, you are likely to spend less than two hours allocated for it. You can do the exam from home. The final exam is comprehensive and open books. It will cover the material in sections 0.2, 0.3, 1.1, 1.2, 1.3, 1.4, 1.5, 2.5, 3.1, 3.2, 4.1, 4.3, and 4.5. Please see the corresponding review sections and review problems therein.

Schedule:
Monday, January 6  Propositional Logic. Examples and applications. Sections 0.2 and 3.1. Lecture 1 slides (PDF)
Wednesday, January 8  Propositional Logic. Examples and applications. Propositional equivalences. De Morgan's Laws for negations. Sections 0.2 and 3.1. Lecture 2 slides (PDF)
Friday, January 10  Logic puzzles. Predicates and quantifiers. Section 3.1. Lecture 3 slides (PDF)
Monday, January 13  Predicates and quantifiers. Nested quantifiers. De Morgan's laws for quantifiers. Section 3.1. Lecture 4 slides (PDF)
Wednesday, January 15  Methods of Proof. Section 3.2. Lecture 5 slides (PDF)
Friday, January 17  Methods of Proof. Section 3.2. Lecture 6 slides (PDF)
Wednesday, January 22  Methods of Proof. Introduction to set theory. Sections 3.2 and 0.3. Lecture 7 slides (PDF)
Friday, January 24  Introduction to set theory. Section 0.3. Lecture 8 slides (PDF)
Monday, January 27  Introduction to set theory. Section 0.3. Lecture 9 slides (PDF)
Wednesday, January 29  Functions. Section 0.4. Lecture 10 slides (PDF)
Friday, January 31  Mathematical induction. Section 2.5. Lecture 11 slides (PDF)
Monday, February 3  Mathematical induction. Strong induction. Section 2.5. Lecture 12 slides (PDF)
Wednesday, February 5  Counting principles. Permutations. Combinations. Sections 1.1 and 1.3. Lecture 13 slides (PDF)
Friday, February 7  Review.
Monday, February 10  Midterm 1
Wednesday, February 12  Counting principles. Permutations. Combinations. Sections 1.2, 1.3, and 1.4. Lecture 14 slides (PDF)
Friday, February 14  Counting principles. Permutations. Combinations. The Binomial Theorem. Sections 1.2, 1.3, and 1.4. Lecture 15 slides (PDF)
Monday, February 17  Combinations. Generalized combinations. Examples. Sections 1.4 and 1.5. Lecture 16 slides (PDF)
Wednesday, February 19  Combinations. Examples. Recurrence relations. Section 2.4. Lecture 17 slides (PDF)
Friday, February 21  Recurrence relations. Introduction to graphs. Sections 2.4 and 4.1. Lecture 18 slides (PDF)
Monday, February 24  Introduction to graphs. Paths and cycles. Euler cycles. Sections 4.1 and 4.5. Lecture 19 slides (PDF)
Wednesday, February 26  Midterm 2
Friday, February 28  Paths and cycles. Euler cycles. Hamiltonian cycles. Sections 4.1 and 4.5. Lecture 20 slides (PDF)
Wednesday, March 4  Hamiltonian cycles. Dijkstra's shortest-path algorithm. Adjacency matrix. Chapter 4. Lecture 21 slides (PDF)
Friday, March 6  Adjacency matrix. Isomorphisms of graphs. Chapter 4. Lecture 22 slides (PDF)
Monday, March 9  Isomorphisms of graphs. Planar graphs. Euler's Formula. Section 4.3. Lecture 23 slides (PDF)
Wednesday, March 11  Planar graphs. Euler's Formula. Section 4.3. Lecture 24 slides (PDF)