Course Syllabus

Logistics and contact info

Course info:

• CSE 20110, Discrete Mathematics
• Class meetings : Tuesday and Thursday from 2-3:15pm
• Location: 131 Debartolo Hall
• Slack channel (for questions/discussion): https://nd-cse.slack.com/messages/cse-20110-02-fa24

Instructor:

• Erin Chambers
• Office: Room 214A Cushing Hall (although will change soon)
• echambe2@nd.edu
• Office hour times: Mondays at 3pm and Tuesdays at 10am

Course staff:

• Guangyu Meng, office hours 10am on Fridays in Fitzpatrick 150B
• Aydin Wells, office hours 9:30am on Wednesdays in Fitzpatrick 150B
• Brady Green, office hours 3:30-5pm on Thursdays in Hagerty or by appt (DM me on Slack!)
• Henry Jochaniewicz, office hours Wednesday at 3:30-5pm on 1st/2nd floor Hesburgh (see Slack), or by appt (email/Slack)
• Michael Saleev, office hours Monday at 4pm at 209 O'Shaughnessy Hall or by appointment

Course info and overview

Course description:

Computer science draws heavily from a rich historical background in mathematics, particularly in binary and discrete objects, which are easier for computers to work with.  In contrast, most of your math classes so far have probably focused on continuous mathematics, like the real numbers.  In order to understand the limits of what computers can do and push computation to its limits, we need a foundational knowledge of mathematical tools for discrete objects.  This course serves as an introduction to mathematical techniques fundamental to computer engineering and computer science.

Topics: mathematical logic, induction, set theory, relations, functions, recursion, recurrence relations, introduction to asymptotic analysis, algebraic structures, graphs, and machine computation.

Course goals:

• To build the mathematical foundations for topics in computer science such as data structures, algorithms, relational databases, automata theory, formal languages, compiler design, and cryptography
• To build the mathematical foundations for topics in mathematics such as: linear and abstract algebra, combinatorics, probability, logic, set theory, graph theory, and number theory
• To develop the ability to see a problem from a formal mathematical perspective.

Course outcomes:

Upon successful completion of this course, you will be able to:

1. Translate statements in propositional and predicate logic to English and vice versa; and determine logical equivalences using truth tables and standard equivalences
2. Verify if an argument or proof is correct, as well as create proofs (or find counterexamples) for theorems on integers and divisibility using common forms such as direct, indirect, contradiction, and existence
3. Use set operations to prove set identities, as well as identify different types of functions: injective, surjective, and bijective.
4. Find sums of arithmetic and geometric progressions and determine if a set is countable or otherwise.
5. Determine if a function has the same order as another, as in O, Ω, and Θ; and determine the time complexity of simple algorithms
6. Construct proofs using induction and specify mathematical objects using recursive definitions
7. Use the pigeonhole principle, count number of permutations and combinations satisfying given criteria, model counting problems with recurrence relations, and use inclusion-exclusion for counting
8. Determine the probability of simple events, verify if two events are independent, and use Bayes' Theorem to determine the probability of conditional events
9. Determine if a relation is reflexive, symmetric, or transitive, and its closure with respect to some property, as well as identify equivalence classes, partially ordered sets, and various kinds of elements in a lattice
10. Use and apply basic theorems from graph theory, such as the handshaking theorem for graphs, determining if two graphs are isomorphic, and relating the number of leaves in a tree to its height
11. Understand and identify applications of the above in downstream CSE courses, as well as CSE sub-disciplines

Course outline

See here for a detailed (tentative!) outline of course topics: Discrete Math Agenda.pdf

Graded work:

Scoring:

• Homework — 10% of overall grade
• Zybook readings — 10% of overall grade
• Quizzes — 30% of overall grade
• Exam 01 — 15% of overall grade
• Exam 02 — 15% of overall grade
• Final — 20% of overall grade

Homework:

There will be approximately 10 homeworks, so each is about 1% of the grade.  Homework assignments can be submitted in groups of 1, 2, or 3. It is completely ok to work collaboratively and discuss homework amongst your classmates, but each group should submit their own separately written solutions.

The use of generative AI to help {explain, debug, solve, understand} homework problems is allowed, and even encouraged!  Likewise, feel free to use webpages, old solutions, etc, to help you tackle and understand homework questions.  However, I would suggest you proceed with caution on this front, as the quizzes and exams constitute ~80% of your overall course grade and must be completed *without* the use of any generative AI tools. If you cannot understand and/or reproduce homework solutions on your own, your grade will suffer. Per the Honor Code policy below, homework solutions that leverage generative AI content, web pages, others books, etc must be cited as such.

My suggestion: start the homeworks without use of anything other than your notes and book.  Discuss and solve them solo or in your small group, and then pull in other resources to check your answers or when you get stuck on something.  Think of homework as an easy way to practice and then check problems, so that you'll be ready for quiz and exam questions, which will be very similar.  Note that these homeworks can be challenging, so be prepared to spend several hours per homework on understanding and mastering the material.

Zybook:

For this class, in order to engage with the material and give you credit for time spent on the readings, I'll be using a zybook.  This book uses a combination of readings to introduce the material, followed by short exercises to help you engage with the topic.  There's a lot of research showing that such activities really enhance your learning and retention of the concepts, but the exercises are not graded - rather, they're just provided to let you test your knowledge and try to better understand the readings.  My lectures will then pick up and further expand or give information on the concepts from the reading.

To purchase the zybook:

1. Click any zyBooks assignment link in Canvas. (Note: Do not go to the zyBooks website and create a new account)
2. Subscribe (cost should be about $64)

Note that you can download a copy of this book to use as a reference after the class ends, and I highly encourage that you do so!  This class' content can be critical for later classes, including data structures and algorithms, so it's good to have a reference.  

I'm also happy to suggest supplemental readings for the class.  For example, a good free textbook is available here: https://mfleck.cs.illinois.edu/building-blocks/index-sp2020.html

Or you can find an inexpensive copy of Discrete Mathematics by Rosen, which is one of the main references used for this subject material. 

Quizzes:

Over the course of the semester, I will also give 4 in-class quizzes. Quizzes will consist of 1-to-3 short problems that are directly aligned with problems from a given homework assignment. Quizzes will assess homework assignments that have been returned and/or where solutions have already been posted.  Quizzes will be closed book / closed notes.

I want to provide a quick rationale for quizzes, so you understand their intention:

• Empirical evidence suggests that the homework averages across many CSE courses is in the high 90s. This is likely a function of group work and collaboration, the use of various online resources, the use of generative AI, etc. While I could forbid such tools, the temptation to use them is always there, and in fact using them critically is a key skill for your future careers!  So while traditional homework assignments are important in helping you master concepts, they are now less useful as an assessment tool of an individual student’s work.
• However, I also do not want to tie a student’s grade to just 2-3 high stakes in-class exams. So, the quizzes gave been added as a way to better assess individual student knowledge. Each quiz will only be worth 5% of your overall grade. Moreover, questions on quizzes will very closely mimic questions from the prior homework assignments that they cover. This should serve as motivation to truly understand all aspects of a homework assignment, as you will need to reproduce this knowledge in a closed-book, classroom environment.

Exams:

We will have a total of three larger exams.  The first two cover approximately 1/3 of the content each.  The final exam is cumulative, but will emphasize more heavily the final third of the class, and hence is worth slightly more of your final grade.  More details and practice problems will be released the week before the exams, so you will have time to study.  Exams will be closed book and closed notes, except for a handwritten "cheat sheet" which you are welcome to make while studying and bring to the exam.

• Exam 01: October 8th, 2024 from 8:00 am – 9:15 am in 155 DeBartolo Hall
• Exam 02: November 12th, 2024 from 8:00 am – 9:15 am in 155 DeBartolo Hall
• Final: Monday, December 16th from 7:30 pm – 9:30 pm

Regrade Requests
I am happy to regrade any assignments or exam problems which you think were unfair or incorrect. Please email me or the graduate TAs with the specifics of the homework and your objection, including a detailed written explanation of your question or complaint, within two weeks of the time the paper in question is graded and returned to you.

Where can I get help if I need it?

See my office hours + TA office hours above - we're here to help!  If you have a conflict with office hours, something urgent comes up, etc. please email me and we can work to find an alternative time to meet. 

There is a slack workspace for general questions/discussion - please join the CSE department slack, then join this channel: https://nd-cse.slack.com/messages/cse-20110-02-fa24

In addition to course staff, this class is also participating in the ACES study room program, so their tutors can provide extra help and study sessions - see here for details: https://advising.nd.edu/academic-support/atlas/engineering-academic-support/

Other policies to note:

"Life clause" policy:

In general, late assignments will not be accepted or graded.  However, life does happen, and occasionally emergencies come up.  So, once per semester, you are welcome to get a 3 day extension, with no questions asked or no details needed, on any homework assignment.  Please email myself and the TAs before 11;59pm on the due date, if you choose to exercise this.

I will also drop your lowest two zybook readings, so that if you miss one or two, it will not hurt that portion of your grade. 

Accommodations and disability services

It is the policy and practice of The University of Notre Dame to provide reasonable accommodations for students with properly documented disabilities. Students who have questions about Sara Bea Accessibility Services or who have, or think they may have, a disability are invited to contact Sara Bea Accessibility Services for a confidential discussion by emailing at sarabeacenter@nd.edu or by phone at 574-631-7157. Because the University’s Academic Accommodations Processes generally require students to request accommodations well in advance of the dates when they are needed, students who believe they may need an accommodation for this course are encouraged to contact Sara Bea Accessibility Services at their earliest opportunity. Additional information about Sara Bea Accessibility Services and to learn more about the student process for requesting accommodations, please visits Accessibility Support. As an instructor, I encourage you to utilize these services, and feel free to reach out if you'd like to discuss how this might help in the context of this specific class.

Diversity and Inclusion:

The University of Notre Dame is committed to social justice and diversity. I share that commitment and strive to maintain a positive learning environment based on open communication, mutual respect, and non-discrimination. In this class we will not discriminate on the basis of race, sex, age, economic class, disability, veteran status, religion, sexual orientation, color or national origin. Any suggestions as to how to further such a positive and open environment will be appreciated and given serious consideration.

Computer and Cell Phone Policy
You are unlikely to need computer access during lecture, so as a courtesy to both the instructor and the other students, please refrain from using laptops or electronic media during class time.  I will be posting lecture notes, although you are welcome to take your own on paper as well of course.

You are unlikely to need cell phones during the course of lecture. Please ensure that your cell phone is set to vibrate or silent during lecture, and do not send text messages of any kind.  If an emergency call comes in, please excuse yourself and answer it outside the classroom.

Honor Code

As I'm sure you are all aware, Notre Dame students are expected to abide by Academic Code of Honor Pledge. “As a member of the Notre Dame community, I acknowledge that it is my responsibility to learn and abide by principles of intellectual honesty and academic integrity, and therefore I will not participate in or tolerate academic dishonesty.” (http://honorcode.nd.edu)
            
“All students must familiarize themselves with the Honor Code on the University’s website and pledge to observe its provisions in all written and oral work, including oral presentations, quizzes and exams, and drafts and final versions of essays.”
When in doubt about whether something is allowable, don’t assume that you are right – ask me first.

Generative AI Policy for Students

Policy on children in class:

For any student raising children, I understand that minor illnesses and unforeseen disruptions in childcare often put parents in the position of having to chose between missing class to stay home with a child and leaving him or her with someone you or the child does not feel comfortable with. While this is not meant to be a long-term childcare solution, occasionally bringing a child to class in order to cover gaps in care is perfectly acceptable. (You may in fact meet mine at some point this semester!)

All exclusively breastfeeding babies are welcome in class as often as is necessary to support the breastfeeding relationship. Because not all women can pump sufficient milk, and not all babies will take a bottle reliably, I never want students to feel like they have to choose between feeding their baby and continuing their education. You and your nursing baby are welcome in class anytime.

I ask that all students work with me to create a welcoming environment that is respectful of all forms of diversity, including diversity in parenting status. In all cases where babies and children come to class, I ask that you sit close to the door so that if your little one needs special attention and is disrupting learning for other students, you may step outside until their need has been met. Non-parents in the class, please reserve seats near the door for your parenting classmates.