CSCI 246: Discrete Structures

Spring Semester 2026

Final Presentation

Description

You are to split up into teams of 3-4 students to create a 12-15 minute presentation with 3-5 minutes of Q&A. As a team you are to pick a topic/application in computer science you are interested in and explain the mathematics that underlies the topic/application. A successful presentation will introduce the core mathematical concepts underlying the chosen computer science topic / application, explain the computer science topic / application, and conclude with an example / demonstration of how the mathematical concepts are used in the CS topic / application. Each member of the team is expected to contribute to the presentation's design and delivery.

Generative AI Use

On the final presentation, you may use generative AI to explore computer science topics and their connection with mathematical concepts; however, as a team you are responsible for ensuring that the information you present is correct and accurate. The presentation should be your own work but may be informed / assisted by your use of generative AI. Additionally, the presentation will consist of some time for Q&A, you as a team are expected to be able to answer questions about your presentation / topic.

Grading Criteria

40 pts of your grade will be based on the factual correctness of your presentation (minor issues or typos will not significantly impact your grade).
30 pts of your grade will be based on the quality of the presentation:
- Is it self-contained?
- Does it have a clear logical flow?
- Does it clearly explain the key concepts?
- Does it include meaningful examples or demonstrations?
- Is the topic appropriately scoped?
10 pts of your grade will be based on your delivery:
- Is the presentation clear and easy to follow?
- Is the pacing appropriate?
- Are you speaking clearly?
- Are you engaging with the audience rather than reading directly from slides?
20 pts of your grade will be based on the Q&A portion:
- Are you able to answer on-topic questions?
- Do you demonstrate understanding of the material?
(You are not expected to answer every question, but should be prepared to discuss the material you present.)

Note: Strong presentations require both correct content and clear communication. Even technically correct presentations may lose points if they are difficult to follow.

Potential Topics

Graph Theory

Bipartite graph matching and resource allocation, scheduling, job assignments, etc.
PageRank and Random walks and Search Engines
Weighted graphs and shortest path algorithms (and e.g., Google Maps routing)

Algorithms and Complexity

Asymptotic Analysis and Algorithmic Tradeoffs (pick a specific algorithmic problem)
Modular arithmetic and Probability theory and Hashing
Optimization and Greedy Algorithms (interval scheduling, coin change, etc.)
Recurrence relations and Dynamic Programming
Probability and Randomized Algorithms

Cryptography and Security

Modular Arithmetic, Prime numbers, Number theory and (RSA) Encryption
One way functions and probability theory and Cryptographic Hashing/Passwords
Graph theory and exploit chains

Data and Encoding

Probability theory and Bloom filters
Probability theory/Hamming distances/Algebra and Error Correcting Codes (data transmission and QR codes)
Trees, Greedy Algorithms, Probability Theory and Huffman Coding (compression)

Automated Reasoning about Software

Logic and Satisfiability and program correctness
Graph theory and program representations (data flow, control flow, etc.)
Logic and Satisfiability and verified Hardware

Compilers and Automata

State machines (labeled graphs) and regular expressions
Graph coloring and register allocation
Graph and tree algorithms and Abstract syntax trees (and program optimizations)

Tips for Presentation

You should assume your audience understands basic discrete mathematics, but not your specific topic.

What makes a good presentation

Motivation (1-2 minutes): What is the problem or application? Why should we care?
Mathematical Background (3-5 minutes): Introduce the key concepts (definitions, small examples).
CS Application (3-5 minutes): Explain how the math is used in the application.
Worked Example / Demo (2-4 minutes): Walk through a concrete example.
Summary (1 minute): Recap the key idea and takeaway.

Common Pitfalls

Spending too much time on the application and not enough on mathematical concepts.
Introducing technical definitions without an example.
Choosing a topic that is too broad (e.g., "machine learning").
Including too many slides (estimate 1 minute per slide).
Too much text on slides. Reading directly from slides.
Not practicing what to say on each slide / practicing transitions.
Not including page numbers on slides (helpful for questions).

Choosing a Topic

Your topic should be narrow enough to explain clearly in a 10–15 minute presentation. For example, "Graph Coloring for Register Allocation" is a good topic, while "Compilers," "Machine Learning," or "Databases" are too broad. If you choose a topic covered in class, you are expected to go beyond what was discussed (e.g., more detailed examples, variations, or deeper explanation).

Important Note

A strong presentation explains a small number of ideas clearly and connects them directly to a concrete example.

Example: Graph Coloring and Register Allocation

In a recent lecture, we discussed how graph coloring is used in register allocation. The full topic fit within a 10–15 minute lecture; however, the focus was more on graph coloring itself rather than the application.

If this were structured as a final presentation, the focus would shift toward the application and how the mathematics supports it. A strong presentation might be organized as follows:

Motivation: Compilers must assign variables to a limited number of CPU registers so that programs run efficiently.
Problem Setup: Variables that are live at the same time cannot share the same register.
Mathematical Model: Construct an interference graph, where:
- Vertices represent variables
- Edges connect variables that cannot share a register
Key Insight: Assigning registers becomes a graph coloring problem, where adjacent vertices must receive different colors.
Mathematical Concepts: Define graph coloring and the chromatic number. If a graph is k-colorable, then the program can be executed using k registers.
Worked Example: Start with a small program, construct its interference graph, determine a valid coloring, and show the resulting register assignment.
Takeaway: Any program can be modeled as an interference graph. If the graph is k-colorable, then the variables can be assigned to k registers accordingly.

Your final presentation should follow a similar pattern: introduce the problem, explain the mathematical model, and demonstrate how the math is used in practice.

Note: The goal is not to cover everything about graph coloring, but to explain just enough mathematics to clearly support the application.

Grading Rubric

Each category will be graded holistically within the ranges shown below.

Mathematical Correctness (40 points)

Criteria	Weight	Excellent	Satisfactory	Needs Improvement
Accuracy of Concepts	20 pts	All mathematical definitions and statements are correct and clearly stated (15-20pts).	Minor errors or imprecise definitions (10-15pts).	Major misunderstandings or incorrect statements (0-10pts).
Use of Mathematics	20 pts	Mathematics is used appropriately and meaningfully in the presentation (15-20pts).	Some connection to math, but shallow or partially unclear (10-15 pts).	Little to no meaningful use of mathematics (0-10pts).

Presentation Quality and Structure (30 points)

Criteria	Weight	Excellent	Satisfactory	Needs Improvement
Organization & Flow	10 pts	Clear easy to follow structure (8-10 pts).	Some structure, but transitions unclear (4-7 pts).	Disorganized or hard to follow (0-3 pts).
Clarity of Explanation	10 pts	Concepts explained clearly with appropriate level of detail (8-10 pts).	Some explanations unclear or rushed (4-7pts).	Difficult to understand (0-3 pts).
Examples / Demonstration	5 pts	Includes a clear, relevant worked example or demo (4-5 pts).	Example present but incomplete or unclear (2-3 pts).	No meaningful example (0-1 pts).
Scope & Focus	5 pts	Topic is well-scoped for 12-15 minutes (4-5 pts).	Slightly too broad/narrow (2-3 pts).	Poorly scoped (0-1 pts).

Delivery and Slides (10 points)

Criteria	Weight	Excellent	Satisfactory	Needs Improvement
Delivery	5 pts	Clear speaking, good pacing, minimal reliance on reading slides (4-5 pts).	Some reading or pacing issues (2-3 pts).	Mostly reading slides or difficult to hear/follow (0-1 pts).
Slide Quality	5 pts	Slides are clear, readable, and not overly dense (4-5 pts).	Some clutter or too much text (2-3 pts).	Slides are hard to read or poorly designed (0-1 pts).

Q&A (20 points)

Criteria	Weight	Excellent	Satisfactory	Needs Improvement
Understanding of Topic	10 pts	Demonstrates strong understanding when answering questions (8-10 pts).	Partial understanding (4-7 pts).	Unable to answer basic questions (0-3 pts).
Engagement in Q&A	10 pts	Multiple team members contribute; answers are thoughtful (8-10 pts).	Limited participation or shallow answers (4-7pts).	Minimal engagement (0-3 pts).

Last modified: April 16, 2026