MAT 241: Discrete Mathematics
Fall 2020
Exam 3 information
1. Allowed materials
- There is no cheat sheet of tables for this exam.
- Calculators are NOT allowed on this exam.
- You are strongly discouraged to use the textbook, homework, or class notes during the exam. (See first exam for instructions, explanation, and related issue regarding academic integrity.)
- You are not allowed to use other resources (Internet search, friends, etc.) during the exam.
- You may only use other electronic devices (computer, smart phone) to the extent of following exam logistics.
2. How to study
Please see tips from first exam.
3. Exam content
The exam covers everything we have done, up to and including Chapter 11. (RSA will be on the next exam.) While the exam is cumulative, we will focus on what was not already tested. Here are some topics we emphasized since last exam:- theory of computation (Chapter 9 and Section 11.3.1)
- deterministic finite automata (DFAs): with or without output, state diagrams, state tables
- grammars: regular grammars, derivations; context-free grammars, parse trees (11.3.1)
- regular expressions
- graph theory (Chapter 10 and Section 11.1)
- lots of terminology
- handshake theorem
- connectivity: walks, paths, cycles, etc.
- adjacency matrix, matrix multiplication, counting walks
- Euler circuits, trails; Hamilton cycles, paths
- planarity: Kuratowski's theorem, elementary subdivisions, isomorphisms
- Euler's formula
- regular polyhedra
- chromatic number: proper colourings, duals, 4-colour theorem
- trees: terminology, characterization
As usual, please note that this document is not a contract. I may have inadvertently left something off that ends up on an exam question. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.
4. Logistics
Logistics will be identical to Exam 1; review it if you don't remember the procedure.