DMT1 – Discrete Mathematics
This page does not represent the most current semester of this course; it is present merely as an archive.

1 Teaching Continuity

As of March 19, this course will be taught online. Here’s how we plan to make that work. This may change if we determine better approaches to some elements.

Lectures

We’ll try doing these via zoom. The time is unchanged from our usual lecture time (MoWeFr 10:00 EDT). The link to join is https://virginia.zoom.us/j/273905137. You will be muted upon joining; please un-mute only to ask a question.

I plan to attempt doing turn to your neighbor parts of class via a feature called zoom breakout rooms. I have never done these at that scale, so we might have to adjust as we go.

Lectures will still be recorded and posted to the website as usual.

I am uncertain of the efficacy of this model. We may swap to having prerecorded lecture segments instead and use lecture time as additional professor office hours.

Labs
I’ll still post practice exercises. But we will not use lecture time for one-on-one help; instead, I’ll use most Fridays to do Q&A and work examples.
In-class quizzes
  • Will become open-note (but still do-on-your-own).
  • Will still be limited to a 20-minute time window.
  • We’ll post the problem prompts. You’ll write the answers on paper, take a picture or scan of the paper, and upload it.
Online quizzes
Unchanged
Professor Office Hours
Will occur via zoom. The link to join is https://virginia.zoom.us/j/847054967. During scheduled office hours times, anyone who comes in will be in the same zoom room, If you have personal matters to discuss, email me about a different time to meet.
TA Office Hours

We’ll adopt an online queuing system. The process will work as follows:

You are welcome to come in groups by inviting other students to your meeting room.

If a more text-oriented help will suffice, we recommend using Piazza.

Accommodations, grading, etc

We expect this transition to be bumpy in various ways. Please feel free to use email, Piazza, or Collab’s Anonymous Feedback tool to let me know of any issues. We’ll do our best to work through them.

I have a lot of experience teaching in-person, but very little teaching online. As such, I will be watching for signs of decreased instructional effectiveness and may decrease course expectations so that course grades are not decreased by my inexperience with this teaching medium.

If you have a proposal for a different approach to how a component of this course could go, I’d welcome that suggestion.

2 Course Overview

This is one offering of Discrete Mathematics, a course designed to provide the mathematical tools needed for later CS courses, offered in a flavor designed to meet both the current Discrete Mathematics requirement and to fit with our pilot of a new curriculum. If that new curriculum is adopted, this course is expected to be called discrete math and theory 1 or DMT1.

2.1 Eligibility

You should take this course if and only if

  1. You have credit (or passed the placement test) for at least one of CS 1110, CS 1111, CS 1112, CS 1113, or CS 1120

2.2 Learning Outcomes

At the conclusion of this course, a successful student will be able to

  • Prove theorems and write prose proofs by hand, utilizing the following proof techniques
    • direct proof
    • proof by contradiction
    • proof by cases
    • induction
  • Converse in the language of sets, including proper use of
    • set operators (notation and meaning)
    • set-builder notation
    • cardinality, both finite and infinite (but not classes of infinity)
  • Distinguish between functions, relations, and subroutines
  • Categorize functions as invertable, 1-to-1, and onto
  • Identify relations with the reflexive, transitive, and associative properties, and identify equivalence relations in particular
  • Translate to and from, and manipulate within, propositional logic
  • Understand statements in, and perform basic proofs within, first-order (i.e., quantified predicate) logic
  • Use and understand summation notation, permutations, combinations, and factoring

I hope to also have time to cover several additional topics, including

  • additional discrete structures, including tuples and graphs
  • finite automata
  • logical reductions

3 Writeups

From time to time I create reference pages intended to supplement the textbooks (MCS and ∀x, the latter also having a solution book); I have no obvious place to list those supplements so I’m listing them here. They are: