We investigate two lowest common ancestors (LCA) problems on trees. We give a linear time algorithm for the off-line problem, on a random access machine (RAM). The half-line problem is one in which LCA queries on a fixed tree are arriving on line. We extend our RAM algorithm to answer each individual query in 0(1) time, with 0(n) preprocessing time. Tarjan observed that this result helps to explicate the difference in power between RAM and pointer machines. We also show how to modify our algorithm to achieve a linear preprocessing time, optimal query time, algorithm on a reference machine.

We show how binary trees of bounded balance can be maintained so that the time to perform each individual update (insertion or deletion) in a tree of n nodes is 0(log*n), once the location of the update is known. This is the first example of a balanced tree scheme in which the time of each individual insertion/deletion is substantially lower than the height of the tree, which is 0(log n). Such a data structure is useful in situations where the search time may be much lower than 0(log n). The main example of such a situation is the framework of data structures which support fingers. In addition to guaranteed time bounds per update, our structure supports arbitrarily many fingers and approximate range queries.

A finger is a point in a file near which updates and searches can be conducted particularly efficiently. We present a data structure which supports insertions, deletions, searches, and approximate range queries. In each case both a finger f and a key k are specified as arguments to the appropriate algorithm. The total time bound for n updates (insertion or deletions) in an initiallly empty data structure is the sum over all updates of 0(log d+log*n), where d is the linear distance (i.e., the distance in the linear list being represented) from f to k. By an approximate range query, we mean a query of the form "How many keys lie between the finger f and the key k?", where a predetermined percentage of error is allowed in the number returned. The time for each individual search or range query is 0(log d).

Criminal sanctions are usually public, stable and predictable. In contrast, the practices governing the determination of the probability of detection and conviction reinforce uncertainty. We invoke psychological insights to illustrate that criminals prefer a scheme in which the size of the sentence is uncertain while the probability of detection and conviction is certain. Consequently, the choice to increase certainty with respect to the size of the sentence and to decrease certainty with respect to the probability of detection and conviction can be justified on the grounds that such a scheme is disfavored by criminals and consequently has better deterrent effects.

The rapid evolution of machine learning (ML) presents significant evaluation challenges, particularly regarding data quality (data bugs) and the limited applicability of traditional software testing metrics. Standard evaluation often overlooks crucial aspects like nuanced data diversity, subjective user experience, and content provenance. This dissertation argues for a paradigm shift in ML evaluation, moving beyond narrow, structural metrics towards holistic frameworks. The central thesis is that robust and meaningful assessment requires integrating complementary perspectives: systematically enhancing data diversity, incorporating human-centric subjective evaluation, and ensuring reliable authorship verification.

This work investigates these pillars through empirical studies. Initial analysis reveals the limitations of structural metrics like neuron coverage (NC) for effectively guiding diverse test generation in deep neural networks (RQ1). Subsequently, we demonstrate that aggressively expanding input diversity via label-altering transformations (sibylvariance) significantly improves model generalization, defect detection, and robustness (RQ2). To refine augmentation strategies, we introduce feature-aware data augmentation (FADA) to optimize policies by balancing diversity and text quality, alongside INSPECTOR, a human-in-the-loop system using transformation provenance for efficient data validation (RQ3). Shifting focus to output quality, we propose the Psychological Depth Scale (PDS) to measure subjective, human-centric dimensions like empathy and engagement, finding that current language models can achieve high, human-like levels (RQ4). Recognizing the challenge this poses, we analyze watermarking techniques, demonstrating their practical resilience against attacks and affirming their necessity for authorship verification in the age of advanced AI (RQ5).

Collectively, these findings underscore the need for a multi-faceted evaluation approach. This research contributes components towards a unified framework synthesizing structural rigor, data-centric diversity, human judgment on quality and subjective experience, and technical methods for provenance. By adopting such holistic evaluation—drawing on software engineering, machine learning, and human-computer interaction—we can better assess ML systems for real-world reliability, utility, and trustworthiness, fostering the development of more beneficial and accountable AI.

Pore structure and connectivity determine how microstructured materials perform in applications such as catalysis, fluid storage and transport, filtering, or as reactors. We report a model study on silica aerogel using a recently introduced time-of-flight (TOF) magnetic resonance imaging technique to characterize the flow field and elucidate the effects of heterogeneities in the pore structure on gas flow and dispersion with Xe-129 as the gas-phase sensor. The observed chemical shift allows the separate visualization of unrestricted xenon and xenon confined in the pores of the aerogel. The asymmetrical nature of the dispersion pattern alludes to the existence of a stationary and a flow regime in the aerogel. An exchange time constant is determined to characterize the gas transfer between them. As a general methodology, this technique provides new insights into the dynamics of flow in porous media where multiple phases or chemical species may be present.