CS 240: Introduction to Discrete Mathematics
Lecs 1, 2, & 3, Fall 2024

Lectures:

• Lecture 1 (Beck Hasti): MWF: 9:55 am - 10:45 am, 2650 Humanities
• Lecture 2 (Beck Hasti): MWF: 1:20 pm - 2:10 pm, B102 Van Vleck
• Lecture 3 (Scott Swanson): MWF: 11:00 am - 11:50 am, 168 Noland

Instructors:

• Beck Hasti (Lectures 1 & 2)
  hasti (at) cs.wisc.edu
  Office Hours (tentatively):
  • Monday 11:30 am - 12:30 pm (in 5360 CS)
  • Tuesday 9:00 - 10:45 am (in 5360 CS)
  • Wednesday 2:45 - 4:00 pm (in 5360 CS)
  • and by appointment
• Scott Swanson (Lecture 3)
  scott.swanson (at) wisc.edu
  Office Hours (tentatively):
  • to be determined

Course Description:

CS 240 gives an undergraduate-level introduction to discrete mathematics geared towards prospective Computer Science and Electrical and Computer Engineering majors. It covers fundamental concepts of mathematics (definitions, proofs, sets, functions, and relations) and focuses on the discrete structures that are ubiquitous in digital computing: integers, bits, strings, graphs, and trees.

The goal of the course is two-fold:

• making you familiar with those structures and related notions that are relevant to computer science, and
• developing your skills to reason rigorously about those structures and notions, especially in an algorithmic context.

Topics: Basic concepts of mathematics (definitions, proofs, sets, functions, and relations) with a focus on discrete structures: integers, bits, strings, trees, and graphs. Propositional logic, Boolean algebra, and predicate logic. Mathematical induction and recursion. Invariants and algorithmic correctness. Recursion, recurrences, and asymptotic growth analysis. Fundamentals of counting. Regular expressions and finite automata.

Prereqs: One semester of calculus (Math 217, 221, or 275). It will be useful to have some prior programming experience (or be concurrently enrolled in an introductory programming course such as CS 200 or CS 220).

Topics:

Below is a tentative schedule of the topics and order in which they will be covered. Course content comes from the lectures and discussion sections as well as a zyBooks E-Text and a set of on-line readings (linked in the schedule below).

Each topic roughly corresponds to one week. See Canvas for the most up-to-date schedule.

1. Introduction
2. Propositions and Predicates
3. Sets
4. Proofs
5. Induction
6. Invariants
7. Program Correctness
8. Recursion
9. Recurrences
10. Asymptotic Analysis
11. Relations and Functions
12. Graphs and Trees
13. Finite State Automata and Regular Expressions
14. Counting