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

Lectures:

  • Lecture 1: MWF: 9:55 am - 10:45 am, 1800 Engineering Hall
  • Lecture 2: MWF: 1:20 pm - 2:10 pm, S413 Chemistry

Instructor:

  • Beck Hasti
    hasti (at) cs.wisc.edu
    Office Hours (tentatively):
    • Tuesday 9:00 - 11:00 am (in 5360 CS)
    • Wednesday 2:30 - 3:30 pm (in 5360 CS)
    • Friday 11:30 am - 12:30 pm (in 5360 CS)
    • and by appointment

Announcements:

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
Last Updated: 9/11/2023     ©2023 Beck Hasti