MAT 241: Discrete Mathematics
Fall 2020
Exam 2 information
1. Allowed materials
- There is no cheat sheet of tables for this exam.
-
Calculators are NOT allowed on this exam.
- In terms of counting:
- Leave answers such as $3\cdot7\cdot2+2^3-6$ as is; do not simplify.
- Do not leave answers in terms of $P(-,-)$ or $C(-,-)$; simplify to factorials or binomial coefficients.
- Simplify $\binom7r$ for $r=0,1,7$; these do not require calculators.
- Leave answers such as $7!$ or $\binom73$ as is; do not simplify.
- In terms of solving LHRRwCCs:
- You may need to solve quadratics using factoring or the quadratic formula (memorized).
- You may need to use the Rational Roots Theorem to find rational roots for higher-degree polynomials.
- Once a rational root is found as above, you may need to use long division (or factoring) to proceed.
- You may need to solve a system of linear equations.
- I will carefully engineer the questions so the arithmetic you have to do by hand is reasonable.
- In terms of counting:
- 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 7. (Chapter 9 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:- algorithms: expressing in pseudocode, with or without recursion.
- algorithmic complexity: counting critical operations; big-$O$, $\Omega$, and $\Theta$; related 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).
- halting problem.
- basic counting: permutations and combinations, with or without replacement; binomial coefficients.
- more complex counting: combinations with replacement, multinomial coefficients, anagrams.
- counting principles: Independent Tasks, Mutually Exclusive Tasks, Pigeonhole, Inclusion–Exclusion.
- combinatorial identities: algebraic and combinatorial proofs.
- recurrence relations: various types, back substitution.
- LHRRwCCs: characteristic polynomials, with or without repeated roots, found using factoring, quadratic formula, or the Rational Roots Theorem.
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.