MAT 241: Discrete Mathematics

Fall 2021

Final exam information

1. Exam format

The final exam is comprised of two portions:

1. Mandatory portion: Unit 5 exam.
   • This will be on new material that has not been tested before (see below).
   • Think of it as a 5th midterm exam.
   • You should plan to spend up to 70 minutes on this portion, as usual.
2. Optional portion: bonus opportunity to recover some points for Units 1 through 4.
   • You may select up to two units to re-test.
   • If you want to re-test Unit $N$, where $N\in\{1,2,3,4\}$, then:
     • Review and master the topics of that unit (see previous exam topics).
     • In the same exam PDF, there will be a section clearly marked as Unit $N$.
     • In that section will be a couple of problems (similar to the harder ones on Exam $N$).
     • Do those.
     • If you do well, I will use their average to replace your Exam $N$ score.
     • But this is capped at 90%.
     • If you don't do well, I will NOT lower your Exam $N$ score (so you have nothing to lose).
   • Since the grade replacement is capped at 90%, if you got above 90% on Exam $N$, you should not bother re-testing Unit $N$.
   • This benefits all kinds of students:
     • If you consistently did well on all midterm exams, you need not worry about re-testing.
     • If you had a fluke on one or two exams, this is your chance to make it up.
     • If you consistently did poorly on all midterm exams, you should focus your attention on two units (of your choice) and master that material.
   • If you object to this bonus opportunity, simply don't re-test and your grade won't be affected.

2. Allowed materials

• If you are re-testing Unit 1 or Unit 2, you are 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.

3. How to study

Please see tips from first exam.

Get enough rest during finals week and the weekend before. Create a list and schedule of what you will do each day, including enough sleep in your schedule. Start studying early enough so you can take breaks; reward yourself after working hard.

Practicing by solving problems is much more effective than reading over solutions. There are plenty of review questions in the textbook. Going over homework/exams and correcting mistakes is also a good idea.

4. Exam content

The exam covers everything we have done. While the exam is cumulative, the mandatory portion will focus on what was not already tested. Here are some topics we emphasized since the 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.
• RSA encryption (3.4.6).
• halting problem (4.4).

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.

5. Logistics

Logistics will be largely similar to Exam 1; review it if you don't remember the procedure. The only change is that it is during our officially scheduled final exam period, which runs for 2 hours. (I don't anticipate you needing that long for the exam.)

Also, whether you re-test or not, you will simply upload a single PDF of all the problems you attempted, as usual. (You do not need to scan "blank" problems from sections you didn't attempt to re-test.)