Notes for the 2011-9-23 CSI 3334 lecture

csi3334-2011-09-23.tex

%
% DO NOT CHANGE THIS TEMPLATE!
%
% To allow combining the lecture notes from different students in a
% simple way everybody must use the same header.
%
% If you think the template lack a package, then contact the lecturer,
% and we will probably extend the template with your favorite package.
%

\documentclass[11pt,letterpaper,twoside]{article}
\usepackage{alg}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{amssymb}
\usepackage{amsmath}

\begin{document}
\pagestyle{myheadings}
\thispagestyle{plain}

\newcommand{\lecture}[5] { %
\newcommand{\fdate}{#1}%
\newcommand{\fnumber}{#2}%
\newcommand{\fheadline}{#3}%
\newcommand{\flecturer}{#4}%
\newcommand{\fauthor}{#5}%
\markboth{CSI 3334 -- Fall 2011}{\fheadline}%
\hrule
\begin{center}
\large \bf 
CSI 3334, Data Structures

\vspace*{2mm}
\Large \bf 
Lecture \fnumber: \fheadline
\end{center}
\small
\noindent Date: \fdate
\\
Author(s): \fauthor
\\
Lecturer: \flecturer
\\
\hrule
\vspace{5mm}
}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}

% \lecture{date}{lecture number}{lecture headline}{lecturer}{author}
%
%
%

%%%%% Edit after this row. The above should not need editing. %%%%%

%%%%% Define your own stuff here. %%%%%

\newcommand{\zed}{\mathbb{Z}}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\GF}[1]{\mathrm{GF}_{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\lecture{2011-08-31}{11}{Programming Assignment 2 \& Trees}{Fredrik Niemel\"a}{Adam Cammack, Michael Webbon}

\noindent
What are we supposed to turn in? What is a tree?

\section{Programming Assignment 1}

This assignment was designed primarily to test your ability to use the site. Some students did not email the right address in time; their assignments will be due on the day that they get their logins, within reason.

\section{Programming Assignment 2}

Due: Monday, 3 October 2011

Implement Vector, Stack, and Queue classes. Code must be indented and use a convention of your choice. Code should be properly modularized in files and should not leak memory.

\noindent
All containers will store \texttt{unsigned\_int}s. For all the containers the size is the maximum and guaranteed size of the instance. Size of zero is allowed and containers will not resize. Use \texttt{const} where appropriate. The expected interface is as follows:

\begin{description}
\item[Vector]

\begin{itemize}
\item \texttt{explicit Vector(size\_t)}
\item copy constructor
\item assignment (=) operator
\item index operator (\texttt{[]}), two versions: one \texttt{const} (for accessing) and one reference (for assignment). May throw \texttt{std::out\_of\_range} where it makes sense.
\end{itemize}

\end{description}

\begin{description}
\item[Stack]

\begin{itemize}
\item \texttt{explicit Vector(size\_t)}
\item copy constructor
\item assignment (=) operator
\item \texttt{void push()}, throws \texttt{std::length\_error} on overflow
\item \texttt{unsigned int pop()}, throws \texttt{std::length\_error} on underflow
\item shovel operators (see below)
\end{itemize}

\end{description}

\begin{description}
\item[Queue]

\begin{itemize}
\item \texttt{explicit Vector(size\_t)}
\item copy constructor
\item assignment (=) operator
\item \texttt{void push()}, throws \texttt{std::length\_error} on overflow
\item \texttt{unsigned int pop()}, throws \texttt{std::length\_error} on underflow
\item shovel operators (see below)
\end{itemize}

\item[Shovel Operators]

\begin{itemize}
\item \texttt{ostream $\ll$ cont} pops off the top element and prints it
\item \texttt{istream $\gg$ cont} pushes an element on to the container
\item \texttt{cont $\ll$ uint} pushes an element on to the container
\item \texttt{cont $\gg$ uint} pops off the top element
\end{itemize}

\end{description}

\section{Trees}

\begin{description}
\item[Graph] $G = \{V, E\}$ where $E\subset \{V \times V\}$
\item[Tree] Graph where every pair of nodes is connected by exactly one path
\item[Rooted Tree] What most people mean when say 'tree'. Has a root node. Nodes have child nodes.
\item[Forest] Graph where every pair of nodes is connected by at most one path (a set of trees)
\end{description}

\end{document}