Discrete mathematics is the study of discrete mathematical structures. This includes things like integers and graphs, whose basic elements are discrete or separate from one another. This is in contrast to continuous structures, like curves or the real numbers. We will investigate a variety of topics in and proof techniques common to discrete math. This course provides the mathematical foundations for further theoretical study of computer science, which itself can be considered a branch of discrete mathematics.
Communication
There are a number of different tools we'll be using to communicate about the class.
Course materials
Lecture notes will be made available via this course webpage. The course website also contains basic information about the course (i.e. you can treat it like a syllabus).
Discussion and announcements
We will use Ed Discussion for course discussion and announcements. Restricted course materials will also be posted here.
Coursework and grades
Gradescope will be used for distributing and receiving problem sets and exams.
PrairieLearn will be used for administering work in discussion sessions, such as quizzes and groupwork.
Office hours
Office hours are times when the course staff are available for you. The instructor and teaching assistants will have scheduled office hours in-person and/or online. While most students typically use this as an opportunity to ask about coursework, you're welcome to ask about or discuss things that are related directly or indirectly with the course.
Class meetings
Lectures
Lectures are often the first point at which students will be exposed to new ideas and material. They will cover material that is necessary for success in the course. However, lectures alone may not be sufficient for all students. It is not expected that students will master the material learned in lecture without significant review, inquiry, and practice outside of lecture.
Discussions
Discussion sessions are intended to give students an opportunity to practice and get feedback in a more active setting than lecture. Discussion sessions consist of two components: proctored quizzes and collaborative problem solving.
Course material
The following is a list of topics that will be covered in the course.
Proof and Logic
The language and rules of mathematical reasoning: propositional and predicate logic, proofs and proof rules, induction and recursion
Elementary Number Theory
The structure of the integers: divisibility, modular arithmetic, prime numbers
Combinatorics
Enumerating discrete structures: counting, permutations and combinations, pigeonhole principle, the binomial theorem
Graph Theory
The structure of relations: graphs, paths, connectivity, trees
Probability Theory
Describing the likelihood of discrete events: probability axioms, conditioning, independence, expectation
Text
There is no required textbook for this course and lecture notes will be provided. However, there are a number of alternate resources. Note that definitions and notation may differ slightly across these. When in conflict, the primary source for definitions and notation in this course is the lecture notes.
The recommended textbook is Mathematics for Computer Science, by Lehman, Leighton, and Meyer. The linked draft of this book is freely available.
Another comprehensive resource for this course is Discrete Mathematics and Its Applications, 8th ed. by Kenneth H. Rosen. An electronic copy is available through the UChicago Library.
Evaluation
Your computed grade in this course will be determined by the following coursework components.
Problem sets, roughly weekly, together worth $\frac 1 6$.
Participation in collaborative problem solving, roughly weekly, together worth $\frac 1 {12}$.
Quizzes, roughly weekly, together worth at most $\frac 1 6$.
One midterm examination, held on Thursday October 29, worth at most $\frac 1 4$.
One final examination, to be scheduled by the Registrar, worth at least $\frac 1 3$. Furthermore, the portion of the grade not earned apportioned to quizzes and the midterm examination are assigned to the final examination.
Problem sets
Problem sets will be distributed and submitted via Gradescope and will be due on Fridays at 7:00 pm (19:00) Central.
Collaboration, citation, and academic integrity
The purpose of the problem sets is to give you the opportunity to practice working through the process of solving problems, composing their solutions, and to receive feedback on that process. The work that you hand in to be graded is expected to be the result of your thought, consideration, and effort. Why is this important?
When you submit work, you are claiming that it is a product of your understanding of the material.
Your work will be subject to review and appraisal. It is important that your work represents your understanding so that the feedback you receive will be useful.
While authorship is broadly recognized as a means of assigning credit for work, it is also a mechanism for accountability. You should not submit any work for which you do not want to be held responsible for.
In a theory course where the emphasis is on “proof”, citation of results is necessary for justifying any claims that are made. Whether a result needs to be cited explicitly depends on its role in relation to the course.
You do not need to cite the result explicitly if
the result was discussed in class,
the result appears in the lecture notes,
the result is a solution that was discussed in discussion sessions,
the result is solved on a problem set.
Otherwise, the result must be cited explicitly.
A result appearing in a textbook is not one of the scenarios listed above.
If you are at all unsure about whether a result needs to be cited, it is your responsibility to consult the instructor.
If you choose to work with others, you must acknowledge and list your collaborators.
You may only work with other students in the class. Your collaboration should be to a degree that your writeups are substantially different. It is not acceptable that solutions are largely copies of each other.
You may not use tools to generate your submissions, whether in part or in whole. This includes both ideation and composition.
You should not look up solutions to assigned problems, online or otherwise. This includes question and answer forums, homework websites, and other publicly available materials from other courses in the department or at other institutions. Be aware that if you can find a solution online, the course staff can too.
If you are not sure about whether something is permissible, it is your responsibility to consult the instructor.
It is your responsibility to be familiar with the University’s policy on academic honesty. Instances of academic dishonesty will be referred to the Office of College Community Standards for adjudication. Note that academic penalties are imposed at the sole discretion of the instructor and are determined independent of the OCCS process. If you have any questions, please consult the instructor.
How submissions are graded
Your submissions for problem sets and exams are judged on the following basis:
Validity
Your solution will be judged on its correctness. This includes whether a result, method, or definition was applied correctly, calculations are correct, and proof steps follow the rules of logic.
Presentation
Your solution will be judged on its presentation as it relates to readability and fluency. A solution may be correct, but still to communicate an argument clearly to the reader.
A readable solution should guide the reader through the argument, providing the appropriate explanation, context, and justification.
By fluency, we mean the correct use of the language of mathematics. This includes the proper use of established terminology and notation.
Grading of problems is based on the overall quality of the solution. Solutions need to be valid in order to be evaluated highly, but a completely valid solution that is not presented appropriately will still be given a poor evaluation. Grades are assigned as a qualitative evaluation of the work and not a quantitative accounting of the work.
Generally, the overarching principle that guides the grading is: How much work and guidance is needed for you to revise your submission into something that is Excellent?
Excellent
The solution is correct and readable. The solution is not necessarily perfect—it may have a few trivial flaws in logic or presentation that can be easily corrected.
Good
The solution is generally correct and readable and has some minor flaws in logic or presentation—often there is one last “step” that is missing. Understanding of the problem has been clearly demonstrated. The solution and presentation can be improved quickly with a few suggestions—for instance, a bit more generalization or one more logical step that needs to be taken.
Borderline
The solution could be correct and readable but has a major flaw in logic or presentation. There is evidence that there is some understanding of the problem and the solution is on the right track or has the right idea. The solution and presentation can be improved with some guidance and substantial revisions.
Needs revision
The solution is generally not correct or not readable. It is not clear that the problem was understood and/or the presentation of the solution is heavily flawed. In either case, there is a significant gap in understanding or execution. The solution should be revised with some guidance.
Incomplete
The solution was not submitted or is clearly incomplete—not enough of the solution has been submitted to be able to provide any useful feedback. Submissions that are graded Incomplete are ineligible for resubmission.
The assigned grade is the grader’s judgement of whether the solution meets the standards for the course. In addition to the assigned grade, the grader is expected to provide detailed feedback, addressing specific flaws in the submitted work that can and should be improved in future work.
Resubmission
Part of the learning process is identifying and correcting mistakes. After your submissions have been graded and returned to you, you will have the opportunity to use the feedback you receive to revise and resubmit your work.
Instructions for how to prepare resubmissions will be provided when problem sets become available for resubmission.
Regrade requests
You may submit a regrade request in the event of an error by the grader. That is, if the feedback provided by the grader is a factual error, you may request a review of the grading. Please indicate the source of the error in this case.
We will not consider regrade requests concerning disagreement with a grader’s evaluation of your work. In such cases, you should consider the feedback that was given and apply it towards revision and resubmission of your work.
Accessibility
Students with disabilities who have been approved for the use of academic accommodations by Student Disability Services (SDS) and need reasonable accommodation to participate fully in this course should follow the procedures established by SDS for using accommodations. Timely notifications are required in order to ensure that your accommodations can be implemented. Please discuss your access needs in this class with the instructor after you have completed the SDS procedures for requesting accommodations.
Lectures
Lecture notes may appear before class but are not finalized until after the class. Readings are taken from Lehman, Leighton, and Meyer.