Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 10 of 10 for “"amortized analysis"”.
-
A type-theory for higher-order amortized analysis
… depends on the precision of the underlying analysis. For precision, sometimes it is useful to consider the average cost over a sequence of operations, instead of separately considering the cost of each individual operation. This kind of an analysis is often referred to as amortized resource …
-
Types with potential: polynomial resource bounds via automatic amortized analysis
… bounds, it relies on the potential method of amortized analysis. Types are annotated with multivariate resource polynomials, a rich class of functions that generalize non-negative linear combinations of binomial coefficients. The main theorem states that type derivations establish resource …
-
THE DESIGN AND ANALYSIS OF HEAP ALGORITHMS
… This thesis is a study on the design and analysis of heap-type data structures. In particular, we are interested in the asymptotic limits in the efficiency of operations on heaps. The key contributions of this thesis are in the development of three new types of heaps: inorder heaps, …
-
On Lock-Free Data Structures for Dynamic Sets and Their Amortized Step Complexities
… because operations may run forever. In an amortized analysis of these data structures, we consider the number of steps taken in an execution consisting of a sequence operations, rather than an individual operation. Depending on how the steps of processes are interleaved, there are many ways …
-
Non-Blocking Data Structures Handling Multiple Changes Atomically
… for our list implementation. We also give an amortized analysis for our list implementation, which is the first upper bound on amortized time complexity that has been proved for a concurrent doubly-linked list. In addition, we evaluate our list algorithms on a multi-core system empirically to …
-
New Analytical Methods for Online Binary Search Trees
… extend the use of extremal combinatorics in an amortized analysis of BSTs. The technique exploits the specific structures of the input of BSTs. This method encodes the execution log of BSTs in the form of a matrix and applies powerful theorems from forbidden matrix literature to upper-bound the …
-
Multi-way self-adjusting data structures: a general theory and some limitations
… the formulation of contemporary concepts such as amortized analysis and competitiveness. Our own work focuses on the situations in which we can do better than classical binary search trees, namely in biased searching, when balanced trees “lose” because of their “over-balancedness”. The classical …
-
Updating the Vertex Separation of a Dynamically Changing Tree
… have good running time performance only in the amortized sense. The running time of all our algorithms is sublinear in the number of vertices in the tree, assuming certain information is precomputed for the tree. This improves upon current algorithms by Skodinis and Ellis, Sudborough, and …
-
Applications of Lexicographic Breadth-first Search to Modular Decomposition, Split Decomposition, and Circle Graphs
This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches …
-
Advanced Static Performance Analysis Using Meta Infer
Statický analyzátor složitosti Looper slouží pro odvozování přesných horních mezí ceny vykonání programů. Jako teoretický základ byl využit dříve existující nástroj Loopus a jeho abstraktní programový model využívající tzv. difference constraints (nerovnosti typu + ), které umožňují přirozeným …