UMBC CMSC 203
CMSC 203, Section 0401
Discrete Structures
Extra Credit Project
General Information
This extra credit project is a completely voluntary project and is not
part of the requirements for the course. The maximum number of points
that can be earned on this extra credit project is 100. To receive
the full 100 points of extra credit, the student is expected to put
forth a substantial amount of individual effort. All projects are to
be worked on as individuals. If you discuss your projects with others
(including other students, friends, or faculty members) they should be
cited in an acknowledgements section of your report or paper.
The project consists of one of two options (described in detail
below). The student is responsible for choosing a discrete math
related topic of interest and the direction of the project (with
approval by the instructor). Every project requires initial approval.
Project proposals must be submitted via email to mgasto1@cs.umbc.edu no later
than 11:59pm on Tuesday, 11/23. Project proposal should be one or
two paragraphs describing the topic area, direction, and scope of the
project. No late proposals will be approved. Upon approval,
students will have approximately three weeks to work on the projects.
Final projects (see specific requirements below) are to be submited
electronically via email no later than 11:59pm on Saturday,
12/11. Late projects will recieve zero (0) points.
The points earned on the extra credit project will be based on the level of effort put forth by the student. The general guidelines for evaluating projects is:
- Relevance of topic - 20 points
- Level of effort/detail - 50 points
- Clarity and completeness of the submitted materials - 30 points
Students are encouraged to search for topics and ideas on the web, but
all submitted work must be the work of the student. The goal of the
project is for student's to acquire and in-depth understanding of a
topic area of discrete math as well as a richer appreciation for the
subject matter. Some student's may be asked to briefly present their
project in class on 12/14.
Option 1: Computational Project
The first option for the project is a computation-based option. The
student is expected to design an experiment, implement code, conduct
experiments, and document their findingd in order to test, verify, or
explain some important aspect of discrete math. The aspects of
discrete math could be famous theorems, general properties, claims,
unproven theories, or unsolved problems. Examples of computational projects include:
- Implementing various sorting algorithms and comparing their worst
case, average case, and best case performance for various input
problems.
- Exploring prime numbers. Implementing various codes for primality testing including an exhaustive search and a probabilistic algorithm. Testing the practicality and accuracy of various methods in different situations.
- Implementing various Traveling Salesman solvers and comparing their performance.
- Implementing cryptographic techniques of various complexities.
- Developing code to solve the Tower of Hanoi for n disks. Attempting to implement an optimal solver for a variation of the Tower of Hanoi with 4 pegs.
- Choose a discrete math game and implement various strategies for playing the games. Test the different strategies. (Games include: picking up toothpicks, let's make a deal, etc.)
- The Four Color Theorem.
- Find an application of finite state automatons and implementing a pattern recognizer for this domain.
- Cellular Automata.
Students may use the examples above, but are encouraged to come up
with a topic on their own.
Requirements for Option 1:
- Proposal - Due nlt 11:59pm on 11/23.
- Project Submission - due nlt 11:59 on 12/11.
- Source code of any implemented software.
- Examples of input and output for software.
- Documentation of findings (written in LaTeX, 3-4 pages including figures, description of topic, experiments, and findings, and at least four references).
Option 2: Technical Writing Project
The second option is a writing option. For this option, students
are expected to produce a short technical report on a discrete
math topic of interest. The report may discuss important theorems in
discrete math and their applications, unsolved problems in discrete
math and the nature of their difficulty, historical accounts of
contributors to discrete math including the impact of their findings,
or important applications of an area of discrete math.
Example topics include:
- Fibonacci Numbers
- Magic Squares
- Godel's Incompleteness Theorem
- Bayes' Theory (see Bayesian Networks)
- Lewis Carroll
- Alan Turing
- Donald Knuth
Students may choose from these topics or find their own topic areas.
The latter is encouraged. The paper must be technical in nature and describe and discuss the relevant mathematics for the topic area.
Requirements for Option 2:
- Proposal - due nlt 11:59pm on 11/23.
- Paper Submission - due nlt 11:59 on 12/11.
- formatted in LaTeX
- 6-8 pages in length
- mathematical content (equations)
- at least six (preferably not web-based) references.
Last Modified: Tuesday, 16-Nov-2004 11:23:30 PM EST