\documentclass[11pt]{article}

\renewcommand{\today}{January 17, 2000}

\usepackage{fullpage}
\usepackage{fancyhdr}

\lhead{Algorithms}
\chead{}
\rhead{\today}
\lfoot{}
\cfoot{\thepage}
\rfoot{}

\pagestyle{fancy}

\parindent0em

\begin{document}

\begin{center}
  \large\textbf{Literature Notes on Homeworks and the Takehome Exam}
\end{center}

\subsection*{Homework 1}

\begin{itemize}
\item[1:] \textbf{Orientability} 
  
  The notation of $c$-orientability is very closely related to the
  notion of bounded arboricity, and the definitions are basically
  identical. The papers~\cite{AMZ} and \cite{BF} considers the
  implicit representation of graphs of bounded arboricity,
  where~\cite{AMZ} considers the problem for static graphs
  and~\cite{BF} considers the dynamic version of the problem where
  edges can be inserted and deleted.
\item[2:] \textbf{Array initialization}
  
  Section~III.8.1 of~\cite{M} contains a description of how a bitvector can
  be intitialized in worst case constant time.
\item[3:] \textbf{Sink}

  Exercise 23.1-6 in~\cite{CLR}. 
\item[4:] \textbf{Scorpion}
  
  Exercise~3 of homework~2 in~\cite{K}, from which also the following
  paragraph is taken.
  
  ``This is a counterexample to an earlier version of the famous
  \emph{Anderaa-Rosenberg conjecture}, which stated that any
  nontrivial graph property that is invariant under graph isomorphism
  requires $\Omega(n^2)$ probes of the adjacency matrix to test.
  Anderaa disproved this version in 1975 using a different
  counterexample (see~\cite{RV}), but conjectured that it held for
  \emph{monotone} properties (those that cannot change from false to
  true when edges are deleted). This was later verified by Rivest and
  Vuillemin~\cite{RV}.''
\end{itemize}

\subsection*{Homework 2}

\begin{itemize}
\item[\bf 1:] \textbf{Extendible Arrays}
  
  The array doubling idea is folklore. A generalization of this idea
  has been described by Overmars in~\cite{O} for the design of dynamic
  data structures.
\item[\bf 2:] \textbf{Binomial Heaps}
    
  A proof that binomial heaps support merging in amortized constant
  time was given in~\cite{KL}.
\item[\bf 3:] \textbf{Dijkstra's Algorithm}

  Folklore.
\item[\bf 4:] \textbf{Prim's Algorithm}
  
  Exercise 2 of homework~4 in~\cite{K}.  Prim's algorithm for
  computing a minimum spanning tree is, \textit{e.g.}, described
  in Section~24.2 of~\cite{CLR}.
\item[\bf 5:] \textbf{The Stable Marriage Problem}
  
  Exercise~1 of homework 6 in~\cite{K}.  Gale and Shapley were the first
  to investigate the stable marriage problem and gave an $O(n^2)$ solution
  in~\cite{GS}.
\end{itemize}

\subsection*{Homework 3} 

\begin{itemize}
\item[\bf 1:] \textbf{Minimum Spanning Trees}
  
  A linear time algorithm for finding a minimum spanning tree for
  planar graph was first given in~\cite{CT}. The $O(m\log^* n)$ time
  algorithm for finding a minimum spanning tree in a general graph was
  described in~\cite{FT}---the paper introducing Fibonacci heaps.  The
  current best dertministic minimum spanning tree algorithms use time
  $O(m\alpha(m,n))$, where $\alpha$ is an inverse of Ackerman's
  function~\cite{C,P}. A randomized linear time algorithm has been given
  in~\cite{KKT}.
\item[\bf 2:] \textbf{Augmenting Paths of Maximum Bottleneck Capacity}

  Exercise 1(b) of homework~5 in~\cite{K}.
\item[\bf 3:] \textbf{Ghostbusters}
  
  Problem 35-4 in~\cite{CLR}.  The ghostbusters problem can be solved
  in time $O(n\log n)$ by a divide-and-conquer algorithm, by applying the
  Ham-Sandwich Theorem and using a linear time algorithm for finding
  ham-sandwich cuts from~\cite{LMS}.
\item[\bf 4:] \textbf{Self Adjusting Trees}
  
  The class of self-adjusting trees considered in the exercise are
  often denoted \emph{splay-trees}, and were described in~\cite{ST}.
\end{itemize}

\subsection*{Homework 4}

\begin{itemize}
\item[\bf 1:] \textbf{Disk intersection}
  
  Exercise 35.2-6 in~\cite{CLR}.
\item[\bf 2:] \textbf{Edit distance}
  
  Computing the edit distance of two strings is one of the classical
  applications of dynamic programming. Hirshberg developed in~\cite{H}
  a general technique that, among others, allows the computation of
  the edit sequence in linear space.
\item[\bf 3:] \textbf{Minimal perfect hash functions}
  
  An asymptotic space optimal perfect hash function implementation was
  first described in~\cite{SS}. The exercise follows the basic
  approach of~\cite{SS}.
\end{itemize}

\subsection*{Takehome Final Exam}
  
The takehome exam covers results from three papers.  The application
of level linked $(a,b)$--trees for finger searches was given
in~\cite{HM}. The use of efficient merging of search trees for finding
regularities in strings was explored in~\cite{BLPS}, where the
regularities found are \emph{pairs with bounded gap} which are an
generalization of tandem repeats. The approach of extracting all
tandem repeats from the set of all branching tandem repeats was taken
in~\cite{SG}.  The algorithm in \cite{SG} for computing all tandem
repeats is simpler than the approach taken in the exercise, since
\cite{SG} does not generate the leaf-lists explicitly but only applies
two depth first traversals of the suffix tree.

\begin{thebibliography}{00}
\parskip0pt
\small
\bibitem{AMZ} 
  Srinivasa~R. Arikati, Anil Maheshwari, and Christos~D. Zaroliagis.
  \newblock Efficient computation of implicit representations of sparse graphs.
  \newblock \emph{Discrete Applied Mathematics}, 78:1--16, 1997.
\bibitem{BF}
  Gerth St{\o}lting Brodal and Rolf Fagerberg. 
  \newblock Dynamic Representations of Sparse Graphs.                              
  \newblock In \emph{Proc. 6th International Workshop on Algorithms and Data
    Structures}, volume 1663 of \emph{Lecture Notes in Computer Science}, 
  342--351.  Springer Verlag, Berlin, 1999.
\bibitem{BLPS}
  G.~S. Brodal, R.~B. Lyngs\o{}, C.~N.~S. Pedersen, and J.~Stoye.
  \newblock Finding maximal pairs with bounded gap.
  \newblock In \emph{Proceedings of the 10th Annual Symposium on Combinatorial
    Pattern Matching (CPM)}, volume 1645 of \emph{Lecture Notes in Computer
    Science}, pages 134--149, 1999.
\bibitem{C}
  B. Chazelle. 
  \newblock A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. 
  \newblock NECI Technical Report 99-099, July 1999.
\bibitem{CT}
  D. Cheriton and R. E. Tarjan.
  \newblock Finding minimum spanning trees.
  \newblock \emph{SIAM Journal of Computing}, 5:724-742, 1976.
\bibitem{CLR} 
  Thomas~H. Cormen, Charles~E. Leiserson, and Ronald~L. Rivest.  
  \newblock \emph{Introduction to Algorithms}.  
  \newblock MIT Press, 1990.
\bibitem{FT}
  Michael~L. Fredman and Robert~Endre Tarjan.
  \newblock Fibonacci heaps and their uses in improved network optimization algorithms.  
  \newblock \emph{Journal of the ACM}, 34(3):596--615, 1987.
\bibitem{GS}
  D. Gale and L. S. Shapley.
  \newblock College admissions and the stability of marriage.
  \newblock \emph{American Mathematical Monthly}, 69:9-14, 1962.
\bibitem{HM}
  Scott Huddleston and Kurt Mehlhorn.
  \newblock A new data structure for representing sorted lists.
  \newblock \emph{Acta Informatica}, 17:157--184, 1982.
\bibitem{KL}
  C. M. Khoong and H. W. Leong. 
  \newblock Double-ended binomial queues.
  \newblock In \emph{Algorithms and Computation}, volume 762 of 
  \emph{Lecture Notes in Computer Science},
  128--137.   Springer Verlag, Berlin, 1993.
\bibitem{H}
  D. S. Hirschberg.  
  \newblock Algorithms for the longest common subsequence problem.  
  \newblock \emph{Journal of the ACM}, 24:664-675, 1977.
\bibitem{KKT}
  D. R. Karger, P. N. Klein, and R. E. Tarjan. 
  \newblock A randomized linear-time algorithm to find minimum spanning trees. 
  \newblock \emph{Journal of the ACM}, 42:321-328, 1995.
\bibitem{K} 
  Dexter C. Kozen.
  \newblock \emph{The Design and Analysis of Algorithms}.
  \newblock Springer-Verlag, 1992.
\bibitem{LMS}
  C.-Y. Lo, J. Matou{\v s}ek, and W. L. Steiger.
  \newblock Algorithms for ham-sandwich cuts.
  \newblock \emph{Discrete Computational Geometry}, 11:433--452, 1994.
\bibitem{M}
  Kurt Mehlhorn.  
  \newblock \emph{Data Structures and Algorithms 1: Sorting and Searching}.  
  \newblock Springer {V}erlag, Berlin, 1984.
\bibitem{O}
  Mark~H. Overmars.  
  \newblock \emph{The Design of Dynamic Data Structures}, 
  volume 156 of \emph{Lecture Notes in Computer Science}.  
  \newblock Springer {V}erlag, Berlin, 1983.
\bibitem{P}
  S. Pettie.
  \newblock Finding Minimum Spanning Trees in $O(m\alpha(m,n))$ Time.
  \newblock UTCS Technical Report TR99-23.
\bibitem{RV}
  R. L. Rivest and J. Vuillemin.
  \newblock On recognizing graph properties from adjacency matrices.
  \newblock \emph{Theoretical Computer Science}, 3:371-384, 1976/77.
\bibitem{SS}  
  J.~P. Schmidt and A.~Siegel.
  \newblock The spatial complexity of oblivious $k$-probe hash functions.
  \newblock \emph{SIAM Journal on Computing}, 19(5):775--786, 1990.
\bibitem{ST}
  Daniel~Dominic Sleator and Robert~Endre Tarjan.
  \newblock Self-adjusting binary search trees.  
  \newblock \emph{Journal of the ACM}, 32(3):652--686, 1985.
\bibitem{SG}
  J.~Stoye and D.~Gusfield.
  \newblock Simple and flexible detection of contiguous repeats using a suffix
  tree.
  \newblock In \emph{Proceedings of the 9th Annual Symposium on Combinatorial
    Pattern Matching (CPM)}, volume 1448 of \emph{Lecture Notes in Computer
    Science}, pages 140--152, 1998.
\end{thebibliography}
  
\end{document}
