% T I T L E   P A G E
% -------------------
% Last updated June 14, 2017, by Stephen Carr, IST-Client Services
% The title page is counted as page `i' but we need to suppress the
% page number. Also, we don't want any headers or footers.
\pagestyle{empty}
\pagenumbering{roman}



% The contents of the title page are specified in the "titlepage"
% environment.
\begin{titlepage}
        \begin{center}
        \vspace*{1.0cm}

        \Huge
        {\bf Efficient Data Structures for Partial Orders, Range Modes, and Graph Cuts }

        \vspace*{1.0cm}

        \normalsize
        by \\

        \vspace*{1.0cm}

        \Large
        Bryce Sandlund \\

        \vspace*{3.0cm}

        \normalsize
        A thesis presented to the University of Waterloo in fulfillment of the thesis requirement
        for the degree of Doctor of Philosophy in Computer Science
        %A thesis \\
        %presented to the University of Waterloo \\ 
        %in fulfillment of the \\
        %thesis requirement for the degree of \\
        %Doctor of Philosophy \\
        %in \\
        %Zoology \\

        \vspace*{2.0cm}

        Waterloo, Ontario, Canada, 2021 \\

        \vspace*{1.0cm}

        \copyright\ Bryce Sandlund 2021 \\
        \end{center}
\end{titlepage}

% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii'
\pagestyle{plain}
\setcounter{page}{2}

\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed.
% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary.

 
% E X A M I N I N G   C O M M I T T E E (Required for Ph.D. theses only)
% Remove or comment out the lines below to remove this page
\begin{center}\textbf{Examining Committee Membership}\end{center}
  \noindent
The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote.
  \bigskip
  
  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
External Examiner: \>  Pat Morin \\ 
\> Professor \\
\> Carleton University \\
\end{tabbing} 
  \bigskip
  
  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Supervisor(s): \> J. Ian Munro \\
\> University Professor and Canada Research Chair in Algorithm Design\\
\> Cheriton School of Computer Science, University of Waterloo \\
\end{tabbing}
  \bigskip
  
  \noindent
  \begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Internal Member: \> Lap Chi Lau \\
\> Associate Professor \\
\> Cheriton School of Computer Science, University of Waterloo \\
\end{tabbing}
  \bigskip
  
  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Internal-External Member: \> Joseph Cheriyan \\
\> Professor \\
\> University of Waterloo \\
\end{tabbing}
  \bigskip
  
  \noindent
\begin{tabbing}
Internal-External Member: \=  \kill % using longest text to define tab length
Other Member(s): \> Trevor Brown \\
\> Assistant Professor \\
\> Cheriton School of Computer Science, University of Waterloo \\
\end{tabbing}

\cleardoublepage

% D E C L A R A T I O N   P A G E
% -------------------------------
  % The following is a sample Delaration Page as provided by the GSO
  % December 13th, 2006.  It is designed for an electronic thesis.
  \noindent
This thesis consists of material all of which I authored or co-authored: see Statement of Contributions included in the thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.

  \bigskip
  
  \noindent
I understand that my thesis may be made electronically available to the public.

\cleardoublepage

% A B S T R A C T
% ---------------

%\begin{center}\textbf{Abstract}\end{center}
\section*{Abstract}

This thesis considers the study of data structures from the perspective of the theoretician, with a focus on simplicity and practicality. We consider both the time complexity as well as space usage of proposed solutions. Topics discussed fall in three main categories: partial order representation, range modes, and graph cuts.

We consider two problems in partial order representation. The first is a data structure to represent a lattice. A lattice is a partial order where the set of elements larger than any two elements $x$ and $y$ are all larger than an element $z$, known as the join of $x$ and $y$; a similar condition holds for elements smaller than any two elements. Our data structure is the first correct solution that can simultaneously compute joins and the inverse meet operation in sublinear time while also using subquadratic space. %We give a data structure to represent lattices that computes order relations in constant time, meets and joins in $O(n^{3/4})$ time, and utilizes $O(n^{3/2})$ space.
The second is a data structure to support queries on a dynamic set of one-dimensional ordered data; that is, essentially any operation computable on a binary search tree. We develop a data structure that is able to interpolate between binary search trees and efficient priority queues, offering more-efficient insertion times than the former when query distribution is non-uniform.

We also consider static and dynamic exact and approximate range mode. Given one-dimensional data, the range mode problem is to compute the mode of a subinterval of the data. In the dynamic range mode problem, insertions and deletions are permitted. For the approximate problem, the element returned is to have frequency no less than a factor $(1+\epsilon)$ of the true mode, for some $\epsilon > 0$. Our results include a linear-space dynamic exact range mode data structure that simultaneously improves on best previous operation complexity and an exact dynamic range mode data structure that breaks the $\Theta(n^{2/3})$ time per operation barrier. For approximate range mode, we develop a static succinct data structure offering a logarithmic-factor space improvement and give the first dynamic approximate range mode data structure. We also consider approximate range selection.

The final category discussed is graph and dynamic graph algorithms. We develop an optimal \emph{offline} data structure for dynamic $2-$ and $3-$ edge and vertex connectivity. Here, the data structure is given the entire sequence of operations in advance, and the dynamic operations are edge insertion and removal. Finally, we give a simplification of Karger's near-linear time minimum cut algorithm, utilizing heavy-light decomposition and iteration in place of dynamic programming in the subroutine to find a minimum cut of a graph $G$ that cuts at most two edges of a spanning tree $T$ of $G$.


\cleardoublepage

% A C K N O W L E D G E M E N T S
% -------------------------------

\section*{Acknowledgments}
%\begin{center}\textbf{Acknowledgements}\end{center}

This thesis marks the culmination of seven years of graduate school. I would not be where I am today without the help and support of so many. First and foremost, I'd like to thank my advisor, Ian Munro. Ian was always enthusiastic to talk algorithms and through his large group at Waterloo, facilitated numerous prolific collaborations. Thank you for showing me the area of data structure design, with all of its exciting puzzles and balancing acts. I would also like to thank Richard Peng. Despite no formal relationship, Richard was an instrumental mentor to me, including me on several research projects and further introducing me to some extremely bright young collaborators. A third mentor I wish to express my appreciation towards is Eric Bach. Eric showed me how to be a successful researcher, guiding me during my tenure at Wisconsin-Madison. He also supported me in my decision to switch my research focus to data structures, connecting me with Ian Munro at Waterloo.

I am very grateful for all of the coauthors I have had the pleasure of collaborating with on the topics of this thesis.
%I am also grateful for my highly-competent coauthors.
%I would also like to thank my coauthors. 
Corey, thank you for welcoming me into the lattice research project. I thoroughly enjoyed our brainstorming sessions and the two eureka moments, when we figured out how to efficiently compute order-testing and meets/joins. Sebastian, thank you for collaborating with me on lazy search trees. It took countless tries, but we were able to come up with a meaningful solution that generalizes priority queues with binary search trees. Hicham, Meng, and Yakov, thank you for the many fruitful whiteboard sessions, distant email and hangout chats, and the two papers that came out of our range mode project. Antonio and Nalin, thank you for working with me on minimum cuts and Yinzhan, I am very grateful you included me on faster dynamic range mode. I am extremely fortunate to have met you three through the vibrant competitive programming community, two of you via Richard Peng. Lastly, Danny, thank you for being an inspirational example in the area of data structure design. I have thoroughly enjoyed all our conversations and hope the future holds more of them.

This thesis would not be possible if not for a committee that has volunteered their precious time to give their thoughts and academic critiques of my research. Thank you Lap Chi and Trevor Brown, for your volunteering on this thesis and for your support at Waterloo. Prof. Joseph Cheriyan, thank you for volunteering on this thesis committee despite residing in a different academic department. Finally, thank you Prof. Pat Morin; despite having no interactions with me personally, you have volunteered to share your expertise regarding this document.

My interest in pursuing a research path was kindled due to early encounters with several inspiring individuals. Kerrick, I recall meeting you on the bus to our first ACM International Collegiate Programming Contest; you were programming mergesort in assembly. I have been very impressed with your intellect and our interactions encouraged me to further pursue mathematics and contests, which has led to this thesis. Simanta Mitra, thank you for all your support in ICPC and for encouraging me to pursue a PhD. Steve Butler, I would like to thank you for allowing me to join your combinatorics class late in the term at Iowa State. You introduced me to a beautiful area of mathematics that shaped my research trajectory and helped me publish my first paper. Hridesh Rajan, Steve Kautz, and Jim Lathrop, thank you for the discussions that led me to pursue a PhD. 
Sariel Har-Peled, thank you for conversing with a curious undergraduate to whom you had no formal relation. Lastly, I'd like to thank Bernhard Haeupler. In our brief experience together, you were an inspirational theoretical computer scientist to a young graduate student, but also a powerful role model in the way you live your life outside of research.

There are many more individuals that helped me succeed in my graduate school experience. Chung Webster, thank you for supporting me in my decision to pursue a PhD. Dieter van Melkebeek and Shuchi Chawla, thank you for your support at Wisconsin-Madison. Andrew Morgan, Menghui Wang, Rex Fernando, Ben Miller, Dimitris Paparas, Jinman Zhao, Yunfeng Li, Krittisak Chaiyakul, Ingkarat Rak-amnouykit, and Songwong Tasneeyapant, thank you for the many conversations and experiences we shared at Wisconsin-Madison. Gautam Kamath and Jochen Koenemann, thank you for the insightful conversations and for your support at Waterloo. Kevin Wu, Lingyi Zhang, and Azin Nazari, thank you for the many research discussions and also for the much-needed dinner breaks at some of Waterloo's better restaurants. Joachim von zur Gathen, thank you for writing me a graduate admissions recommendation letter. Colin Zheng, thank you for the mentorship and advice during my summer at Google.

Lastly, I'd like to thank my friends and family who have made graduate school more tolerable. Brett, Mike, Ronak, Chris, Ross, Meaghan, Eric, Ainura, Cameron, Saraid, Dan, Erin, Danny, Pasha, Joey, Devon, Evan, Natasha, Jeremy, Ying, Saranya, Satyam, Ian, Ryan B, Paul, Graham, Sam, Jan, Akshay, Ryan H, Amit, Beatrix, Sierra, Nolan, Jaehyun, Andy, Jordyn, Adam, Matt, Nick, Mike, Chris, Steve, Tony, and Allen, thank you for all of the good times we shared together and in particular for keeping me sane with online poker and Age of Empires while under the many covid-19 lockdowns. Finally, thank you to my brothers Jacob and Caleb, my sister Jess, and my mom and dad, who have listened to my adventure into deeper mathematics for seven years, supporting me throughout my journey.
\cleardoublepage

% D E D I C A T I O N
% -------------------

\section*{Dedication}

This thesis is dedicated to immigrants. Wherever they may be from, wherever they may choose to go, may they be welcome.
\cleardoublepage

\section*{Statement of Contributions}
%\begin{center}\textbf{Previous Publications}\end{center}

This thesis is based on the following publications.

%\begin{itemize}
%	\item Chapter 2: \cite{Munro20} \bibentry{Munro20}
%	\item Chapter 3: (not yet on arxiv)
%	\item Chapter 4: \cite{ElZein18} \bibentry{ElZein18}
%	\item Chapter 5: \cite{Sandlund20} \bibentry{Sandlund20}
%	\item Chapter 6: \cite{ElZein19} \bibentry{ElZein19}
%	\item Chapter 7: \cite{Peng19} \bibentry{Peng19}
%	\item Chapter 8: \cite{Lovett20} \bibentry{Lovett20}
%\end{itemize}

\begin{itemize}
	\item[Chapter \ref{chapter-lattices}:] \cite{Munro20} \bibentry{Munro20}
	\item[Chapter \ref{chapter-lazysearchtrees}:] \cite{Sandlund20b} \bibentry{Sandlund20b}
	\item[Chapter \ref{chapter-dynamicmodespace}:] \cite{ElZein18} \bibentry{ElZein18}
	\item[Chapter \ref{chapter-dynamicmodetime}:] \cite{Sandlund20a} \bibentry{Sandlund20a}
	\item[Chapter \ref{chapter-succinctmode}:] \cite{ElZein19} \bibentry{ElZein19}
	\item[Chapter \ref{chapter-offlineconnectivity}:] \cite{Peng19} \bibentry{Peng19}
	\item[Chapter \ref{chapter-mincut}:] \cite{Lovett20} \bibentry{Lovett20}
\end{itemize}

\cleardoublepage

% T A B L E   O F   C O N T E N T S
% ---------------------------------
\renewcommand\contentsname{Table of Contents}
\tableofcontents
\cleardoublepage
\phantomsection    % allows hyperref to link to the correct page

% L I S T   O F   T A B L E S
% ---------------------------
%\addcontentsline{toc}{chapter}{List of Tables}
%\listoftables
%\cleardoublepage
%\phantomsection		% allows hyperref to link to the correct page

% L I S T   O F   F I G U R E S
% -----------------------------
\addcontentsline{toc}{chapter}{List of Figures}
\listoffigures
\cleardoublepage
\phantomsection		% allows hyperref to link to the correct page

% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package)
% -----------------------------
%\printglossaries
%\cleardoublepage
%\phantomsection		% allows hyperref to link to the correct page

% Change page numbering back to Arabic numerals
\pagenumbering{arabic}

