Math 237: Discrete Structures (Fall 2017)

Contents

Syllabus

Download the course syllabus here. The syllabus contains essential information about the course (textbook, prerequisites, course description, material covered, etc.).

Textbook

The official textbook for this course is: Discrete Mathematics (7th edition), authored by Richard Johnsonbaugh, published by Pearson. See this link for the full reference.

Note: Although we will use the 7th edition, getting the 8th edition is also fine. You may also get a digital version of the book.

Class time and location & Office hours

Class time and location:

Monday: 10:00am-11:20am, Smith Hall B-24
Wednesday: 10:00am-11:20am, Smith Hall B-24

Office hours:

Monday: 1:15-2:15pm, Smith Hall 308
Wednesday: 2:30-3:30pm, Smith Hall 308

Course policies

Your overall grade for the course will be a precise combination of:

1. Your global quiz grade $G_1$. There will be about 9 quizzes in the semester. Each quiz grade will be automatically scaled to a grade /100, and at the end all the quiz grades, dropping the lowest two, will be averaged to a global quiz grade.
2. Your global midterm grade $G_2$. There will be two midterm exams, whose grades will be automatically scaled to grades /100, and then averaged to a global midterm grade.
3. Your final exam grade $G_3$. There will be one final exam, whose grade will also be automatically scaled to a grade /100.
Note: Although your homework assignements will not be collected nor graded, they will often provide a basis for the quiz questions.

The formula for your overall grade $G$ for the course will be: $G = c_1 G_1 + c_2 G_2 + c_3 G_3$, where the coefficients $c_1$, $c_2$ and $c_3$ will be around $c_1 = 35\%$, $c_2 = 30\%$ and $c_3 = 35\%$. These coefficients may be subject to marginal change.

Finally, you will be assigned a letter grade for the course depending only on your overall grade $G$, according to the following table:

90% ≤ G ≤ 100% A
80% ≤ G < 90% B+
70% ≤ G < 80% B
60% ≤ G < 70% C+
50% ≤ G < 60% C
40% ≤ G < 50% D
0% ≤ G < 40% F

Note: There will be no exceptions to the grading policy described above.

Attendance & Excused absence policy

Attendance is mandatory: you are required to attend every class.

If you must miss a class for a legitimate reason, you are required to inform me as soon as possible and provide documentation for your absence. If you miss a midterm exam, there will not be automatically a make-up exam if the reason of absence is not serious or the notice is too short. There will be no make-up quizzes, even if you miss a quiz with a valid reason of absence.

Textbook vs Lecture notes

Although we will follow the outline of the textbook very closely, your lecture notes should always be your primary source of information. You can only be expected to know the contents of the lectures, unless you are explicitely asked to review specific segments of the textbook. Nevertheless, the textbook is a great secondary source of information and will be the main source of problems, which are of the utmost importance.

Calculator

You will never need to use a calculator in this course. Calculators will not be allowed during quizzes or exams.

Our goal is to provide all the resources necessary for you to succeed and learn great mathematics in the process, regardless of your background coming in. Nevertheless, you may find this course very challenging. Attending every class is absolutely necessary to meet the challenge but in no way will it be sufficient. The key to your success rests on yourself: it will require hard work, including hours of study, lots of problem solving, and your active involvement in learning both in and outside of the classroom. Of course, you will be assisted in your efforts, and I encourage you to reach me as often as you need.

Contact

My e-mail is brice@loustau.eu. I encourage you to write with any questions.

My office is 308 in Smith Hall. You are welcome during office hours (see above), you may also see me outside of office hours by appointment (first send me an e-mail).

Course schedule

For general important dates in the semester, see the academic calendar here.

Refer to the course schedule below very regularly. It contains among other things the homework assignments and the past quizzes and exams.

This course schedule is only tentative: it is very much subject to change. Always refer to last version online, and make sure that you refresh the page.

Date Topic Homework assignment Special
Wed 09/05 Discussion of course policies
Introduction to the course
Chapter 1: Sets and Logic
1.1 Sets
First day of class
Mon 09/11 1.1 Sets
Review lecture notes
1.1 Review exercises 1-15
Tue 09/12 - - Last day to drop a course without a "W" grade
Wed 09/13 1.2 Propositions
1.3 Conditional Propositions and Logical Equivalence
Review lecture notes
1.1 Exercises: 1-48, 57-93, 95
Mon 09/18 1.4 Arguments and Rules of Inference
1.5 Quantifiers
1.6 Nested Quantifiers
Review lecture notes
1.2 Exercises: All
1.3 Exercises: All except 74, 75
Quiz #1
Quiz #1 Solutions
Wed 09/20 1.5 Quantifiers
Review lecture notes
1.4 Exercises: 1-17
Mon 09/25 1.6 Nested Quantifiers Review lecture notes
1.5 Exercises: 1-67
Quiz #2
Quiz #2 Solutions
Wed 09/27 Chapter 2: Proofs
2.1 Proofs and Counterexamples
2.2 More Proof Methods
Review lecture notes
1.6 Exercises: 1-92
Mon 10/02 2.1 Proofs and Counterexamples
2.2 More Proof Methods
Review lecture notes
Exercise given in class
Quiz #3
Quiz #3 Solutions
Wed 10/04 2.2 More Proof Methods
Review lecture notes
2.1 Exercises 6-15, 19-27, 44-54
Mon 10/09 2.4 Mathematical Induction Review lecture notes
2.2 Exercises 1, 6-8, 12, 15, 16, 18, 21, 22-27, 30, 32, 33, 37-39, 43, 48
Quiz #4
Quiz #4 Solutions
Wed 10/11 2.4 Mathematical Induction
Chapter 3: Functions
3.1 Relations and Functions
Review lecture notes
2.4 Exercises 1-9, 14, 21-26, 28
Mon 10/16 - List of topics EXAM #1
EXAM #1 Solutions
Wed 10/18 3.1 Relations and Functions Review lecture notes
Mon 10/23 3.1 Relations and Functions
3.2 Sequences and Strings
Review lecture notes
Exercise given in class
3.1 Exercises 1-5 (except the part about the inverse function), 10-31, 51-52, 82-88, 98-103
No quiz
Wed 10/25 3.2 Sequences and Strings
3.3 Relations
Review lecture notes
Exercises given in class
3.1 Exercises 1-5, 32-47, 62-70, 90-97
Mon 10/30 3.3 Relations
3.4 Equivalence Relations
Review lecture notes
3.2 Exercises 1-82, 116-122, 124, 129-131
Quiz #5
Quiz #5 Solutions
Wed 11/01 3.4 Equivalence Relations
3.5 Matrices of Relations
3.6 Relational Databases
Review lecture notes
3.3 Exercises 1-55, (56-59)
Mon 11/06 Chapter 4: Algorithms
4.1 Introduction
4.2 Examples
4.3 Analysis of Algorithms
Review lecture notes
Exercises given in class
3.4 Exercises 1-20, 24, 27, 28
Quiz #6
Quiz #6 Solutions
Last day to drop a course with a "W" grade
Wed 11/08 4.2 Examples
4.3 Analysis of Algorithms
Review lecture notes
4.1 Exercises 5, 9-12, 14
4.2 Exercises 4-7, 14, 19
Mon 11/13 - Review lecture notes
4.3 Exercises 1-28, 33-34, 60-61
List of topics
EXAM #2
EXAM #2 Solutions
Wed 11/15 4.4 Recursive Algorithms
Chapter 7: Recurrence relations
7.1 Introduction
Review lecture notes
Mon 11/20 7.2 Solving Recurrence Relations
7.3 Analysis of Algorithms
Review lecture notes
4.4 Exercises 1, 5, 6, 9, 12, 13
7.1 Exercises 1-17, 56-57, (70)
No quiz
Wed 11/22 - - Class cancelled
follows a Friday schedule
- - Thanksgiving recess
11/23 - 11/26
Mon 11/27 7.3 Analysis of Algorithms: complexity of selection sort
Chapter 6: Counting methods
6.1 Basics
Review lecture notes
Problem given in class
7.2 Exercises 11-14, 27, (29-32)
Quiz #7
Quiz #7 Solutions
Wed 11/29 6.1 Basics
6.2 Permutations and Combinations
Review lecture notes
Homework problems given in class
7.3 Exercises 28-39
6.1 Exercises 4-12, 15-16, 31-37, 44-60
Mon 12/04 6.2 Permutations and Combinations
(6.7 Binomial coefficients and Combinatorial identities)
6.8 The pigeonhole principle
Review lecture notes
6.1 Exercises 4-12, 15-16, 20-27, 31-37, 44-60, 86, 87, 90, 91
6.2 Exercises 1-13, 25-29, 33-38, 40-41, 43-47, 60-64
Quiz #8
Quiz #8 Solutions
Wed 12/06 Chapter 5: Number theory
5.1 Divisors
Review lecture notes
Homework problems given in class
6.7 Exercises 1, 2, 22
6.8 Exercises 1-4, (6), 7-8
Mon 12/11 5.2 Representations of Integers and Integer Algorithms
(5.4 The RSA Public-Key Cryptosystem)
Review lecture notes
Homework problem given in class
5.1 Exercises 1-33
Quiz #9
Quiz #9 Solutions
Wed 12/13 Review session Review lecture notes
5.2 Exercises 1-41
Mon 12/18 FINAL EXAM List of topics FINAL EXAM
Time: 11:45 - 2:45pm
Location: Smith B-24