@string{brics = "{BRICS}"}
@string{daimi = "Department of Computer Science, University of Aarhus"}
@string{iesd = "Department of Mathematics and Computer Science, Aalborg University"}
@string{rs = "Research Series"}
@string{ns = "Notes Series"}
@string{ls = "Lecture Series"}
@string{ds = "Dissertation Series"}
@TechReport{BRICS-DS-97-3,
author = "Husfeldt, Thore",
title = "Dynamic Computation",
institution = brics,
year = 1997,
type = ds,
number = "DS-97-3",
address = daimi,
month = dec,
note = "PhD thesis. 90~pp",
abstract = "Chapter~1 contains a brief introduction and motivation of
dynamic computations, and illustrates the main
computational models used throughout the thesis, the
random access machine and the {\em cell probe model}
introduced by Fredman.\bibpar
Chapter~2 paves the road to proving lower bounds for
several dynamic problems. In particular, the chapter
identifies a number of key problems which are hard for
dynamic computations, and to which many other dynamic
problems can be reduced. The main contribution of this
chapter can be summarised in two results. The first shows
that the signed prefix sum problem, which has already
been heavily exploited for proving lower bounds on
dynamic algorithms and data structures, remains hard even
when we provide some amount of nondeterminism to the
query algorithms. The second result studies the amount of
extra information that can be provided to the query
algorithm without affecting the lower bound. Some
applications of these results are contained in this
chapter; in addition, they are heavily developed for the
lower bound proofs in the remainder of the thesis.\bibpar
Chapter~3 investigates the dynamic complexity of the
symmetric Boolean functions, and provides upper and lower
bounds. These results establish links between parallel
complexity (namely, Boolean circuit complexity) and
dynamic complexity. In particular, it is shown that the
circuit depth of any symmetric function and the dynamic
prefix problem for the same function depend on the same
combinatorial properties. The connection between these
two different modes and models of computation is shown to
be very strong in that the trade-off between circuit size
and circuit depth is similar to the trade-off between
update and query time.\bibpar
Chapter~4 considers dynamic graph problems. In
particular, it presents the fastest known algorithm for
dynamic reachability on planar acyclic digraphs with one
source and one sink (known as planar
{\em st-graphs}). Previous partial solutions to this
problem were known. In the second part of the chapter,
the techniques for lower bound from chapter~2 are further
exploited to yield new hardness results for a number of
graph problems, including reachability problems in planar
graphs and grid graphs, dynamic upward planarity testing
and monotone point location.\bibpar
Chapter~5 turns to strings, and focuses on the problem of
maintaining a string of parentheses, known as the dynamic
membership problem for the Dyck languages. Parentheses
are inserted and removed dynamically, while the algorithm
has to check whether the string is properly balanced. It
is shown that this problem can be solved in
polylogarithmic time per operation. The lower bound
techniques from the thesis are again used to prove the
hardness of this problem",
linkhtmlabs = "",
linkps = "",
linkpdf = ""
}
@TechReport{BRICS-DS-97-2,
author = "{\O}rb{\ae}k, Peter",
title = "Trust and Dependence Analysis",
institution = brics,
year = 1997,
type = ds,
number = "DS-97-2",
address = daimi,
month = jul,
note = "PhD thesis. x+175~pp",
abstract = "The two pillars of {\em trust analysis} and {\em
dependence algebra} form the foundation of this
thesis. Trust analysis is a static analysis of the
run-time trustworthiness of data. Dependence algebra is a
rich abstract model of data dependences in programming
languages, applicable to several kinds of
analyses.\bibpar
We have developed trust analyses for imperative languages
with pointers as well as for higher order functional
languages, utilizing both abstract interpretation,
constraint generation and type inference.\bibpar
The mathematical theory of dependence algebra has been
developed and investigated. Two applications of
dependence algebra have been given: a practical
implementation of a trust analysis for the C programming
language, and a soft type inference system for action
semantic specifications. Soundness results for the two
analyses have been established",
linkhtmlabs = "",
linkps = "",
linkpdf = ""
}
@TechReport{BRICS-DS-97-1,
author = "Brodal, Gerth St{\o}lting",
title = "Worst Case Efficient Data Structures",
institution = brics,
year = 1997,
type = ds,
number = "DS-97-1",
address = daimi,
month = jan,
note = "PhD thesis. x+121~pp",
abstract = "We study the design of efficient data structures where
each operation has a worst case efficient
implementations. The concrete problems we consider are
{\em partial persistence}, implementation of {\em
priority queues}, and implementation of {\em
dictionaries}.\bibpar
The {\em node copying\/} technique of Driscoll {\it et
al.}\ to make bounded in-degree and out-degree data
structures partially persistent, supports update steps in
amortized constant time and access steps in worst case
constant time. We show how to extend the technique such
that update steps can be performed in worst case constant
time on the pointer machine model.\bibpar
We present two comparison based priority queue
implementations. The first implementation supports {\sc
FindMin}, {\sc Insert} and {\sc Meld} in worst case
constant time and {\sc Delete} and {\sc DeleteMin} in
worst case time $O(\log n)$. The second implementation
achieves the same performance, but furthermore supports
{\sc DecreaseKey} in worst case constant time. We show
that these time bounds are optimal for all
implementations supporting {\sc Meld} in worst case time
$o(n)$. We show that any randomized implementation with
expected amortized cost $t$ comparisons per {\sc Insert}
and {\sc Delete} operation has expected cost at least
$n/{2^{O(t)}}$ comparisons for {\sc FindMin}.\bibpar
For the CREW PRAM we present time and work optimal
priority queues, supporting {\sc FindMin}, {\sc Insert},
{\sc Meld}, {\sc DeleteMin}, {\sc Delete} and {\sc
DecreaseKey} in constant time with $O(\log n)$
processors. To be able to speed up Dijkstra's algorithm
for the single-source shortest path problem we present a
different parallel priority data structure yielding an
implementation of Dijkstra's algorithm which runs in
$O(n)$ time and performs $O(m\log n)$ work on a CREW
PRAM.\bibpar
On a unit cost RAM model with word size $w$ bits we
consider the maintenance of a set of $n$ integers from
$0..2^w-1$ under {\sc Insert}, {\sc Delete}, {\sc
FindMin}, {\sc FindMax} and {\sc Pred} (predecessor
query). The RAM operations used are addition, left and
right bit shifts, and bit-wise boolean operations. For
any function $f(n)$ satisfying $\log\log n\leq f(n)\leq
\sqrt{\log n}$, we support {\sc FindMin} and {\sc
FindMax} in constant time, {\sc Insert} and {\sc Delete}
in $O(f(n))$ time, and {\sc Pred} in $O((\log n)/f(n))$
time.\bibpar
The last problem we consider is given a set of $n$ binary
strings of length $m$ each, to answer $d$--queries, {\it
i.e.}, given a binary string of length $m$ to report if
there exists a string in the set within Hamming distance
$d$ of the string. We present a data structure of size
$O(nm)$ supporting 1--queries in time $O(m)$ and the
reporting of all strings within Hamming distance 1 of the
query string in time $O(m)$. The data structure can be
constructed in time $O(nm)$ and supports the insertion of
new strings in amortized time $O(m)$",
longabstract = "We study the design of efficient data structures. In
particular we focus on the design of data structures
where each operation has a worst case efficient
implementations. The concrete problems we consider are
{\em partial persistence}, implementation of {\em
priority queues}, and implementation of {\em
dictionaries}.
The first problem we consider is how to make bounded in-degree and
out-degree data structures partially persistent, {\it i.e.}, how to
remember old versions of a data structure for later access. A {\em node
copying\/} technique of Driscoll {\it et al.}\ supports update steps in
amortized constant time and access steps in worst case constant time.
The worst case time for an update step can be linear in the size of the
structure. We show how to extend the technique of Driscoll {\em et
al.\/} such that update steps can be performed in worst case constant
time on the pointer machine model.
We present two new comparison based priority queue implementations, with
the following properties. The first implementation supports the
operations {\sc FindMin}, {\sc Insert} and {\sc Meld} in worst case
constant time and {\sc Delete} and {\sc DeleteMin} in worst case time
$O(\log n)$. The priority queues can be implemented on the pointer
machine and require linear space. The second implementation achieves the
same worst case performance, but furthermore supports {\sc DecreaseKey}
in worst case constant time. The space requirement is again linear, but
the implementation requires auxiliary arrays of size $O(\log n)$. Our
bounds match the best known amortized bounds (achieved by respectively
binomial queues and Fibonacci heaps). The data structures presented are
the first achieving these worst case bounds, in particular supporting
{\sc Meld} in worst case constant time. We show that these time bounds
are optimal for all implementations supporting {\sc Meld} in worst case
time $o(n)$. We also present a tradeoff between the update time and the
query time of comparison based priority queue implementations. Finally
we show that any randomized implementation with expected amortized cost
$t$ comparisons per {\sc Insert} and {\sc Delete} operation has expected
cost at least $n/{2^{O(t)}}$ comparisons for {\sc FindMin}.
Next we consider how to implement priority queues on parallel (comparison
based) models. We present time and work optimal priority queues for the
CREW PRAM, supporting {\sc FindMin}, {\sc Insert}, {\sc Meld}, {\sc
DeleteMin}, {\sc Delete} and {\sc DecreaseKey} in constant time with
$O(\log n)$ processors. Our implementation is the first supporting all
of the listed operations in constant time. To be able to speed up
Dijkstra's algorithm for the single-source shortest path problem we
present a different parallel priority data structure. With this
specialized data structure we give a parallel implementation of
Dijkstra's algorithm which runs in $O(n)$ time and performs $O(m\log n)$
work on a CREW PRAM. This represents a logarithmic factor improvement for
the running time compared with previous approaches.
We also consider priority queues on a RAM model which is stronger than
the comparison model. The specific problem is the maintenance of a set
of $n$ integers in the range $0..2^w-1$ under the operations {\sc
Insert}, {\sc Delete}, {\sc FindMin}, {\sc FindMax} and {\sc Pred}
(predecessor query) on a unit cost RAM with word size $w$ bits. The RAM
operations used are addition, left and right bit shifts, and bit-wise
boolean operations. For any function $f(n)$ satisfying $\log\log n\leq
f(n)\leq \sqrt{\log n}$, we present a data structure supporting {\sc
FindMin} and {\sc FindMax} in worst case constant time, {\sc Insert}
and {\sc Delete} in worst case $O(f(n))$ time, and {\sc Pred} in worst
case $O((\log n)/f(n))$ time. This represents the first priority queue
implementation for a RAM which supports {\sc Insert}, {\sc Delete} and
{\sc FindMin} in worst case time $O(\log\log n)$ --- previous bounds were
only amortized. The data structure is also the first dictionary
implementation for a RAM which supports {\sc Pred} in worst case $O(\log
n/\log\log n)$ time while having worst case $O(\log\log n)$ update time.
Previous sublogarithmic dictionary implementations do not provide for
updates that are significantly faster than queries. The best solutions
known support both updates and queries in worst case time $O(\sqrt{\log
n})$.
The last problem consider is the following dictionary problem over binary
strings. Given a set of $n$ binary strings of length $m$ each, we want
to answer $d$--queries, {\it i.e.}, given a binary query string of length
$m$ to report if there exists a string in the set within Hamming distance
$d$ of the query string. We present a data structure of size $O(nm)$
supporting 1--queries in time $O(m)$ and the reporting of all strings
within Hamming distance 1 of the query string in time $O(m)$. The data
structure can be constructed in time $O(nm)$. The implementation
presented is the first achieving these optimal time bounds for the
preprocessing of the dictionary and for 1--queries. The data structure
can be extended to support the insertion of new strings in amortized time
$O(m)$",
linkhtmlabs = "",
linkps = "",
linkpdf = ""
}