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

Lectures:

  • Lecture 1: MWF: 9:55 am - 10:45 am, 5206 Social Sciences
  • Lecture 2: MWF: 1:20 pm - 2:10 pm, 113 Psychology

Instructor:

  • Beck Hasti
    hasti (at) cs.wisc.edu
    Office Hours:
    • Tuesday 1:00 - 2:30 pm (via Zoom)
    • Wednesday 2:30 - 4:00 pm (in 5375 CS)
    • Friday 11:30 am - 12:30 pm (in 5375 CS)
    • and by appointment

Announcements:

  • Canvas is used to deliver all course materials.
  • Course information (for both lectures) can be found on the COMP SCI 240 Syllabus

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/22/2021     ©2021 Beck Hasti