CS/MATH 61: Sections 02, 03, M1
Discrete Mathematics
Fall 2021


Welcome to Discrete Math. This class is for you! We want all students to succeed in this class and provide many resources for doing so. Please don't hesitate to reach out if you have any concerns or questions.

Why take Discrete Math? Here are the abilities you will develop in this class:

  1. You will learn to write proofs at an introductory level. You will be able to frame your argument in a clear, logical and convincing manner, and you will be familiar with certain standard methods used in many courses such as proof by induction or proof by contradiction.
  2. You will experiment with examples and develop conjectures. In the real world, the purpose of research is to investigate ideas and uncover truth. Instead of solving a known problem, one must be comfortable exploring an idea that may be true or false.
  3. You will develop your language skills, writing technical ideas in mathematical language with correct syntax as well as translating between math and English.
  4. You will become familiar with a variety of basic mathematical terminology and concepts that can arise in many other classes and in technical fields. Topics include: Propositional Logic, Sets, Counting, Relations (including Equivalence Relations and Functions), Methods of Proof and Graph Theory.
  5. You will explore one application in depth, namely to learn all of the mathematics underlying RSA Cryptography, including Modular Arithmetic. RSA is one of the oldest and most widely used public-key cryptosystems, used for example to send credit card information over the Internet.
We look forward to working with you!


Instructors:

Karen Edwards (she/her/hers)
Sections: 02, 03
Office: Halligan 221
Email: kedwardsREMOVEME@cs.tufts.edu
Office Hours: MW 2:30-3:30pm, Fri 12-1pm or by appt. I will be in my Halligan office and also available virtually at https://tufts.zoom.us/j/92819263712. The password is the Tufts mascot (no caps).

Emmely Rogers (she/her/hers)
Sections: M1
Email: emmely.rogersREMOVEME@tufts.edu

Lectures:

Lectures are held online. Zoom links were emailed to enrolled/waitlisted students.
Section 02 is E block (MWF 10:30-11:20)
Section 03 is G block (MWF 1:30-2:20)
Section M1 (for online postbac students) meets Thursdays 6-7:30pm
The lectures for 02 and 03 run in parallel; you are welcome to attend either one!

Recitations/Worksheets:

Discussion Board/Announcements:

Class discussion and announcements for this course will take place in Piazza, with important announcements forwarded to your email from Piazza. Please register as soon as possible. The access code was emailed to enrolled/waitlisted students.

Course Materials:

TAs:

Office hours:

All office hours (including cancellations) will be posted in Piazza. Please stop by often, whether you have specific questions, a concern, or just want to hang out and work on your homework.

Content:

This class covers foundations of discrete mathematics and introduction to proofs. Topics include Propositional Logic, Sets, Counting, Relations (inlcuding Equivalence Relations and Functions), Methods of Proof, Modular Arithmetic, RSA Cryptography and Graph Theory.

Classroom environment:

This class is a safe space to learn and be confused about math. I want everyone to explore your confusions, because wrestling with your confusions is the key to deepening your knowledge. All questions are good questions. If you're not confused by anything in this class then you're in the wrong class.

Prerequisites:

Comp 11 or Math 32 is recommended, but the primary outcome we are looking for is math maturity, so that you are prepared to understand and write proofs, consider new number systems such as modular arithmetic, and be comfortable reading symbols such as set notation. You will need a few algebra skills here and there.

Textbook:

We are using Mathematics: A Discrete Introduction (2nd edition OR 3rd edition) by Edward Scheinerman. It is available in many places, in multiple formats (new, used, rental, digital).

Lectures:

Lectures are a place for exploring simple yet deep math ideas together. It's ok to be confused! All questions are good questions!

Schedule:

Date Hwk # Sections Topic(s)
Sep 8 1 1–2 Intros/Syllabus; Thinking Logically
Sep 10 1 3–4 The Integer Sandbox; Theorems
Sep 13 2 5 Proofs
Sep 15 2 6, 7 Counterexamples; Boolean Algebra
Sep 17 2 7, Syll Syllogisms
Sep 20 3 8, 9 Lists; Factorial
Sep 22 3 10 Intro to Sets
Sep 24 3 11 Quantifiers
Sep 27 4 12 Set Operations & Proofs
Sep 29 - 1–12 ---review---
Oct 1 - 1–12 Exam 1

Date Hwk # Sections Topic(s)
Oct 4 5 13 Combinatorial Proofs
Oct 6 5 14 Relations
Oct 8 5 15 Equivalence Relations
Oct 11 - - -
Oct 13 6 16 Partitions
Oct 15 6 17 Binomial Coefficients
Oct 18 7 17 cont. Binomial Coefficients cont.
Oct 20 7 20 Contradiction and Contrapositive
Oct 22 7 22A Induction
Oct 25 8 22B Strong Induction
Oct 27 8 24 Functions
Oct 29 8 25 Pigeonhole Principle
Nov 1 - 13–17, 20, 22, 24–25 ---review---
Nov 3 9 25, 29 ---Optional bonus material: Big-O, Cantor's Thm---
Nov 5 - 13–17, 20, 22, 24–25 Exam 2

Date Hwk # Sections Topic(s)
Nov 8 10 35, 36 Mod operation, Euclid's Algorithm
Nov 10 10 36 cont. Euclid's Algorithm cont.
Nov 12 10 37 Modular arithmetic
Nov 15 11 43 Fermat's Little Theorem
Nov 17 11 43 cont. Euler's Theorem
Nov 19 11 44, 46 RSA Cryptography
Nov 22 12 47 Graphs: Intro
Nov 24 - - -
Nov 26 - - -
Nov 29 13 48 Graphs: Subgraphs
Dec 1 13 49 Graphs: Connectedness
Dec 3 13 50 Graphs: Trees
Dec 6 - 35-37, 43, 44, 46-50 ---review---
Dec 8 14 51, 52, 53 ---Optional bonus material: Eulerian Graphs, Coloring, Planar Graphs---
Dec 10 - 35-37, 43, 44, 46-50 Exam 3 (24 hr take-home, no class)
Dec 13 - ---all--- ---Review for final---

Grading:

Your grade is based on 3 exams plus a final, plus your hw and participation as follows:

Your numerical grade will be converted to a letter grade as follows:

Homework:

HW assignments are posted on Piazza and will be submitted via Gradescope. Instructions for submitting homework will be posted on Piazza. Homeworks are usually due Sundays at 11:59pm.

Late homework:

HW collaboration policy: You are welcome to talk to the Instructor, TAs or other students about HW problems, but if so please follow the "sandwich" rule:

You should not be looking up hw solutions on the Internet. If you have substantially collaborated with other students on a problem, please acknowledge this at the top of that problem, i.e. "I worked with Alex and Robin". The write up still needs to be your own. In general, you should assume that problems require justification---no credit for correct answers with no justification.

Typesetting homeworks using LaTeX (optional but recommended): In order to run LaTeX you will need to install a free LaTeX distribution. Alternatively, you can use the lab machines, remote login (ssh & sftp) (non EECS majors can get an account @ EECS systems office), or online LaTeX editors such as Overleaf. If you would like to explore LaTeX for the first time, TAs with some LaTeX familiarity are starred in the OH list on Piazza.

Proofwriting and Rewrites:

A core component of Discrete Math is developing your ability to reason logically and communicate your argument clearly and convincingly. Namely, proofwriting! Writing proofs in math is like writing essays in English; you need lots of practice and feedback. Thus, when you submit proofs (worth 5 pts) on your homework, you will get a grade of 5, 4, or Rewrite. If you get a Rewrite, you then improve and resubmit the proof and can still earn up to full credit.

Participation:

Exams:

Exams 1 and 2 for sections 02 and 03 will be IN-PERSON during class time, either 10:30-11:30 or 1:30-2:30 (location TBD, will be announced on Piazza). Sections 02 and 03 are welcome to take the exam at either time. Exam 3 will be take-home for all sections.

Final Exam:

We will use the standard Tufts final exam blocks. The final exam for sections 02, 03 will be IN-PERSON, unless Tufts policy changes. Students in sections 02, 03 are welcome to attend either of those final exam blocks.

Academic Integrity:

Students must adhere to the Tufts Academic Integrity policy. See above for homework collaboration policy. Exam policies will be detailed on each exam. All students' written work must be their own in all cases. Violations will be reported to the Dean of Student Affairs, and are likely at a minimum to result in a grade of 0 for the assignment or exam.

Missing homeworks/exams:

If you have a serious reason for not submitting homework or not taking an exam, you should notify your Dean and/or Health Services, and of course you may copy me as well. Decisions about missed homeworks/exams will be made in consultation with your Dean. Otherwise, exams must be taken at the scheduled times. There are no makeups (instead I drop the lowest exam, as explained above in Grading.) Please check the exam schedule before making travel arrangements.

Tips for being a successful student in Discrete Math: