Discrete Mathematics

Problem Set Omega


This problem set is not like the others. It is optional, and can only count positively. The submission deadline is Monday, 4 December at 11:59pm. You should do it if you have an idea for something worthwhile, fun, or interesting to do (that’s a logical or, not an exclusive xor). A good submission for this assignment can also help your grade, counting like a bonus problem set. An excellent submission could count like two bonus problem sets. If you write a musical about Evariste Galois as good as Hamilton, you will get an automatic A+ in the class and not need to take the final.

Collaboration Policy

For this assignment, you may work alone or with as many other people as you choose. If you work in a team, your team should jointly post a single submission with all of your names on it. All team members will receive the same credit, unless you specify and justify an uneven distribution in your submission. Your team may be as large as you want, but the expectations for quality and value of your submission scale according to sqrt(N) (that is, a team with 4 people should do something twice as impressive as an individual to merit the same credit; if you are able to convince all of the other 320 students in the class to join your team, you should do something approximately 17.9 times as impressive as what would be expected from a single student). You are welcome to include people not in the class in your team (and they do not increase the value of N).


Create an artifact that conveys some idea related to this class to a selected target audience.

Target Audience

You can define your target audience but should specify what it is. Examples of target audiences include “five year olds”, “typical third graders”, “your parents”, “UVa students majoring in history”, “Martians”, “cs1110 students”.

Your artifact can be anything you want, so long as it includes some representation as a finite sequence of bits that can be posted on the Internet. Examples of possible artifacts include a written story, a comic, a video, a song (lyrics), or an interpretive dance. If your artifact cannot be posted on the Internet (for example, if you bake a cake, build a quantum computer, or develop a time machine) you should still make some description of your artifact (including a picture if helpful) that can be posted.


You should submit your artifact by use this web form:

Problem Set Omega Submission Form.

Your submission should include: (a) a description of your target audience; and (b) a link to your artifact, hosted at a URL that will not disappear shortly after you graduate.

Your submission may also (optionally) include a poetic license statement. Everything technical in your artifact should be correct, unless you carefully document how you know it is incorrect. To convey the essence of an idea effectively to a general audience, it may be necessary to simplify some things in ways that are not technically correct but do not violate the important essence of the idea. If you do this, include a poetic license statement to your submission that explains and justifies your decisions (otherwise, you will lose points for any technical inaccuracies).

Optional Presentation

If you would like to present, perform, or share your artifact in class on 5 December (the last day of class), you must submit your request by 5:59pm on Monday, 4 December. Your request should explain what you would like to do and how much time you think you need for this. Given the size of the class, it may not be possible for all teams that want to present to do so, so selection will be done based on what you submit with an emphasis on things that will be worthwhile or enjoyable for the whole class.

Evaluation Criteria

Since this is an “optional” assignment, submissions that are not considered to have significant value will not be worth any credit. To be worth credit, your submission should be something that (in the subjective opinion of the course instructors) would be worth showing to someone in your target audience.

Submissions will be evaluated on technical correctness and perceived effectiveness in conveying an important idea to your defined target audience. Aesthetic merit, entertainment value, and creativity are also important, but only in as much as they support the goal of conveying an idea from discrete math to your target audience.

Motivating Examples

To give you some ideas, here are some examples of things students have done in past years for similar assignments (including some from classes other than cs2102).

cs2102 Fall 2016

(You can see a larger selection of submissions from Fall 2016 here: psZhighlights.)

Logical Operators
Helen Simecek

Carlos Goes Birdwatching (A story about binary operations for middle school students)
Derrick Chien Huang, Andrea Chang, Jennifer Qian

Sets and Superheroes
Matt Huo, Joe Karaki

Call of Duty and Countable Infinities
Aarron Braxton, Shreyas Hirway

Induction Rap
Milan Bharadwaj

Gumball State Machine
Priya Nakhre

Modeling Mario Party with State Machines
Benjamin Fuhrman

State Machines and Breakdancing
Kenny Le

Recursive Music
Jiahong Chen, WenBin Qi

Other Classes

Conveying Computing (cs1120: Computing: Language, Logic, Machines, Fall 2011)

Turing Machine Cake Balls, Megan Dunne and Jamie Miller

Conveying Complexity Highlights (cs3102: Theory of Computation, Spring 2010) (you can see all the submissions here, but many of the links don’t work anymore since people used their people.virginia.edu pages)

The most successful (at least by number of views) is Authur Gordon, Allison Gurlitz, Stephen Lam, and Eugene Moy’s A “Downfall” Parody: P = NP:

Mario – Determinism vs. Nondeterminism, by Navid Hosseini, John Koelling, Trung Tran, and Ben Powell:

From CS588: Cryptology - Principles and Applications (Fall 2001), Adam Glaser and Portman Wills, Safe Computing at UVA:

Some examples that were not for course assignments:


Dori-Mic and the Non-Equivalence of Kleene-* and Kleene-X (Trailer)
(Full Feature)

Dori-Mic and the Universal Machine.