Discrete Mathematics

Problem Set Omega


This problem set is not like the others. It is optional, and can only count positively.
If you want an opportunity to present, the deadline is Sunday, 4 December at 6:29pm. The final submission deadline is Tuesday, 6 December at 11:59pm (although this can be extended on request).

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.

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 202 students in the class to join your team, you should do something approximately 14.2 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 from 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 “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 6 December (the last day of class), you must submit your request by 6:29pm on Sunday, 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. What you submit on 4 December does not need to be your final submission, but it should be enough to make a decision on whether or not it should be presented.

Evaluation Criteria

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 (but with different topics, because of being in either Theory of Computation course or Introduction to Computing).

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: