## Final exam

The days/times for the final exam are:

• (A and C lectures): Tuesday 11th 1:30pm or Thursday 13th 8am (you can pick either time)
• (B lectures): Monday 10th 1:30pm or Friday 7th 8am (you can pick either time)

Around the last week of classes, we'll set up a form for you to sign up for one of the two times corresponding to your lecture.

The final consists of three parts, each 40 minutes long:

• Part A: inequality proof and review questions
• Part B: countability and state diagrams
• (optional) retake of one examlet from examlets 1-10

The whole thing should take about 2 hours.

If you do a retake, you will receive the higher of your retake and original scores.

## Weekly examlets

Weekly examlets will be given in class on Monday or Tuesday (depending on your lecture), starting in the third week of classes.

Before the first examlet, you must read the exam instructions. These instructions will NOT be reprinted with each examlet.

When writing equations in moodle, it's often helpful to know some basic latex commands. Here is a brief guide

The listed chapters and skills are the new skills for each examlet. The examlet will focus on these new skills. However, be aware that you're still expected to remember concepts from earlier in the term.

The information (e.g. skills list, study problem) for each examlet should be viewed as tentative until a week before the examlet date. We don't expect large changes but there might be small ones.

Examlet Week Given Textbook sections Skills list Study Problems
#1: Prerequisites and Logic Week 3 Chapters 1 and 2
excluding 1.5-1.6
Examlet 1 math prerequisites
logic
#2: Number theory Week 4 Chapters 3 and 4
excluding 4.12-4.14
Examlet 2 proofs
number theory
#3: Modular arithmetic
Set theory
Week 5 4.12-4.14, Chapter 5 Examlet 3 modular arithmetic
set theory
#4: Relations Week 6 Chapter 6 Examlet 4 relations
#5: Functions Week 7 Chapters 7 and 8 Examlet 5 functions
#6: Graphs Week 8 Chapter 9 Examlet 6 graphs
#7: Two-way bounding
Easy Induction
Week 9 1.5, Chapter 10, 11.1-11.7 Examlet 7 two-way bounding
easy induction
#8: Induction
Recursive Definition
Week 10 Chapters 11 and 12 Examlet 8 unrolling
induction
#9: Trees, Grammars Week 11 1.6, Chapter 13
excluding 13.6, 13.7
Examlet 9 tree induction
[holiday] Week 12
#10: Big-O, Algorithms, Recursion Trees Week 13 13.6, 13.7, Chapter 14, Chapter 15 Examlet 10 recursion trees
algorithms
#11: NP
Collections of Sets
Week 14 Chapters 16, 17, 18 Examlet 11 contradiction
collections of sets
Final: State Diagrams
Countability
Finals week Chapters 19, 20 Final examlet inequality induction
state diagrams
countability