This course covers key mathematical concepts used in computer science, including: logic, proofs, counting, discrete probability, graph theory, and boolean algebra. These topics all fall within the general category of discrete mathematics as oppose to continuous mathematics (see here for more on this distinction.) Throughout the course, I will use algorithmic analysis to provide motivating examples, so you will also learn algorithm basics.
The required textbook for this course is Discrete Mathematics and its Applications, 7th Edition by Kenneth H. Rosen. Most of the topics and examples covered in this course will be adapted from this text.
Grades in the course will be based on weekly problem sets and two exams (a midterm and a final). The problem set problems will be graded on the following scale: check plus (correct answer with at most minor issues), check (shows understanding but has at least one major issue), and zero (does not demonstrate a reasonable understanding of the problem). Each check plus earns you 2 points, each check 1 point, and each zero, of course, 0 points. At the end of the semester, I add up all the points you earned, and this is your raw problem set score. I will then translate that raw score into a letter grade.
Each problem set will be returned to you along with sample solutions, grading notes, and a guide to mapping your point score to a letter grade scale. Though this mapping will vary from problem set to problem set, depending on length and difficulty, in most cases, to earn an A on a problem set you should be aiming to get a check plus on most problems.
In determining your final grade, I will average your problem set grade with your midterm and final grades according to the below weights.
Problem Sets | 50% |
Midterm | 25% |
Final | 25% |
This course has two teaching assistants who will hold regular office hours in Room 330 in Saint Mary's Hall. Their contact information and office hour times are below.
In addition to the teaching assistant office hours listed above, I will hold regular office hours from 2:00 to 3:30 pm on Tuesdays, in my office at 334 Saint Mary's Hall.
If you have a question for me about the material or course logistics, my preference is that you ask me immediately before or after class, or during my office hours. If you instead e-mail me, I cannot guarantee a timely response (I am a bad e-mail correspondant). Therefore, if you have a last minute question (e.g., about a problem set), you will likely be better served e-mailing one of the teaching assistants.
The following rules describe my expectations and grading policies for problem sets:
There will be two exams in the course: a midterm and a final. The final exam is not cumulative; that is, it covers material from the second half of the course starting with discrete probability and ending with boolean algebra.
I take academic integrity seriously. To repeat the problem set instructions from above: You must work alone on problem sets. You may only discuss problems with me. The only materials you can reference when working on these problems are your course notes and the assigned textbook. In particular, you may not reference online sources or talk to other students.
You may not bring any outside material into exams.
You may not reference any problem sets, exams, or solutions from prior teachings of this course.
When in doubt, ask me what is allowed.
Below is the current schedule for the course. I will add more detail regarding the topics covered (and corresponding textbook sections) as the semester continues. I will adjust this schedule if needed if our pace proves too fast or slow.
Week 1 (9/1)
Introduction to the course and its topics; begin work on logic and proofs.
Problem Set 1 Assigned (Due on 9/13): [Download]
Textbook Chapter(s): 1
Week 2 (9/6 and 9/8)
Logic and proofs continued.
Textbook Chapter(s): 1
Week 3 (9/13 and 9/15)
Sets, functions, and sums.
Problem Set 2 Assigned (Due on 9/20): [Download]
Textbook Chapter(s): 2
Week 4 (9/20 and 9/22)
Algorithms: their specification, correctness, and complexity.
Problem Set 3 Assigned (Due on 9/29; notice this is a Thursday due date): [Download]
Textbook Chapter(s): 3
Week 5 (9/27 and 9/29)
No Class on Tuesday, 9/27
Begin induction on Thursday, 9/29.
Problem Set 4 Assigned (Due on 10/11): [Download]
Textbook Chapter(s): 5
Week 6 (10/4 and 10/6)
Finish induction; introduction to recursion.
Textbook Chapter(s): 5
Week 7 (10/11 and 10/13)
Basic Counting
Problem Set 5 Assigned (Due on 10/20; notice this is a Thursday due date): [Download]
Textbook Chapter(s): 6
Week 8 (10/18 to 10/20)
The first lecture this week will continue our discussion of counting. The second lecture will be an optional review session for the midterm. Notice, the problem set is due on Thursday this week and will cover material from Tuesday's lecture.
Textbook Chapter(s): 6
Week 9 (10/25 and 10/27)
No Class on Tuesday, 10/25
Your midterm is on Thursday, 10/27.
Week 10 (11/1 and 11/3)
Discrete probability.
Problem Set 6 Assigned (Due on 11/15): [Download]
Textbook Chapter(s): 7
Week 11 (11/8 and 11/10)
Discrete probability continued; recurrence relation basics.
(Reminder: Monday, 11/7 is the last day to withdrawl.)
Textbook Chapter(s): 7 and 8
Week 12 (11/15 and 11/17)
Graph theory.
Problem Set 7 Assigned (Due on 11/22): [Download]
Textbook Chapter(s): 10 and 11
Week 13 (11/22 and 11/24)
Graph theory.
(Note: we only have one class this week due to the Thanksgiving holiday).Problem Set 8 Assigned (Due on 12/6): [Download]
Textbook Chapter(s): 10 and 11
Week 14 (11/29 and 12/1)
Graph theory concluded and introduction to boolean algebra.
Textbook Chapter(s): 10, 11, and 12
Week 15 (12/6)
Overflow material, wrap-up and exam review.
Final Exam: Wednesday, 12/14 from 4:00 to 6:00 pm, in STM 110 (our normal classroom).