MAT 241: Discrete Mathematics
Fall 2021
Exam 2 information
1. Allowed materials
-
You are strongly encouraged to print out
tables1.pdf
(found on Moodle) and bring to the exam for use. (You may also look at it on your computer screen instead.) - 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 4. (Chapter 5 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 the last exam:- induction: including complete induction, but not multidimensional induction.
- applications of elementary number theory: (extended) Euclidean Algorithm to calculate GCD and inverse $\pmod m$, linear congruence, Chinese Remainder Theorem; in this section, the emphasis is on using—not proving—these famous and useful theorems.
- algorithms: expressing in pseudocode.
- algorithmic complexity: counting critical operations; big-$O$, $\Omega$, and $\Theta$; proofs using definitions or theorems; standard reference functions (Table 4.1); social conventions for a good reference function (p.193).
- example algorithms: search (sequential and binary); pattern matching: Boyer–Moore (for this exam, ignore Obvious and KMP algorithms for pattern matching; focus on Boyer–Moore instead).
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.