Final
Logistics
The final will happen in-person from 4:30-6:20pm on Monday Dec. 11. You will take the exam in Kane Hall 130.
But what happens if...
- I have a conflict with the exam time that I know about right now? Fill out this form by Tuesday Dec. 5 so we can schedule a conflict.
- I need to isolate on the day of the exam? Let us know as soon as you can (by email to Robbie); we'll schedule you for a conflict exam or find some other way for you to take the exam safely. We will not ask you for proof that you need to isolate.
UW has a flowchart to help you determine if isolation is required. If the flowchart does not require isolation, but you still believe it would be wise to isolate, we will still offer a conflict exam. (We will not ask for details on why you are isolating).
- I'm sick? Email Robbie as soon as you can. We'll schedule you for the conflict if you'll be well enough by then (in-person if you'll be able to be in a room with others). Otherwise we'll find some other way for you to take the exam safely when you're ready to work. If you aren't well enough to take an exam by the time grades need to be submitted, we can give an incomplete and finish the quarter when you're ready to work (this is the same thing we'd do pre-pandemic for significant illnesses).
- [other emergency] happens Let Robbie know as soon as you know something unusual is going to interfere with your ability to take the exam. These must be significant and beyond your control, but we will accommodate them (an example of this might be you got into a car accident on your way to campus).
The Exam Itself
In-Exam Resources
- The exam is closed-book and individual.
- We will allow each student one 8.5x11inch-sheet (both-sides) of hand-written notes during the exam.
- Hand-written means either really handwritten (like with pencil or pen) OR a facsimile of handwritten, e.g., you hand-wrote on an iPad and printed it out. If you use technology you may NOT use it to artificially shrink your handwriting.
- We may remind you of some key definitions, but only when they aren't the main point of the problem
- For example, we won't remind you what irregular means when asking you to prove a set is irregular, or what the definition of a subset is when we ask you to prove that one set is a subset of another (those are the point of those problems!), but we might remind you of the definition of mod so you remember whether it's n|b-a or n|a-b.
- We recommend you consider writing proof templates on your note sheet! We will not provide those templates on the exam.
What could be covered?
- Everything from the slide deck for lecture 1 through the slide deck for lecture 26 (Friday Dec. 1) can show up in any way on the exam. (Note this is the deck rather than the lecture itself; that content may extend to the next lecture meeting).
- There will be one problem that gives you the option of proving a language irregular (lecture 27) or proving a set is uncountable (lecture 28). It will be your choice which to do.
- We will not directly test you on the other content of lecture 28. "directly" means, for example, we might use the definition of one-to-one as the inspiration for a problem, but we would remind you of any definitions you need and would write the problem expecting it to be a "new concept" for you.
- We will not directly test you on the content only in the deck for lecture 29.
Where will the emphasis be?
- We will focus on writing problems for aspects of the course that are critical for future classes, and on topics that were covered after the midterm.
- You can expect some training wheels questions (e.g., translation, quantifiers, taking contrapositives, etc.)
- There will be two induction proofs
- Proofs will all be English proofs; we won't ask you to write an inference proof or a proof that just applies equivalences from the big chart.
What won't be covered?
- Items we identified as non-testable during the quarter, e.g. taking a reflexive-transitive closure and the DFA-minimization algorithm won't be covered.
- We will not ask you to execute the Euclidian algorithm. But just like for the midterm, you should remember what its purpose is.
Study materials
The materials below are intended to help you study. They are not a guarantee of what types of questions will be on the exam. Note that prior quarters had slightly different sets of topic coverage, so you may find questions on "non-testable" topics in these materials. The materials may also have extraneous old announcements or advice that you can ignore (e.g. the old final incorrectly claims your final will be open-book; yours is still closed-book).
How should we study?
- Take the given final under exam conditions (e.g., timed, not googling or asking others for help) so you get more practice trying to write proofs in a time-constrained way.
- Look back at old homework problems and solutions.
- Look back at old section problems.
- Think carefully about what you want on your note-sheet. With a limited time, you'll want to be able to find what you're looking for quickly, not simply list every fact.
Midterm
We will have an evening midterm, Wednesday November 15, from 6-7:30 PM. We will be split between two rooms (BAG 131 and BAG 154)
But what happens if...
- I have a conflict with the exam time that I know about right now? Or a request related to taking the exam. Fill out this form by Wednesday November 8th.
- I need to isolate on the day of the exam? Let us know as soon as you can (by email to Robbie); we'll schedule you for a conflict exam or find some other way for you to take the exam safely. We will not ask you for proof that you need to isolate.
UW has a flowchart to help you determine if isolation is required. If the flowchart does not require isolation, but you still believe it would be wise to isolate, we will still offer a conflict exam. (We will not ask for details on why you are isolating).
- I'm sick? We'll schedule you for a conflict exam within a few days of the regular midterm (definitely before Thanksgiving Break). If you can't make it to a makeup exam (because your illness is extended or you're isolating for longer), we'll discuss other options.
- [other emergency] happens Let Robbie know (by email) as soon as you know something is going to interfere with your ability to take the exam. These must be significant and beyond your control, but if they are we will accommodate them (an example of this might be you got into a car accident on your way to campus).
Homework 5 Feedback
- If you do not use late days on HW5 part 2, we intend to return feedback to you Tuesday morning.
- If you do use late days on HW5 part 2, we hope to give you feedback before the exam, but cannot promise that we will.
- We will release solutions to HW5 in-class on Monday Nov. 13
- We will not return HW5 part 1 feedback before the midterm.
Timing Logistics
- You will have 90 minutes to do the exam; we will design the exam so that with studying and preparation, we would be comfortable giving the exam in a 50-minute exam slot.
- You aren't used to writing proofs in a time-constrained environment! We don't want time pressure to be extremely intense the first time you're having to work quickly, hence the extra time. But the time limit is still there (and there will be a time limit on the final as well)! We strongly recommend taking an old exam under exam conditions (e.g., writing all the answers with pencil and paper; timing yourself) to make sure you're close to the time target.
In-Exam Resources
- The exam is closed-book and individual.
- We will allow each student one 8.5x11inch-sheet (both-sides) of hand-written notes during the exam.
- Hand-written means either really handwritten (like with pencil or pen) OR a facsimile of handwritten, e.g., you hand-wrote on an iPad and printed it out. If you use technology you may NOT use it to artificially shrink your handwriting. Similarly, you may recreate diagrams or lecture slides by rewriting and redrawing them, but may not just copy them using technology and print them.
- We will not remind you of definitions we've used frequently.
- For example, we won't remind you what what the definition of a subset is when we ask you to prove that one set is a subset of another (understanding what subset means is part of the point of the problem!), but we would remind you what the "Fundamental Theorem of Arithmetic" is if we wanted to ask you about it.
- We recommend you consider writing proof templates on your note sheet! We will not provide those templates on the exam.
- We will not provide the logical equivalences sheet; we will not ask a question requiring knowing the rule names (for example, we won't ask you to do a symbolic proof), but we might expect you to know rules we've used frequently (like DeMorgan's Law or the Law of Implication); you may write these on your notes sheet if you prefer to have them.
Topic Coverage
What you will see:
- You are responsible for topics covered through lecture 17 (Induction Practice Day). There will not be a structural induction proof on the exam.
- One of the exam questions will be a proof by induction (either strong or weak induction; not structural).
- There will be at least one other English proof.
- "Training Wheels" questions (translate between English and notation, negate an expression, take a contrapositive, etc.) are likely
- There may be other question(s) not fitting into the above list.
What you will not see:
- We will not require you to run the extended Euclidian algorithm. All algebra and other computations will be possible without a calculator. But you should still remember generally what the Extended Euclidan Algorithm process entailed (we can ask, e.g., what the algorithm was, how it was used, etc.)
- We will not have any symbolic proofs (neither applying the logical equivalences nor an inference proof). But we may still ask you to negate an expression or take a contrapositive, for example (just not to tell us the names of the steps you used).
- We will not test the details of the RSA encryption scheme discussed in lecture 14, but we do expect you to remember protions that were practiced in homework. For example, you don't have to remember what the variables n,p,q represented in the scheme or why n was public but p and q were private. But you should remember what a multiplicative inverse is and that the Extended Euclidian Algorithm is how we found them.
Practice
We recommend the following resources to study. Note that the previous midterms were given in a different mode (take-home exams rather than in-class exams).
We think the exams will still be good as practice, but you should not expect your midterm to be an exact match in terms of number/difficulty of problems.
- 22Sp's midterm exam and solutions
- 22Wi's midterm exam and solutions
- Section on November 9th will be a mix of induction practice and midterm review.
- Lecture slots on Nov. 15th will be used for review problems and answering last-minute questions.