Virginia Tech - CS6104 Class Projects
SYMBOLIC COMPUTATION PROJECTS
Here is a list of who in the class is working on what projects:
(Project list created 6/6/96; updated 6/7/96; presentation dates added 6/19/96)
PROJECT IDEAS (Created May 27, 1996)
Here is a list of ideas to stimulate your choice
of a class project.
A project can be tackled by an individual student or by a team
of two or three students.
A team that includes both a mathematician and a computer scientist
should work well.
At least one team member should be experienced at technical writing.
Education
I intend to use Mathematica as a tool
in teaching
CS 5024, Models and Analysis,
in the Fall.
As part of that use,
I would like to have Mathematica packages or notebooks
to develop some of the computationally expensive topics.
A non-exhaustive and non-disjoint list of topics is:
-
Combinatorics;
-
Generating functions;
-
Techniques for solving recurrences;
-
Probability;
-
Stochastic processes;
-
Markov chains;
-
Queuing systems and queuing networks.
Some subset of these topics implemented in a Mathematica notebook
could make a nice educational package.
CS 5034, Models of Computation
is more directly related to the theme of this course.
Here Larch and Larch Prover would be good tools for developing
educational materials.
A potential list of topics is:
-
Knuth-Bendix completion;
-
Formal program specification and verification;
-
Formal semantics for programs.
Since I have not taught this course,
it will be helpful if you have taken it.
Dynamic programming,
as taught in an algorithms course such as
CS 4104, Data and Algorithm Analysis
or
CS 5114, Theory of Algorithms,
is typically the most "mathematical" method of developing
optimization algorithms
that is presented.
It should be possible to develop a Mathematica notebook
to present the paradigm of dynamic programming
with examples
AND with the ability to automatically implement prototype dynamic programming
algorithms using Mathematica formulas
to fill in the blanks in the paradigm.
History
For the historians among us,
I can think of at least three interesting (library and web) research projects:
-
Trace the history of symbolic computation as a mathematical subject.
Start with Axel Thue in the early part of this century and
perhaps with others even before him
to identify the key players (Church, Rosser, Turing, etc.)
in the development of symbolic computation
and what motivated them.
Write a nice and interesting paper that presents the history you find,
along with plenty of references to the key papers.
-
Trace the history of symbolic algebra.
Take the same approach as the previous point.
-
Trace the history of symbolic computation systems.
Look at all the current symbolic computation systems,
as listed on, say,
Symbolic Net,
and trace their origins.
What caused one system to evolve from another?
What was the motivation for the earliest systems?
For the most specialized systems?
You may be able to do a lot of the initial research for this one
on the web.
Then write a nicely structured paper.
Mathematics
Symbolic computation has many applications in mathematics.
Explore one of those applications in some depth,
such as solving systems of polynomial equations.
Compare different methods for achieving the same symbolic end.
Research the history of automated theorem proving in mathematics.
What systems have been developed to do theorem proving?
What is the history of these systems?
What are some notable successes and failures?
Research
I have a few research problems
that I would like to employ symbolic computation (probably Mathematica)
during their solutions.
Here are some:
-
There is a model of cycle stealing (one workstation
using idle computational resources at another workstation)
that employs the technique of dynamic programming
to find an optimal solution.
One could implement a prototype in
Mathematica to compute these optimal solutions
and to develop intuition regarding the "behavior" of these solutions.
-
Map anamorphosis is the concept
of making the area of each region in a map
be proportional to some quantity assigned to the region.
The problem is to find an algorithm that produces the requisite map.
The solution to this problem seems to involve
an interesting mixture of graph theory and real analysis.
Mathematica could be used to implement the symbolic manipulations
and perhaps even to search for a proof
that such an algorithm exists!
-
Ben Keller is working on a system to find Gröbner bases
in path algebras.
He has a prototype system that is suited to experimentation.
There are several experiments
that we would like to run regarding
matters of admissible orders,
the underlying graphs, etc.
Perhaps you would like to run the experiments and report the results!?!
Of course,
you may want to show how symbolic computation
can benefit your own research!
Symbolic Computation Systems
Take two or three symbolic computation systems
and compare them with respect to philosophy, audience,
and usability.
In particular you might implement several different computations
in each of them and compare their programming techniques
and efficiency.
This might require that you have access to all the systems you study.
Alternately,
you might find detailed implementation information
on one or two (fairly general) systems
and organize and present that.
This is likely to be difficult to do for a commercial system,
but perhaps you can find published information on a public domain system.
Please report any problems found in these pages to:
CS6104 EI Account (cs6104@ei.cs.vt.edu)