Purpose

• Show your understanding of a topic related to the course.
• Presentation skills.

Format

• A talk of length 10-15 minutes.
• Slides. (Required for everyone. You need to submit those slides. )
• You can use the whiteboard during your talk.

Structure

1. Introduce the topic. Given the basic definition. Or state the problem you try to solve. (Be friendly to you audience.) You can lightly use some Youtube video to help. But please note that it is your talk, you don’t want to use the video for too long.
2. Solve the problem, typically you present a proof or some calculation (typically for counting and probablity problems). Or if you are introducing some mathematical software, demo what kind of problem it can solve and how to solve it.
3. Summerize the skills that you used form this course.
4. Q and A.

Topics.

I don’t sugguest topics. You need to pick you own topics. However, the following topics are examples to help you understand what is expected. Once you have selected a topic, you need to send me an email to seek my approval on the topic.

Set Theory and Mathematical Logic:

1. More application of Cantor’s Diagonalization trick in proof.
2. Cantor-Schroeder-Bernstein theorem.
3. Lean theorem prover.
4. SAT solver tutorial.

Recursive function, inductive proof, and counting

1. Problems that has beautiful recursive solutions that we haven’t talked about yet in the class. For example,
   • Derangement
   • Domino and Tromino Tiling
2. Inductive proofs and possibly the recursive algorithms inspired by them.
3. Counting with recursion. For instance, the Catalan Numbers.
4. Generating functions of counting problems. See example in Generatingfunctionology.
5. Correctness of an algorithm by induction.
6. Recursive definitions and structural inductive proof. Example: propositional logic string parsing.

Graphs and trees.

1. Recursive algorithms on Graphs and trees.
2. Proofs on graphs and trees.

Probability.

1. Understand Bayes’ Rule via simulation. Example 1.10.1 (Page 59-62), An Introduction to Kolmogorov Complexity and Its Application, Fourth Edition. The above list is not intended to be complete. Again, I expect that you will do you own research to pick your own topic.

Topics from previous semesters

• Fall 2023. For some reason the class likes gambling games and probability a lot.