% This is a LaTex file.
% Homework for the course "Discrete Modeling",
% Winter quarter, 1998, Anne Greenbaum.
% A latex format for making homework assignments.
\documentstyle[12pt]{article}
% The page format, somewhat wider and taller page than in art12.sty.
\topmargin -0.1in \headsep 0in \textheight 8.9in \footskip 0.6in
\oddsidemargin 0in \evensidemargin 0in \textwidth 6.5in
\begin{document}
% Definitions of commonly used symbols.
% The title and header.
\noindent
{\scriptsize Discrete Modeling, Winter 1998} \hfill
\begin{center}
\large
Review for Final (Wed., Mar. 18, 2:30--4:20 pm)
\normalsize
\end{center}
\vspace{.3in}
\noindent
YOU MAY BRING IN ONE $8 \frac{1}{2}$ by $11$ SHEET OF PAPER WITH NOTES.
\vspace{.2in}
\noindent
You will be expected to know all material from before the midterm,
but the questions will emphasize material covered {\em after} the midterm.
The final will cover:
\begin{itemize}
\item
Secs. 3.6 and 3.7.
\item
Ch. 11, {\em except} Secs. 11.4.5, 11.4.6, and 11.6.4.
\item
Ch. 12, {\em except} Secs. 12.2.2 and 12.6.
\item
Ch. 13, {\em except} Secs. 13.3.6 and 13.4.2.
\end{itemize}
% The questions!
\vspace{.1in}
\noindent
To review:
\begin{enumerate}
\item
Make sure you can do all of the assigned homework exercises.
\item
For extra practice, choose additional related problems in Secs. 3.6--3.7
and in Chs. 11--13. Many have answers in the back.
\item
Algorithms that you should know include the following:
\begin{itemize}
\item
Binary search.
\item
Bubble sort and quick sort.
\item
Depth-first search for connectedness and finding a strongly connected
orientation.
\item
Algorithm for finding an Eulerian closed chain.
\item
Algorithm for finding a maximum matching.
\item
Kruskal's and Prim's minimum spanning tree algorithms.
\item
Dijkstra's shortest path algorithm.
\item
Maximum flow algorithm.
\end{itemize}
\end{enumerate}
\end{document}