\documentclass[12pt]{article}

\usepackage[T1]{fontenc} 
\usepackage{fullpage,amsmath,amsfonts}

\begin{document}

\title{Algorithms and Data Structures}
\author{Summer Semester 2022}
\date{Topics for the Mock Final Exam, July 12, 2022}
\maketitle

\begin{enumerate}
\item Basics of Big-Oh and Big-Omega notation: Definition (see, e.g.,
GTG Exercise R-3.8 for a precise understanding), relative ordering of
growth rates (GTG Exercise R-3.8), spotting characterization of
running time from simple pieces of code (GTG Exercises R-3.23--27).
Many of the other R-Exercises from Chapter~3 are also worth looking
at.

\item Recursion: The four basic examples from GTG Section 4.1 are
worth reviewing in depth, including the analysis of run-time later in
the chapter.  To see further good examples for recursion, jump ahead
to the recursive definition of a tree, the recursive formulation of
tree traversal problems and the recursive computation of depth and
height in trees, all in Chapter~8.

\item Turning recursive algorithms into non-recursive ones (GTG
Section 4.6, Exercise C-4.9 -- can you do it both ways?), or vice
versa.

\item Dynamic arrays: implementation and run-time analysis, in
particular amortization (see, e.g., GTG Exercise R-5.5), use of index
arrays (this is a very wide field, but see, for example Exercise R-5.7
for an interesting twist).

\item Stacks, queues, and deques: know the basic operations on these
abstract data types (see most of the R-Exercises from Chapter~6; can
you implement a stack or a queue using the Priority Queue as a basis?
-- see Exercises C-9.26, C-9.27, and following).

\item Linked Lists: know the basis operations on singly and doubly
linked lists (see, e.g., Exercises R-7.1, R-7.3, R-7.5), running time
comparison of linked lists vs.\ arrays (Section 7.7)

\item Trees: major part of possible exam topics, in particular
Sections 8.1, 8.2, 8.4.1--3.  The chapter exercises contain a lot of
good practice material, e.g. Exercise R-8.2, R-8.5, R-8.7, R-8.8,
R-8.13, R-8.20.

\item Priority queues: definition of the abstract data type, priority
queue implementations via an unsorted list, a sorted list, or a heap.
Performance analysis of the heap data structure, using priority queues
for sorting, in particular the heap sort?  Practice problems are
plenty in the Chapter~9 exercises, in particular R-9.2--12, R-9.18--20.


\end{enumerate}

General advice:
\begin{itemize}
\item Reading code fragments from the book is always a good idea.
Translation from code into a more schematic description, or vice
versa, is a possible exam problem.  The general emphasis in this class
is not on the fine details of providing an object oriented API in
Python, but rather on the core structures of the algorithms.

\item Review the coding exercises done in the tutorials.  There might
be questions about finding errors in code, or on any of the
algorithmic patterns covered.

\end{itemize}


\end{document}
