CSE 311: Foundations of Computing I

4.0

Paul Beame

Discrete Math & Its Applications, Rosen

Examines fundamentals of logic, set theory, induction, and algebraic structures with applications to computing; finite state machines; and limits of computability.

CSE 143; either MATH 126 or MATH 136.

Required

At the end of this course, students will be able to:

express simple mathematical concepts formally
understand formal logical expressions and translate between natural language expressions and predicate logic expressions
manipulate and understand modular arithmetic expressions
create simple proofs, including proofs by induction
design two-level logic circuits to compute Boolean functions
design simple finite state machines both with and without output
design and interpret regular expressions representing sets of strings
recognize that certain properties of programs are undecidable

(a) an ability to apply knowledge of mathematics, science, and engineering
(e) an ability to identify, formulate, and solve engineering problems
(m) knowledge of discrete mathematics

Propositional/Boolean logic (3-4 lecture hours)
- logical connectives
- truth assignments and truth tables
- Boolean logic gates
- mapping between English sentences and propositional logical expressions
- logical equivalences, e.g. De Morgan's laws
- satisfiability and tautology
- Boolean algebra
- combinational logic circuits
- sum-of-products (DNF) and product-of-sums (CNF) normal forms
Predicate Logic (2 lecture hours)
- quantifiers
- quantifier order
- mapping between English sentences and predicate logical expressions
- logical equivalences involving quantifiers, De Morgan's Laws
Logical Inference (2 lecture hours)
- logical equivalences
- propositional and predicate proof rules
- methods of proof
Sets and Functions (0.5-1 lecture hour)
- Boolean operations on sets
- power set and Cartesian product operations
- Boolean operations on bit vectors
- 1-1 and onto functions
Arithmetic (3-4 lecture hours)
- divisibility
- primality and compositeness
- mod relation
- twos complement representation and its correctness
- greatest common divisors and Euclidean algorithm
- modular arithmetic including modular inverse
- optional: unique factorization, modular exponentiation, RSA
Mathematical Induction and Applications (5-6 lecture hours)
- organization of an inductive proof
- course of values (strong) induction
- recursive definitions
- structural induction
- applications and examples of inductive definitions
Relations and Directed Graphs (1.5-2 lecture hours)
- binary relations:
- properties of binary relations: reflexivity, symmetry and antisymmetry, transitivity
- composition and powers of binary relations
- directed graph representation of binary relations
- paths, connectivity, and reflexive-transitive closure
- optional: n-ary relations and relational database operations
Finite-State Machines (4.5-5 lecture hours)

deterministics finite automata diagrams
examples of DFAs including product construction
finite-state machines with output at states
minimization of finite-state machines with outputs
equivalence with regular expressions
- nondeterministic finite automata
- NFA recognition of regular languages
- equivalence of NFAs and DFAs - subset construction
- optional: conversion of NFAs to regular expressions
non-regular languages
optional: 5-tuple formal definition of DFAs, application to pattern matching

Circuits for finite state machines (1 lecture hour)
- combinational circuits for state transition functions
- addition circuits and carry look-ahead adder
- optional: parallel prefix circuits
Turing Machines and Undecidability (3-4 lecture hours)
- Turing machine definition
- relationship to high-level programming languages
- optional: countability and uncountability
- universal Turing machine
- halting problem and undecidability
- application of undecidability to questions about programs