A historic TeX document from Donald Knuth's CS204 course (Autumn 1978).

knuth-cs204.tex

% Modern LaTeX compilation of Knuth's CS204 Problem Set (Autumn 1978)
% Original source: https://www.saildart.org/204.TEX[TEX,DEK]

\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{letterpaper, margin=1in}

% Recreate Knuth's custom commands for modern LaTeX
\newcommand{\problembegin}[3]{%
  \begin{flushright}CS204---Autumn 1978\end{flushright}
  \vskip3pt
  \noindent\textbf{Problem #1.} #2.\hfill(#3)
  \vskip 5pt\noindent
}

\newcommand{\xskip}{\hskip7pt plus3pt minus4pt}
\newcommand{\yskip}{\penalty-50\vskip3pt plus3pt minus2pt}
\newcommand{\bslash}{\textbackslash}
\newcommand{\cpile}[1]{\begin{array}{l}#1\end{array}}
\newcommand{\lpile}[1]{\begin{array}{l}#1\end{array}}
\newcommand{\leftset}{\{}
\newcommand{\rightset}{\}}
\newcommand{\relv}{\mid}
\newcommand{\biglp}{(}
\newcommand{\bigrp}{)}

\setlength{\parindent}{19pt}

\begin{document}

\problembegin{1}{The camel of Khow\={a}rizm}{warmup problem, due October 5}

Let $\phi = (1+\sqrt{5})/2=1.61803\,39887\,49894\,84820\ldots$ be the
``golden ratio.''

A legendary camel in the ancient Persian valley of Khow\={a}rizm used to walk
around and around on a circular road that was
exactly one parathanha in circumference.
Every time this camel would travel a distance of precisely $\phi$ parathanhæ,
it would deposit some beautiful dung that shone like gold. The golden dung
was, of course, bewitched; it was certain death to anyone who touched it
or disturbed it in any way. Thus, over the years a series of such deposits
continued to be built up along the road.

Everyone who passed that way noticed a strange thing---the golden cameldung
seemed to be almost equally spaced. One could practically use the heaps as
mileposts. In fact, at the time when there were $n$ deposits on the road,
the following condition was true (although only a few mathematicians knew it):
There was a point $x_n$ on the road such that if you started at $x_n$ you would
pass exactly one golden dung heap during the time it took to travel one $n$th
of a parathanha. Repeating this $n$ times until returning to $x_n$, you would
see only one heap per segment of your tour. The mathematicians of that time
called this the ``$n$-fold cyclic dung distribution property.''

The magic camel never left the road, and it continued to make its enchanted deposits
for many years. Every time $n$ would increase by one, the $n$-fold cyclic
dung distribution property remained valid. But one year, just as a new deposit
was about to be made, a mysterious cloud appeared and enveloped the poor beast;
and when the cloud moved away, the camel was gone. The spell was broken, and the
gold could now be freely taken.

One of the mathematicians had anticipated this, since he knew that the $n$-fold
cyclic dung distribution property would fail at the time of the next deposit.
This brilliant sorceror had made preparations for the fateful moment, and his
agents immediately pounced on the gold when the enchantment was lifted. He
became the richest man in the valley, so he gave up mathematics and was
assassinated two months later.

The problem is to determine $x_n$ for $n=1$, 2, $\ldots$; and to determine the
final value of $n$ when the camel vanished.

\newpage

\problembegin{2}{Bit fiddling and image processing}{due October 19}

In this problem we will be dealing with pictures represented on a discrete
raster. We have an $n\times n$ grid consisting of square ``pixels,''
each of
which is white or black. Using 0 to represent white and 1 to represent black,
we will be able to represent the picture compactly with 36 pixels per word
(on the AI Lab computer), and the computer's Boolean operations will facilitate
the manipulation of pictures. There are two parts to this problem: first to
``clean up'' a picture, and second to do edge-following that describes the
boundaries of the ``objects'' in a cleaned-up picture.

\yskip\noindent
\textbf{A.} \textsl{The cleaning-up phase} is intended to change stray black pixels to white
and vice versa, as well as to remove sharp turns of more than $90^\circ$ at the
edges of black areas.

For purposes of discussion, a picture $P$ will be regarded as the set of all
black pixels in some image, and the complementary set $P^-$ will be the set of
all white pixels. We define the \textsl{closure} $P^C$ of $P$ to be the smallest
picture containing $P$ such that every white pixel (i.e., every element of
$P^{C-}$) is part of a $3\times3$ square of white pixels. A picture is \textsl{
closed} if it is equal to its closure. The \textsl{interior} $P^O$ of $P$ is
defined to be the largest picture contained in $P$ such that every black pixel
is part of a $3\times3$ square of black pixels. A picture is \textsl{open} if it is
equal to its interior.

\medskip
\noindent\textbf{Problem:} Write a program that finds $P^{CO}$, given a $72\times72$ picture $P$.

\newpage

\problembegin{3}{Cubic spline drawing}{due November 2}

This problem arises in connection with drawing ``nice'' curves on a discrete
raster. We are given two cubic polynomials
$$\begin{aligned}
x(t) &= x_0+x_1t+x_2t^2+x_3t^3,\\
y(t) &= y_0+y_1t+y_2t^2+y_3t^3;
\end{aligned}$$
and we wish to plot the curve $(x(t), y(t))$ for $0\leq t\leq 1$. But we are allowed to plot only integer points,
making king moves.

Knuth's ``binary splitting'' method seems somewhat elegant at first glance, but
the curves it draws are sometimes too skinny-looking and they occasionally
contain undesirable glitches near points where $t$ is a simple binary fraction.
Even when $x(t)$ and $y(t)$ are linear, the results are often very strange.
So the purpose of this problem is to help Knuth design a better routine for the
real METAFONT system.

Find an efficient way to plot a given cubic spline curve $(x(t),y(t))$
for $0\leq t\leq 1$, assuming that $0\leq y'(t)\leq x'(t)$ for $0\leq t\leq 1$. Your algorithm
should decide as rapidly as possible whether or not each successive rightward move
should have slope 0 or 1.

\newpage

\problembegin{4}{A language for Gosper arithmetic}{due November 16}

The main purpose of this problem is not to design a computer program---instead,
we will try to design a good \textsl{programming language} of a new type (related
somewhat to the so-called ``data-flow'' languages being discussed nowadays
in connection with database systems).

Every real number $x$ can be represented in a unique way as
a continued fraction
$$x_0+\frac{1}{x_1+\frac{1}{x_2+\cdots}}$$
where $x_0$ is an integer and $x_1$, $x_2$, $\ldots$ are infinitely many
positive integers; or perhaps $x_k=\infty$ for some $k$, in which case $x_{k+1}$,
$x_{k+2}$, $\ldots$ do not exist. For convenience in notation, we write $x=
x_0+\bslash x_1,x_2,\ldots\bslash$. The $x_k$'s are called ``partial
quotients'' of $x$.

R. W. Gosper has developed a set of routines that do arithmetic directly on
the continued fraction representations of numbers. His routines have the neat
property that they produce one partial quotient at a time as coroutines.

Your goal is to design a suitable user programming language and illustrate how
you would solve the following two problems:

\medskip
\noindent(a) Calculate a root of any given cubic equation.

\noindent(b) Solve a system of $n$ simultaneous linear equations.

\newpage

\problembegin{5}{Kriegspiel endgame}{due December 5}

In this problem we are concerned with the game of chess where there is a white
king and white rook against a black king. An easy checkmate, you say; but there's
a twist: The white player does not know where the black king is.

The game starts with the white king and rook at their normal opening positions,
while the black king may be anywhere else (but not in check); White moves first.
Whenever White makes a move, he or she receives one of the following replies:

\begin{enumerate}
\item[a)] Checkmate, you win.
\item[b)] Stalemate, it's a draw.
\item[c)] That move of yours is illegal because it puts your king next
to mine; try again.
\item[d)] Your move put me in check, but it was not checkmate so I have
made my next move.
\item[e)] Your move did not put me in check, and I have made my next
move.
\end{enumerate}

It is possible for White to force checkmate in finitely many moves,
but the winning strategy is not easy to discover, so a good Black will usually
be able to escape.

Your problem is to design and program a Black strategy that plays 
``intelligently'';
in particular, your program should be able to survive at least 100 moves against
two different White programs supplied by the grader.

\end{document}