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


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: Cummings 455 (behind the 4th floor kitchen)
Email: kedwardsREMOVEME@cs.tufts.edu
Office Hours: Tue 3-4:30pm, Fri 12-1pm or by appt. I will usually be in my Cummings 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
Office Hours: (For M1 students) See Canvas

Lectures:

Lectures are held in-person, except at the beginning of the semester (details in Piazza). Zoom links for the beginning of the semester were emailed to enrolled/waitlisted students.
Section 02 is E block, MWF 10:30-11:20 in Cummings 170
Section 03 is G block, MWF 1:30-2:20 in Cummings 170
Section M1 (for online postbac students) meets Wednesdays 6-7:30pm online
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).

Lecture participation (sections 02, 03):

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 (3rd ed) Topic(s)
Sep 7 1 1–2 Intros/Syllabus; Thinking Logically
Sep 9 1 3–4 The Integer Sandbox; Theorems
Sep 12 2 5 Proofs
Sep 14 2 6, 7 Counterexamples; Boolean Algebra
Sep 16 2 7, Syll Syllogisms
Sep 19 3 8, 9 Lists; Factorial
Sep 21 3 10 Intro to Sets
Sep 23 3 11 Quantifiers
Sep 26 4 12 Set Operations & Proofs
Sep 28 - 1–12 ---review---
Sep 30 - 1–12 Exam 1

Date Hwk # Sections (3rd ed) Topic(s)
Oct 3 5 13 Combinatorial Proofs
Oct 5 5 14 Relations
Oct 7 5 15 Equivalence Relations
Oct 10 - - -
Oct 12 6 16 Partitions
Oct 14 6 17 begin Binomial Coefficients
Oct 17 7 17 cont. Binomial Coefficients cont.
Oct 19 7 20 Contradiction and Contrapositive
Oct 21 7 22 Induction
Oct 24 8 22.5 Strong Induction
Oct 26 8 24 Functions
Oct 28 8 25 Pigeonhole Principle
Oct 31 - 13–17, 20, 22, 24–25 ---review---
Nov 2 9 25, 29 ---Optional bonus material: Big-O, Cantor's Thm---
Nov 4 - 13–17, 20, 22, 24–25 Exam 2

Date Hwk # Sections (3rd ed) Topic(s)
Nov 7 10 35, 36 Mod operation, Euclid's Algorithm
Nov 8 10 36 cont. Euclid's Algorithm cont. THIS IS A REAL TUE / TUFTS FRI
Nov 9 10 37 Modular arithmetic
Nov 11 - - -
Nov 14 11 43 Fermat's Little Theorem
Nov 16 11 43 cont. Euler's Theorem
Nov 18 11 44, 46 RSA Cryptography
Nov 21 12 47 Graphs: Intro
Nov 23 - - -
Nov 25 - - -
Nov 28 13 48 Graphs: Subgraphs
Nov 30 13 49 Graphs: Connectedness
Dec 2 13 50 Graphs: Trees
Dec 5 - 35-37, 43, 44, 46-50 ---review---
Dec 7 14 51, 52, 53 ---Optional bonus material: Eulerian Graphs, Coloring, Planar Graphs---
Dec 9 - 35-37, 43, 44, 46-50 Exam 3 (24 hr take-home, no class)
Dec 12 - ---all--- ---Review for final---

Dec 16 - ---all--- Final exam 12-2pm
Dec 20 - ---all--- Final exam 3:30-5:30pm

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 (TBD, either Sundays or Mondays) at 11:59pm.

Late homework / Token system:

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): If you are exploring LaTeX for the first time (this is a GREAT time to start), TAs with some LaTeX familiarity are starred in the OH list on Piazza. In order to run LaTeX you will need to do ONE of the following.

  1. use an online LaTeX editor such as Overleaf <----Easiest option but requires internet, of course
  2. use the lab machines or remote login to the department servers (you need a CS account; anyone taking a CS class should have received an email to set it up if you don't have one already).
  3. install a free LaTeX distribution.
Here's a template/example to get you started (if links break please alert Karen):

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 60 minutes long during class time, either 10:30-11:30 or 1:30-2:30. 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. 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/classes:

If you have a serious reason for not submitting homework or not taking an exam that needs consideration beyond the systems given above, you should notify your Dean and/or Health Services and cc: me. 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 (that's why I drop one exam instead.) Please check the exam schedule before making travel arrangements.

Tips for being a successful student in Discrete Math: