\documentclass[11pt,twoside]{article}

\usepackage{xspace}

\newcommand{\coursenumber}{CS 6104}
\newcommand{\coursetitle}{Symbolic Computation}
\renewcommand{\docdate}{May 20, 1996}
\newcommand{\doctitle}{Syllabus: \coursenumber---\coursetitle}

\newcommand{\firstpageheading}[1]{
\vbox to 0pt{\vskip -#1
\hbox to \hsize{\sl \vbox to 8.5pt{}\doctitle\hfill\docdate\hfill \rm 1}\vss}
\nointerlineskip
\vspace*{-15pt}
}

\pagestyle{myheadings}
\markboth{\hfill\docdate\hfill\doctitle}{\doctitle\hfill\docdate\hfill}

\addtolength{\textwidth}{1.60in}
\addtolength{\textheight}{1.40in}
\addtolength{\evensidemargin}{-1.25in}
\addtolength{\oddsidemargin}{-0.25in}
\addtolength{\topmargin}{-.70in}

% define environment for a topic

\newlength{\topicwidth}
\setlength{\topicwidth}{5.4in}

\newcommand{\topicrule}{\rule[-9pt]{0pt}{10pt}}

\newenvironment{topic}{\begin{minipage}[t]{\topicwidth}
\raggedright}
{\topicrule\end{minipage}}

% Some new macros

\newcommand{\Grobner}{Gr\"obner\xspace}
\newcommand{\Mathematica}{\emph{Mathematica\/}\xspace}

\begin{document}

\firstpageheading{50pt}

\thispagestyle{empty}

\begin{center}
\Large\bf\doctitle\\
\smallskip
\Large\bf First Summer Session, 1996\\
\smallskip
Home page: \verb,http://ei.cs.vt.edu/~cs6104/,
\end{center}

\section*{Instructor:\ \ Lenwood Heath}
\begin{itemize}
\item
\textbf{Office:}\ \ 638 McBryde Hall
\item
\textbf{Office Hours:}\ \ 11:00--12:00, Monday through Friday
\item
\textbf{EMAIL:}\ \ {\tt heath@cs.vt.edu}
\end{itemize}

\section*{Class Meets:\ \ McBryde 218, 9:30--10:45, Monday through Friday}

\section*{Final Exam:\ \ None}

\section*{Index Number:\ \ 0310}

\section*{Useful Prerequisites:}
\begin{itemize}
\item
Formal language theory
\item
Compilers
\item
Programming languages
\item
Algorithms
\item
General exposure to Computer Science
\item
Abstract algebra
\item
Logic
\end{itemize}

\section*{Description}

This course pursues the assertion that
\begin{center}
\bf All computation is symbolic!
\end{center}
from a Computer Science perspective.
See the ad for the course on the Web pages for additional thoughts.
Specifics are in the topic list at the end of the syllabus.
Everyone will have a chance to indulge his or her own interests.

\section*{Textbooks:\ \ None!}

\section*{On Reserve}

See the latest reserve list through the class web pages.

\section*{Sources}

The material on formal languages and automata
can be found in the books (on reserve) of Hopcroft and Ullman
and of Lewis and Papadimitriou, among others in the library.
The material on string rewriting
is taken from \emph{String-Rewriting Systems}
by Book and Otto;
the library does not have this,
but very similar material is in the book (on reserve) by Jantzen.
Term-rewriting systems can be found in survey chapters of the books
(on reserve)
\emph{Handbook of Theoretical Computer Science,} volume B,
and
\emph{Handbook of Logic in Artificial Intelligence
and Logic Programming,} volume 1,
among other surveys in the literature.
Gr\"obner bases are covered in the book
(on reserve)
by Cox, Little, and O'Shea,
as well as a number of other books and papers.

\section*{Work in the Course and Grades}

The work in the class consists of homework, class presentations,
scribing, and a class project.
Each of the first three contributes about 20\% to the grade,
while the class project contributes 40\% to the grade.
Anyone who wishes to sit in on the class is expected to participate
by making at least one presentation
and being in the scribe rotation.

\paragraph{Homework.}

\begin{sloppypar}
There will be four small homework assignments
on these topics:
symbolic computation in \Mathematica,
string rewriting and term rewriting,
unification and Knuth-Bendix,
and
the Larch prover (LP).
Homework submission in \LaTeX\ is encouraged
(email the source to \verb,cs6104@ei.cs.vt.edu,).
\end{sloppypar}

\paragraph{Class Presentations.}

In the fourth and fifth weeks,
individual students will lead the discussion on various papers,
symbolic computation systems,
or issues related to symbolic computation.
The instructor will make available a number of papers that
you may wish to select from.
You may also wish to look at resources available in the library,
such as the \emph{Journal of Symbolic Computation\/},
\emph{SIGSAM News\/},
and various symbolic (or algebraic) computation proceedings;
see VTLS for these.

The library provides an online service called \verb,firstsearch,
that makes available a number of useful databases.
From UNIX,
the following command
\begin{verbatim}
telnet nebula.lib.vt.edu 2988
\end{verbatim}
will get you to the \verb,firstsearch, service.
A telnet from other computers on the internet should also work.
Try the INSPEC database for journal and conference papers,
the BOOKSINPRINT database for books,
and the DISS database for dissertation abstracts.
Of course,
there are many resources on the Web;
pointers to a few of these will be added to the class web pages
from time to time.

\paragraph{Scribes.}

In lieu of everyone taking notes,
there will be two scribes appointed to take notes
for each class.
The two scribes will work together to write up the notes
in a coherent fashion in \LaTeX.
A \LaTeX\ template for scribe notes can be found on the class web pages.
A list of scribe assignments will be distributed May 21.
Craig Struble has agreed to be scribe on May 20.
Scribe notes are due two days (not counting weekends) after the class.
The \LaTeX\ source, \verb,bib, file,
and any other supporting files
should be emailed to \verb,cs6104@ei.cs.vt.edu,
by one of the two scribes.

\paragraph{Class Project.}

Every student will select a research topic for a class project.
The instructor must agree that the topic is appropriate,
but almost anything related to symbolic computation can be considered.
A list of suggested topics will be placed on the class web pages
the first week.
A student may work on the project alone, or in a team of two or three students.
A more extensive project is expected of a team
than of an individual,
but the level of work in any case need not be great.

The student's paper presentation(s) may or may not be related
to the topic.
Each student or team presents the results of his, her, or its project
the last week of the term.
A 2-page overview of the project,
identifying the topic and the team members,
is to be submitted June 3.
A final project report (perhaps 10 or 15 pages of \LaTeX)
is due June 27.

\section*{Electronic Access}

\paragraph{Email.}
Asynchronous announcements concerning class administration
will be sent by email.
Hence every student must submit an email address.

\paragraph{WWW Access.}
The course has a WWW home page at:
\begin{quote}
\verb,http://ei.cs.vt.edu/~cs6104,
\end{quote}
This will be a repository for handouts,
as well as a means of distributing a variety of information.
Scribe notes for a class will be posted here three days after the class.

\section*{Ethics}

This is a collaborative course
where everyone should be learning from the rest of the class.
Collaboration is encouraged on all assignments.
It is essential, however,
to \emph{acknowledge} the source
for everything you turn in or present,
whether that source is in the literature or is someone in the class.

\section*{Announcement}

If any student needs special accommodations because of a disability,
please contact the instructor during the first week of classes.

\newpage

\setlength{\parskip}{6pt plus 2pt minus 2pt}

\begin{center}
{\Large\bf SCHEDULE OF TOPICS}
\end{center}

\begin{center}
\begin{tabular}{cl}

\bf\hspace*{2pt} DATES\hspace*{2pt}&%
\bf TOPIC\\[10pt]

5/20 &\begin{topic}
Administration.
What is symbolic computation?
Feeling the elephant---connections to all sorts of things!
\end{topic}\\

5/21 &\begin{topic}
Introduction to \Mathematica,
noting salient features.
\end{topic}\\

5/22 &\begin{topic}
Hypothesizing an implementation for \Mathematica.
\end{topic}\\

5/23 &\begin{topic}
Models of computation;
purposes of computation.
Review of formal languages and automata begins.
\end{topic}\\

5/24 &\begin{topic}
Review of formal languages and automata concludes.
Issues of efficiency and decidability.
\end{topic}\\

5/28 &\begin{topic}
String-rewriting systems.
Basic concepts and examples.
\end{topic}\\

5/29 &\begin{topic}
Church-Rosser property.
Confluence.
Normal forms.
Knuth-Bendix completion.
\end{topic}\\

5/30 &\begin{topic}
Term-rewriting systems;
Definitions and examples.
Knuth-Bendix completion.
Undecidable properties of rewriting systems.
\end{topic}\\

5/31 &\begin{topic}
Introduction to the Larch Prover (LP).
Algebraic manipulations.
\end{topic}\\

6/3--6/5 &\begin{topic}
\Grobner bases.
Definitions.
Buchberger's algorithm to construct a \Grobner basis.\end{topic}\\

6/6 &\begin{topic}
Applications of \Grobner bases.
\end{topic}\\

6/7 &\begin{topic}
Implementation of symbolic computation systems.
Issues: What is the model?
Interpreted or compiled?
Dynamic memory allocation and garbage collection.
Efficiency.
Checkpointing and continuation.
\end{topic}\\

6/10--6/14 &\begin{topic}
Paper or system presentations (lead by students).
\end{topic}\\

6/17--6/21 &\begin{topic}
Paper or system presentations (lead by students).
\end{topic}\\

6/24--6/27 &\begin{topic}
Project presentations.
Projects are due on June 27 by 5:00 PM.
\end{topic}\\

\end{tabular}
\end{center}

\end{document}
