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"”.

  1. 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 …

    kent

  2. 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 …

    lmu-germany Repository record for Types with potential: polynomial resource bounds via automatic amortized analysis (opens in a new tab)

  3. 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, …

    nus Repository record for THE DESIGN AND ANALYSIS OF HEAP ALGORITHMS (opens in a new tab) Download file for THE DESIGN AND ANALYSIS OF HEAP ALGORITHMS (opens in a new tab)

  4. 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 …

    toronto-retro Repository record for On Lock-Free Data Structures for Dynamic Sets and Their Amortized Step Complexities (opens in a new tab)

  5. 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 …

    york Repository record for Non-Blocking Data Structures Handling Multiple Changes Atomically (opens in a new tab)

  6. 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 …

    aalto Repository record for New Analytical Methods for Online Binary Search Trees (opens in a new tab)

  7. 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 …

    greece Repository record for Multi-way self-adjusting data structures: a general theory and some limitations (opens in a new tab)

  8. 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 …

    waterloo Repository record for Updating the Vertex Separation of a Dynamically Changing Tree (opens in a new tab)

  9. 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 …

    toronto-retro Repository record for Applications of Lexicographic Breadth-first Search to Modular Decomposition, Split Decomposition, and Circle Graphs (opens in a new tab)

  10. 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 …

    brno-tech Repository record for Advanced Static Performance Analysis Using Meta Infer (opens in a new tab)