MPCS 50103—Mathematics for Computer Science: Discrete Mathematics (Winter 2022)

General information

Instructor

Timothy Ng (timng@uchicago.edu)

Teaching assistants

TBA

Links

• Course webpage
• Lectures
• Ed Discussion
• Gradescope

Overview

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 discrete math and the 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 and links to lecture videos will be made available via this course webpage. The course website also contains basic information about the course (i.e. you can treat this like a syllabus).

Discussion and announcements

We will use Ed Discussion for course discussion and announcements. Restricted course materials and Zoom meeting information will also be posted here.

Problem sets and grades

We will use Gradescope for distributing and receiving coursework, such as problem sets and exams. Your grades will also be available here.

Practice quizzes

We will use PrairieLearn for practice quizzes.

Class meetings

Before January 24

Lectures will be asynchronous and provided weekly as a set of videos on Mondays. In place of live lectures, there will be office hours held on Wednesdays at 5:30 pm via Zoom.

After January 24

Lectures will be held in-person on Wednesdays at 5:30-8:30 pm in Ryerson 276.

Topics

Proof and Logic

Propositional and predicate logic, proofs, induction

Elementary Number Theory

Divisibility, modular arithmetic, prime numbers

Combinatorics

Counting, permutations, combinations, pigeonhole principle, binomial theorem, recurrences, generating functions

Discrete Probability

Probability, independence, correlation, expectation, variance

Graph Theory

Graphs, paths, connectivity, trees

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 may differ across these. When in doubt, your primary source for definitions should be the lecture notes.

• The most comprehensive resource for this course is Discrete Mathematics and Its Applications, 7th ed. by Kenneth H. Rosen. The course notes are heavily based on this text. Ungraded exercises will be assigned from this text.
  • The 8th edition of this text is also available now. An electronic copy is available through the UChicago Library, though there are access limitations.
• Another comphrehensive resource is Mathematics for Computer Science, by Lehman, Leighton, and Meyer. The linked draft of this book is freely available.

Evaluation

Your computed grade in this course will be determined by the following coursework components.

• Examinations, worth 50% in total.
  • A midterm exam, worth up to 20%. Let $M$ be the grade earned on the midterm exam.
  • A final exam, worth at least 30%. Let $F$ be the grade earned on the final exam.
• Weekly problem sets worth 40% in total. Let $P$ be the grades earned on problem sets.
• Weekly practice quizzes, worth 10% in total. Let $Q$ be the the grades earned on quizzes.
• Biweekly personal reflections each worth 1%. Let $R$ be the number of completed reflections.

Then your computed grade will be obtained via the following formula: \[(P \times 40\%) + (Q \times 10\%) + (R \times 1\%) + (M \times 20\%) + (F \times (50\% - (M \times 20\%))).\]

Problem sets

Problem sets will be released on Wednesdays and will be due on the following Wednesday at 5:00 pm (17:00) Central.

Problem sets will be distributed and submitted via Gradescope. Please ensure that submissions are legible. See this guide for submitting on Gradescope.

Students are expected to write up solutions to problem sets individually, but may work together. Be sure to list all of your collaborators and acknowledge any sources beyond course materials that you may have used.

How solutions are graded

The purpose of this class is to help you develop both problem solving skills and mathematical writing skills. Your solutions on problem sets and exams are judged on the following basis:

• Validity. Your solution will be judged on its correctness. This includes whether a method 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 is unable to communicate this fact to the reader. A readable solution should guide the reader through the argument, providing the appropriate explanation 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 for problem sets is based on the overall quality of the solution. Clearly, solutions need to be valid in order to be evaluated highly, but a completely valid solution that is not readable will still be evaluated poorly. Furthermore, grades are assigned as a qualitative evaluation of the work and not a quantitative accounting of the work. This appears as a 4-point scale on Gradescope.

• 4 (Excellent). The solution is correct and readable. The solution may have a few trivial flaws in logic or presentation that can be easily corrected.
• 3 (Good). The solution is generally correct and readable and has a some minor flaws in logic or presentation. Understanding of the problem has been demonstrated. The solution and presentation can be improved quickly with a few suggestions.
• 2 (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. The solution and presentation can be improved with some substantial revisions.
• 1 (Needs revision). It is not clear that the problem was understood and/or the presentation of the solution is heavily flawed. The solution should be revised with some guidance.
• 0 (Incomplete). The solution was not submitted or is clearly incomplete.

The assigned grade is the grader’s judgement of whether the solution meets the standards of the class. 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.

Please follow the instructions for resubmission carefully. An assignment on Gradescope will be available for resubmissions of the problem set. There are a lot of different assignments on Gradescope, so please read carefully and make sure you’re submitting to the correct one. To prepare your resubmission, you should include:

1. the first page of the graded copy of the submission, which contains a summary of the grading (described below) and indicating clearly which solutions are being resubmitted, and
2. your revised solution for problems you wish to resubmit,
3. a response to the grader for each problem you wish to resubmit, indicating explicitly how you have implemented the grader’s feedback.

To get a copy of your graded problem set, use the Download Graded Copy button. The first page of this document is an outline of the grading. Include this page in your resubmission and use it to refer to the graders’ feedback in your response. If you have questions about a grader’s comments, you should contact the course staff by making a post visible only to course staff on Ed.

• Only complete solutions may be resubmitted. The point of this process is to allow you to incorporate the feedback you receive from grading. Incomplete solutions will have no actionable feedback, defeating the purpose of resubmission.
• You do not need to resubmit the entire problem set if you only want to resubmit a solution for one problem.
• You do not need to resubmit any part of the problem set if you are satisfied with your grade.
• If you resubmit part of the problem set, for all problems you are not resubmitting, please select the grading summary page for that problem.
• Your resubmissions will be graded by the same grader.

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.

Practice quizzes

Practice quizzes will be conducted online on PrairieLearn. Quizzes are meant to test your general knowledge of concepts introduced via lecture. These are randomized and automatically graded immediately. You will have the opportunity to retry quizzes as often as you like. You should receive an email invitation to the course instance by the start of the quarter. If you have not received an invitation to join after January 12, please contact the instructor as soon as possible.

Reflections

Reflections are meant to give you an opportunity to reflect on your relationship with the course and the things you're learning. I (the instructor) will be reading and responding to your submissions here, so this will also allow us to establish a dialogue about your learning in this course.

Completion of reflections is optional but each is worth an additional 1% of the course grade. These will be loosely graded on completion/thoughtfulness and not "correctness"; you should aim for about a paragraph or two of thoughtfulness.

Lectures

January 5

Introduction and course information

• Video

January 12

Lecture 1: Logic, Proof, and Induction

1. Natural numbers
   • Notes
   • Video
2. Logic
   • Notes
   • Video
3. Proof
   • Notes
   • Video
4. Indirect Proof
   • Notes
   • Video
5. Induction
   • Notes
   • Video

January 19

Lecture 2: Set theory basics and introduction to elementary number theory

1. Sets
   • Notes
   • Video
2. Set operations
   • Notes
   • Video
3. Functions
   • Notes
   • Video
4. Divisibility
   • Notes
   • Video
5. Division
   • Notes
   • Video
6. Divisors
   • Notes
   • Video

January 26

Lecture 3: Prime numbers and modular arithmetic

1. Strong induction
2. Prime numbers
3. Modular arithmetic

February 2

Lecture 4: Applications of modular arithmetic and introduction to combinatorics

1. Chinese Remainder Theorem
2. Fermat's Little Theorem
3. Combinatorics
4. Permutations
5. Combinations

February 9

Lecture 5: More combinatorics

1. Combinations and permutations with repetition
2. The Binomial Theorem
3. The Pigeonhole Principle

February 16

Lecture 6: Probability theory

1. Discrete Probability
2. Conditional Probability
3. Independence
4. Random variables

February 23

Lecture 7: Expectation, Graph theory

1. Expectation
2. Concentration and tail inequalities
3. Graph theory

March 2

Lecture 8: Connectivity in graphs

1. Paths and connectivity
2. Trees

March 9

Lecture 9: Special structures in graphs

1. Euler and Hamiltonian paths
2. Matchings

Academic integrity

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 the Provost for adjudication. Following the guidelines above on collaboration and citation should be sufficient, but if you have any questions, please ask me.

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 meet with me to discuss your access needs in this class after you have completed the SDS procedures for requesting accommodations.