Calendar Description

Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.

Assumed Background

I am assuming that the students will do this course in 2nd term of their first year. Requirements include:

At least one course in Grade 12 Mathematics (with U TAG)
Completed MATH 1007 (Elementary Calculus) with a grade of ...
Either completed or concurrently registered in MATH 1104 (Linear Algebra)

Should have reasonable idea of

1. Given a solution for a Grade 12 Math problem, should be able to verify it with minimal help.
2. Should have Mathematical sophistication, for example should be able to solve/show that
- Sum of two odd numbers is even
- Not all real numbers are rationals
- The number of prime numbers is infinite
- The number of possible subsets of set of size n is 2^n
- Should know the meaning and significance of basic functions: log x, e^x, x^2, x, x^3
- Should know what is a function, what are properties of function.
- Given a system three linear equations, in three variables, should know how to solve it.
- Should know how to solve a quadratic equation
- Should know how to compute a formula for the sum of first n natural numbers.

....

Learning Objectives

Objectives for the whole course

Mathematical Reasoning: Should be able to read, comprehend and construct mathematical arguments. Should develop sufficient background in mathematical logic, and should be able to apply to construct proofs. Learn some of the standard proof techniques (contradiction, induction, ..).
Number Representation: Learn Bits, Bytes, Binary Representation, Floating-point representation, what is a 64-bit machine?
Discrete Structures: Ability to work with discrete structures - abstract mathematical structures which are used to represent discrete objects and the relationships between objects. Examples of these structures include sets, strings, graphs, and finite-state machines.
Algorithmic Thinking: Solving problems by a step-by-step process (algorithm), described in a pseudo-code. Students will get some idea on how to specify the algorithm, how to argue about its correctness, and how to argue about the computational resources (time and space) being used. (Simple algorithms like, Euclid GCD, Binary search, Merge-Sort, breadth-first search, MST, etc. may be discussed.)

Topics

This list is with respect to ROSEN's Discrete Math 6th edition and very closely follows the UBC Discrete Math Course. Main omissions with current 1805 are - Big-O notation, Countability, and Relations. Big-O will be covered in COMP 2402/COMP 2804.

Propositional Logic [1.1+11.3]: Introduce proposition, truth table, Logical operations (AND, NOT, OR, XOR..), Logical/Combinatorial Gates - simple circuits - how to design an half - full adder - how to design an adder for x+y, where x and y are 3 bits long [Introduce binary representation; complexity of a circuit = # of basic circuit components (wires+gates)]

Logical Equivalences [1.1+1.2]: if-then-else, implication, tautology, contradiction, de Morgan's Law. Learn how to simplify, manipulate, and understand complex logical statements.

Number Representation [3.6 + ?]: Representation of integers, hexadecimal expansion, base conversion, operation on binary numbers - addition, 2's complement, whats a 64-bit machine - what are limitations of this representation. Floating-point representation.

Predicates and Quantifiers [1.3+1.4]: whats a predicate? universal quantifiers, existential quantifier, negation of quantified statements, why are they important in CS (e.g Logic Programming), nested quantifiers and their ordering.

Rules of Inference [1.5]: What is a valid argument in propositional logic, basic rules of inference (if-then-else), using rules to build arguments, resolution, quantification.

Proof Techniques [1.6, 1.7, 3.4]: different methods, strategies. Check whether a propositional logic proof is valid or not, whether it is proving the statement. Practice on simple exercises - how to build a counterexample, how to prove a given statement - what techniques to use. (possibly cover Halting Problem - As an example of Proof by Contradiction [3.1]).

Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.

Introduction to Finite State Machines and Graphs [Parts of 12.2+12.3, Relevant Parts of Chapter 9]: Whats a DFA, how to trace the operation of a DFA, concept of acceptance/rejection of a string, concept of a language, how to design a DFA accepting s simple language. Language as a set of strings. Also show that DFA is a graph - a directed graph - and discuss some properties of undirected and directed graphs - paths and connectivity.

Induction and Recursion [Chapter 4]. Establish properties of self-referential structures using inductive proofs. What are steps involved in proof by induction - show right and wrong proofs - standard pitfalls - describe simple recursive algorithms (e.g. n!, linear search, binary search, merge sort, tree traversals, and discuss how to show that they are correct using Induction and how to argue about computational resources being used).

Sets and Functions [2.1, 2.2, 2.3]: Power Set, Cartesian Products, Set Operations and de Morgans Laws. Functions : definition, 1-1 and onto, inverse (its expected that they will learn in depth about functions in Calculus and/or Linear Algebra courses).

Advanced DFA/NFA [12.1,12.2,12.3]: NFA, Designing NFA, Equivalence of DFA and NFA, existence of languages not recognized by a DFA - regular languages. Idea is to show the capabilities and limitations of these simple computation model - and show how discrete math (proof by contradiction, sets, power set, pigeon hole principle) are used to establish non-trivial results.

More Graph Theory [Relevant Parts of Chapter 9] Stating some of the standard daily-life problems, in terms of Mathematical Abstraction as graphs, and showing some simple graph properties and algorithms which may address the problem. (e.g. MST, DFS, BFS).