CS/MATH 61: Sections 01, 02
Discrete Mathematics
Spring 2024


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. (Office hours and after class is best).

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!


Quick Links:

Instructor
Lecture, Participation, Recitations, Discussion
TAs, Office Hours
Content, Materials, Prereqs
Class Environment
Schedule
Grading
Homework
Proofwriting, Rewrites
Participation
Exams
Final Exam
Academic Integrity
Missing Homework/Exams/Participation
Tips for success!!


Instructor:

Karen Edwards (she/her/hers)
Office: Cummings 455 (behind the 4th floor kitchen)
Email:
kedwardsREMOVEME@cs.tufts.edu
Office Hours: Mon 3-4pm, Fri 12:30-1:30pm, after class, 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).

Lecture Times:

The lectures for 01 and 02 run in parallel; you are welcome to attend either one!

Lecture Participation:

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

Recitations/Worksheets:

There are optional recitations with TAs on Friday afternoons to go through a worksheet based on the week's topics. The worksheets and solutions will be posted afterwards on Piazza. These are not scheduled via SIS; instead you can indicate your preferences in the student questionnaire (sent via email to enrolled/waitlisted students) and the schedule will be posted in Piazza.

Discussion Board/Announcements:

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

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.

Course Materials:

All course materials (handouts/assignments/solutions) for this class will be posted under "Resources" in Piazza. This course does not use Canvas.

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).

Prerequisites:

Comp 11 or Math 32 is useful, 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.

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.

Schedule:

Date Hwk # Sections (3rd ed) Topic(s)
Jan 17 1 1–2 Intros/Syllabus; Thinking Logically
Jan 19 1 3–4 The Integer Sandbox; Theorems
Jan 22 2 5 Proofs
Jan 24 2 6, 7 Counterexamples; Boolean Algebra
Jan 26 2 7, Syll Syllogisms
Jan 29 3 8 Lists; Factorial
Jan 31 3 9, 10 Intro to Sets
Feb 2 3 11 Quantifiers
Feb 5 4 12 Set Operations & Proofs
Feb 7 - 1–12 ---review/catchup---
Feb 9 - 1–12 Exam 1

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

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

May 3 - ---all--- Final exam 12-2pm
May 9 - ---all--- Final exam 12-2pm

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 Mondays at 11:59pm.

Late homework / Token system:

HW collaboration policy: You are welcome to talk to the Instructors, 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 when you list your resources, 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:

This will be based on your lecture responses (see Lecture Participation above).

Exams:

Exams 1 and 2 will be 60 minutes long during class time, either 9:30-10:30 or 10:30-11:30. You are welcome to take the exam at either time; if you switch sections you must RSVP on a piazza post. Exam 3 will be take-home.

Final Exam:

The final exam will be in-person, as indicated below You are welcome to attend either of those final exam blockse; if you switch sections you must RSVP on a piazza post.

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: your instructor. 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 one exam is dropped instead.) Please check the exam schedule before making travel arrangements.

Tips for being a successful student in Discrete Math: