\documentclass[UTF8,12pt]{book}
\title{CS Review}
\author{Sal Elder}
\date{Last updated 22 October 2021}

\begin{document}
\maketitle
\frontmatter
\tableofcontents
\mainmatter
\chapter{Introduction}
%\section{Who is this for?}
I minored in computer science as an undergraduate, and got a pretty good education in it. But after four years, it was time for a review. I wrote this mainly for my own benefit, but it may be useful to anyone who learned about data structures and algorithms years ago and wants to refresh their memory about the finer points.

For example, these notes don't review basic Java syntax or simple examples of recursion, because I'm not at risk of forgetting those.

I do review, for example:
\begin{itemize}\item the runtime of Dijkstra's algorithm
	\item dynamic programming
	\item the difference between virtual functions in C++ and Java\end{itemize}because those are easy to forget even if you vaguely remember them.
\chapter{Object-oriented programming}
\section{Abstract classes and interfaces}
An abstract class is one which cannot be instantiated, either because it contains or inherits abstract methods, or because it has been declared abstract. An abstract method is one with a signature but not an implementation (i.e. function definition). ``Concrete'' just means ``not abstract.''

In Java, classes and methods may be declared \texttt{abstract}. Abstract classes may contain any number of concrete and abstract methods, but if a class contains one or more abstract methods then the class must be declared \texttt{abstract}. You can also define an \texttt{interface}, which is like an abstract class. Usually, interfaces only contain abstract methods and do not contain any fields.\footnote{In newer versions of Java, fields and concrete methods are allowed with some special restrictions.} In an interface, methods are abstract by default.

In C++, abstract methods must be declared \texttt{virtual}. This also implies that the class is abstract, but you don't need to declare the class abstract. Unlike Java, C++ doesn't have interfaces. There is also no \texttt{abstract} keyword.

\section{Multiple inheritance}
In Java, a class may \texttt{extend} only one class, but it can \texttt{implement} any number of interfaces. An interface may \texttt{extend} any number of other interfaces.

In C++, you can extend any number of classes.

\section{Virtual functions}
Say \texttt{Dog} is a subclass of \texttt{Animal}, and both class definitions include an implementation of the function \texttt{noise}. If you have \texttt{Dog d = new Dog();}, then clearly \texttt{d.noise()} should use the definition in \texttt{Dog} and not the definition in \texttt{Animal}, since the reference \texttt{d} and the object stored in it both have type \texttt{Dog}.

But if instead we have \texttt{Animal a = new Dog()}, then what does \texttt{a.noise()} evaluate to? Should it use the definition in \texttt{Animal}, since the reference \texttt{a} has type \texttt{Animal}, or should it use the definition in \texttt{Dog}, since the object referenced by \texttt{a} is in fact a \texttt{Dog}?

If the function is ``virtual,'' then it will use the definition in the type of the \emph{object} (\texttt{Dog}). If the function is not virtual, it will use the definition in the type of the \emph{reference} (\texttt{Animal}).

Abstract methods are always virtual, since there is only one definition anyway. Virtual methods may or may not be abstract.

In Java, all methods are virtual by default; there is no language keyword for it.

In C++, functions are not virtual by default, but they may be declared \texttt{virtual} in the base class. As mentioned above, a function declared \texttt{virtual} may or may not be abstract; i.e., it may or may not have an implementation.

\chapter{Data structures}
\section{Graphs}
\section{Hash tables}
\section{Heaps}

\chapter{Algorithms}
This chapter mostly follows the book ``Algorithm Design'' by Kleinberg and Tardos. (\'Eva Tardos was my professor in CS 4820 at Cornell.)
\section{Greedy}
\subsection{Dijkstra}
\section{Divide and conquer}
\subsection{Quicksort}
\section{Dynamic programming}
\subsection{Bellman-Ford}
\subsection{Knapsack problem}
\section{Max-flow}
\section{NP-completeness}


\end{document}
