bluuebunny/crossref_metadata_2025 huggingface dataset:
EFFICIENCY AND OPTIMIZATION OF THE 3-D FINITE-DIFFERENCE MODELING OF SEISMIC GROUND MOTION
Authors: MOCZO PETER , KRISTEK JOZEF , BYSTRICKÝ ERIK
Published: July 2002

We present a tutorial introduction to the 3-D finite-difference modeling of seismic ground motion in elastic and viscoelastic media with special emphasis on its computational efficiency. We consider four basic types of the finite-difference schemes — the displacement-stress, displacement-velocity-stress and velocity-stress schemes on a staggered grid, and displacement scheme on a conventional grid. Their memory requirements in the case of perfectly elastic medium, elastic medium with aposteriori approximate attenuation correction, and realistic viscoelastic medium are reviewed. We also present application of the powerful optimization techniques to the 3-D fourth-order displacement-stress and displacement-velocity-stress modeling in the case of viscoelastic medium whose rheology is based on the generalized Maxwell body. Description of a medium using material cell types and use of a discontinuous grid with combined memory optimization makes it possible to simulate earthquake ground motion in realistic large-scale models.
LEED AND STM STUDY OF Cs ON Cu(211)
Authors: CARAGIU M. , SEYLLER TL. , DIEHL R. D. , NORRIS A. G. , McGRATH R. , MURYN C. A.
Published: July 2002

A low-temperature (25 K) STM study of Cs adsorption on Cu(211) indicates that Cs forms variable-density structures which align along the step edges of the Cu(211) surface. The density of the overlayer increases with Cs coverage, forming a quasihexagonal c(2×2) structure at a coverage of 0.17. A dynamical LEED study of that structure at 130 K indicates that the Cs atoms are adsorbed on top of the Cu atoms in the center of the terraces, with a Cs–Cu nearest-neighbor distance of 3.56± 0.04 Å. This structure is accompanied by a significant rumpling of the Cu(211) surface.
FLEXOR DIGITORUM PROFUNDUS TENDON AVULSION THROUGH A RECURRENT ENCHONDROMA — A CASE REPORT
Authors: Chen Darren B. , Yee David C.
Published: July 2002

Flexor digitorum profundus (FDP) tendon avulsion from the distal phalanx is a well recognised injury, which usually follows a hyperextension force to a flexed distal interphalangeal (DIP) joint. It is commonly seen in contact sport athletes, with a predilection for the ring finger.2,4 Avulsion of the FDP tendon from pathological bone is an infrequent occurrence. It has, however, been reported to occur in association with an enchondroma of the distal phalanx.2,3 To our knowledge, an FDP tendon avulsion through a recurrent enchondroma has not been reported. We present the case findings of such an event.
ISCHAEMIA OF THE HAND IN INFANTS FOLLOWING RADIAL OR ULNAR ARTERY CATHETERISATION
Authors: Green J. A. , Tonkin M. A.
Published: July 2002

Radial and ulnar arterial catheterisation have become frequently used methods of monitoring in neonatal and pediatric intensive care units. Minor complications are common and temporary ischaemic changes in the form of blanching are well described. However, permanent ischaemia in the infant has rarely been reported. This series is the first in the hand surgery literature to address the issue of digital ischaemia following radial artery catheterisation in the infant population and adds three to the six previously reported cases in the English literature. One patient had fingertip necrosis to the distal interphalangeal joint level of the middle, ring and little fingers, while two other patients required amputation at the carpometacarpal joint level.
PHYSICISTS ATTEMPT TO SCALE THE IVORY TOWERS OF FINANCE
Authors: FARMER J. DOYNE
Published: July 2002

Physicists have recently begun doing research in finance, and even though this movement is less than five years old, interesting and useful contributions have already emerged. This article reviews these developments in four areas, including empirical statistical properties of prices, random-process models for price dynamics, agent-based modeling, and practical applications.
OPTION RISK MEASUREMENT WITH TIME-DEPENDENT PARAMETERS
Authors: LO C. F. , YUEN P. H. , HUI C. H.
Published: July 2002

In value-at-risk (VaR) methodology of option risk measurement, the determination of market values of the current option positions under various market scenarios is critical. Under the full revaluation and factor sensitivity approach which are accepted by regulators, accurate revaluation and precise factor sensitivity calculation of options in response to significant moves in market variables are important for measuring option risks in terms of VaR figures. This paper provides a method for pricing equity options in the constant elasticity variance (CEV) model environment using the Lie-algebraic technique when the model parameters are time-dependent. Analytical solutions for option values incorporating time-dependent model parameters are obtained in various CEV processes. The numerical results, which are obtained by employing a very efficient computing algorithm similar to the one proposed by Schroder [11], indicate that the option values are sensitive to the time-dependent volatility term structures. It is also possible to generate further results using various functional forms for interest rate and dividend term structures. From the analytical option pricing formulae, one can achieve more accuracy to compute factor sensitivities using more realistic term-structures in volatility, interest rate and dividend yield. In view of the CEV model being empirically considered to be a better candidate in equity option pricing than the traditional Black–Scholes model, more precise risk management in equity options can be achieved by incorporating term-structures of interest rates, volatility and dividend into the CEV option valuation model.
A PATH INTEGRAL APPROACH TO DERIVATIVE SECURITY PRICING II: NUMERICAL METHODS
Authors: ROSA-CLOT MARCO , TADDEI STEFANO
Published: July 2002

We discuss two numerical techniques, based on the path integral approach described in a previous paper, for solving the stochastic equations underlying the financial markets: the path integral Monte Carlo, and the path integral deterministic evaluation. In particular, we apply the latter to some specific financial problems: the pricing of a European option, a zero-coupon bond, a caplet, an American option, and a Bermudan swaption.
ESSENTIAL SMOOTHNESS, ESSENTIAL STRICT CONVEXITY, AND LEGENDRE FUNCTIONS IN BANACH SPACES
Authors: BAUSCHKE HEINZ H. , BORWEIN JONATHAN M. , COMBETTES PATRICK L.
Published: July 2002

The classical notions of essential smoothness, essential strict convexity, and Legendreness for convex functions are extended from Euclidean to Banach spaces. A pertinent duality theory is developed and several useful characterizations are given. The proofs rely on new results on the more subtle behavior of subdifferentials and directional derivatives at boundary points of the domain. In weak Asplund spaces, a new formula allows the recovery of the subdifferential from nearby gradients. Finally, it is shown that every Legendre function on a reflexive Banach space is zone consistent, a fundamental property in the analysis of optimization algorithms based on Bregman distances. Numerous illustrating examples are provided.
EFFECT OF GEOMETRIC AND LOADING CONDITIONS ON STABILITY OF PRESTRESSED ARCHES
Authors: MIRMIRAN AMIR , AMDE AMDE M. , XU ZEFANG
Published: July 2002

Geometric and loading conditions affect stability and strength of arch frameworks. Prestressed arches that are made by buckling of flat struts into shape are more sensitive to these parameters. Most studies on prestressed arches are limited to the initial buckling path, not accounting for the looping response. This paper investigates the effect of arch rise-to-span ratio, support fixity, tapering of the arch section and various loading conditions on the complete response of prestressed arches. A corotational formulation augmented with a two-parameter path finding technique is developed to effectively trace the snap-through, snap-back, and looping paths of the arch. Results indicate that symmetric limit loads increase almost proportionally to the steepness ratio of the arch, whereas the asymmetric bifurcation loads asymptote around the rise-to-span ratio of 0.5. Clamped arches are more stable than their equivalent pinned arches, and do not demonstrate any looping behavior. A tapered-out prestressed arch with a taper angle of less than 2° 12′ is more stable than its equivalent prismatic or tapered-in arch. Prestressed arch is least stable when a point load acts within 12%–27% of its span length from the crown, or when only three-quarters of the span is loaded with a uniform load.
DYNAMICS OF ECONOMIC AND TECHNOLOGICAL SEARCH PROCESSES IN COMPLEX ADAPTIVE LANDSCAPES
Authors: EBELING W. , SCHARNHORST A.
Published: July 2002

We investigate the dynamics of economic evolution and technological change as hill-climbing in an adaptive landscape over a continuous characteristics space. A technology/firm is described by a large number of attributes or characteristics representing technology-inherent aspects, financial, organizational and economic features. These parameters span a characteristics space, which is a real Euclidean vector space, in analogy to the phenotype space in biology. Further we define a real-valued multimodal fitness function/functional and a population density over the characteristics space. The evolutionary dynamics including competition and mutations/innovations is modeled by reaction-diffusion equations of Fisher–Eigen or Lotka–Volterra type. We demonstrate the potential of such models, which in certain aspects go beyond the widespread applications of discrete replicator dynamics. Concerning technological change the emergence of technological populations as the result of a search process in an adaptive landscape will be investigated. In particular, the relation between incremental and radical innovations will be considered, especially the apparent paradox of a discrete continuum of technological change. Further, an application of the developed framework to the assessment of firms in the stock market is discussed.
An extension of manifold boundary representations to the r-sets
Authors: Desaulniers H. , Stewart N. F.
Published: July 2002

In this paper we study the relationship between
manifold solids
(r-sets whose boundaries are two-dimensional closed manifolds) and
r-sets
. We begin by showing that an r-set may be viewed as the limit of a certain sequence of manifold solids, where distance is measured using the Hausdorff metric. This permits us to introduce a minimal set of generalized Euler operators, sufficient for the construction and manipulation of r-sets. The completeness result for ordinary Euler operators carries over immediately to the generalized Euler operators on the r-sets and the modification of the usual boundary data structures, corresponding to our extension to nonmanifold r-sets, is straightforward. We in fact describe a modification of a well-known boundary data structure in order to illustrate how the extension can be used in typical solid modeling algorithms, and describe an implementation.

The results described above largely eliminate what has been called an inherent mismatch between the modeling spaces defined by manifold solids and by r-sets. We view the r-sets as a more appropriate choice for a modeling space: in particular, the r-sets provide closure with respect to regularized set operations and a complete set of generalized Euler operators for the manipulation of boundary representations, for graphics and other purposes. It remains to formulate and prove a theorem on the soundness of the generalized Euler operators.
Visibility-ordering meshed polyhedra
Authors: Williams Peter L.
Published: July 2002

A visibility-ordering of a set of objects from some viewpoint is an ordering such that if object
a
obstructs object
b
, then
b
precedes
a
in the ordering. An algorithm is presented that generates a visibility-ordering of an acyclic convex set of meshed convex polyhedra. This algorithm takes time linear in the size of the mesh. Modifications to this algorithm and/or preprocessing techniques are described that permit nonconvex cells nonconvex meshes (meshes with cavities and/or voids), meshes with cycles, and sets of disconnected meshes to be ordered. Visibility-ordering of polyhedra is applicable to scientific visualization, particularly direct volume rendering. It is shown how the ordering algorithms can be used for domain decomposition of finite element meshes for parallel processing, and how the data structures used by these algorithms can be used to solve the spatial point location problem. The effects of cyclically obstructing polyhedra are discussed and methods for their elimination are described, including the use of the Delaunay triangulation. Methods for converting nonconvex meshes into convex meshes are described.
A practical approach to calculating luminance contrast on a CRT
Authors: MacIntyre Blair , Cowan William B.
Published: July 2002

Luminance contrast is the basis of text legibility, and maintaining luminance contrast is essential for any color selection algorithm. In principle, it can be calculated precisely on a sufficiently well-calibrated display surface, but calibration is very expensive. Consequently, most current systems deal with contrast using heuristics. However, the usual CRT setup puts the display surface into a state that is relatively predictable. Luminance values can be estimated based on this state, and these luminance values have been used to calculate contrast using the Michelson definition. This paper proposes a method for determining the contrast of colored areas displayed on a CRT. It uses a contrast metric that is in wide use in visual psychophysics and shows that the metric can be approximated reasonably without display measurement, as long as it is possible to assume that the CRT has been adjusted according to usual CRT setup standards.
Algorithm 704: ABDPACK and ABBPACK-FORTRAN programs for the solution of almost block diagonal linear systems arising in spline collocation at Gaussian points with monomial basis functions
Authors: Majaess Fouad , Keast Patrick , Fairweather Graeme , Bennett Karin R.
Published: July 2002

ABDPACK is a package of FORTRAN programs for the solution of systems of linear equations with the almost block diagonal structure arising in spline collocation at Gaussian points with monomial spline basis functions, when applied to two-point boundary value problems with separated boundary conditions. The package ABBPACK is designed to handle a subclass of such linear systems which have what may be called an almost block bidiagonal structure. Such systems result, for example, when condensation is applied to the full spline collocation linear system. This package may also be used to solve the almost block bidiagonal systems arising in multiple shooting techniques and implicit Runge-Kutta methods for solving two-point boundary value problems. The algorithms implemented in the package are based on an alternate column and row pivoting scheme which avoids most of the fill-in introduced by more commonly used techniques.
Adjoint equations and random walks for illumination computation
Authors: Pattanaik S. N. , Mudur S. P.
Published: July 2002

In this paper we introduce the potential equation that along with the rendering equation forms an adjoint system of equations and provides a mathematical frame work for all known approaches to illumination computation based on geometric optics. The potential equation is more natural for illumination computations that simulate light propagation starting from the light sources, such as progressive radiosity and particle tracing. Using the mathematical handles provided by this framework and the random-walk solution model, we present a number of importance sampling schemes for improving the computation of flux estimation. Of particular significance is the use of approximately computed potential for directing a majority of the random walks through regions of importance in the environment, thus reducing the variance in the estimates of luminous flux in these regions. Finally, results from a simple implementation are presented to demonstrate the high-efficiency improvements made possible by the use of these techniques.
The computation of elementary unitary matrices
Authors: Lehoucq R. B.
Published: July 2002

The construction of elementary unitary matrices that transform a complex vector to a multiple of
e
1
, the first column of the identity matrix, is studied. We present four variants and their software implementation, including a discussion onthe LAPACK subroutine CLARFG. Comparisons are also given.
Clustering for glossy global illumination
Authors: Christensen Per H. , Lischinski Dani , Stollnitz Eric J. , Salesin David H.
Published: July 2002

We present a new clustering algorithm for global illumination in complex environments. The new algorithm extends provious work on clustering for radiosity to allow for nondiffuse (glossy) reflectors. We represent clusters as points with directional distributions of outgoing and incoming radiance and importance, and we derive an error bound for transfers between these clusters. The algorithm groups input surfaces into a hierarchy of clusters, and then permits clusters to interact only if the error bound is below an acceptable tolerance. We show that the algorithm is asymptotically more efficient than previous clustering algorithms even when restricted to ideally diffuse environments. Finally, we demonstrate the performance of our method on two complex glossy environments.
Weighted bicubic spline interpolation to rapidly varying data
Authors: Foley Thomas A.
Published: July 2002

The weighted bicubic spline that is a C
1
piecewise bicubic interpolant to three-dimensional gridded data is introduced. This is a generalization of the univariate weighted spline, developed by Salkauskas, in that a weighted minimization problem is solved. The minimization problem solved is a weighted version of the problem that the natural bicubic spline and Gordon's spline-blended interpolants minimize. The surface is represented as a piecewise bicubic Hermite interpolant whose derivatives are the solution of a linear system of equations. For computer-aided-design applications, the shape of the surface is controlled by weighting the variation over the individual patches, whereas many other shape-control methods weight the discrete data points. A method for selecting the weights is presented so that the weighted bicubic spline effectively solves the important and often difficult problem of interpolating rapidly varying data.
Composition and refinement of discrete real-time systems
Authors: Ostroff Jonathan S.
Published: July 2002

Reactive systems exhibit ongoing, possibly nonterminating, interaction with the environment. Real-time systems are reactive systems that must satisfy quantitative timing constraints. This paper presents a structured compositional design method for discrete real-time systems that can be used to combat the combinatorial explosion of states in the verification of large systems. A
composition rule
describes how the correctness of the system can be determined from the correctness of its modules, without knowledge of their internal structure. The advantage of compositional verification is clear. Each module is both simpler and smaller than the system itself. Composition requires the use of both model-checking and deductive techniques. A
refinement rule
guarantees that specifications of high-level modules are preserved by their implementations. The
StateTime
toolset is used to automate parts of compositional designs using a combination of model-checking and simulation. The design method is illustrated using a reactor shutdown system that cannot be verified using the StateTime toolset (due to the combinatorial explosion of states) without compositional reasoning. The reactor example also illustrates the use of the refinement rule.
Convexity algorithms in parallel coordinates
Authors: Inselberg Alfred , Reif Mordechai , Chomut Tuval
Published: July 2002

With a system of
parallel coordinates
, objects in

R
N

can be represented with planar “
graphs
” (i.e., planar diagrams) for arbitrary
N
[21]. In
R
2
, embedded in the projective plane, parallel coordinates induce a point ← → line duality. This yields a new duality between
bounded and unbounded convex sets and hstars
(
a generalization of hyperbolas
), as well as a duality between convex union (convex merge) and intersection. From these results, algorithms for constructing the intersection and convex merge of convex polygons in
O
(
n
) time and the convex hull on the plane in
O
(log
n
) for real-time and
O
(
n
log
n
) worst-case construction, where
n
is the total number of points, are derived. By virtue of the duality, these algorithms also apply to polygons whose edges are a certain class of convex curves. These planar constructions are studied prior to exploring generalizations to
N
-dimensions. The needed results on parallel coordinates are given first.
Presto
Authors: Dourish Paul , Edwards W. Keith , LaMarca Anthony , Salisbury Michael
Published: July 2002

Traditional document systems use hierarchical filing structures as the basis for organizing, storing and retrieving documents. However, this structure is very limited in comparison with the rich and varied forms of document interaction and category management in everyday document use. Presto is a prototype document management system providing rich interaction with documents through meaningful, user-level document attributes, such as “Word file,” “published paper,” “shared with Jim,” “about Presto,” or “currently in progress” Document attributes capture the multiple different roles that a single document might play, and they allow users to rapidly reorganize their document space for the task at hand. They also provide a basis for novel document systems design and new approaches to document management and interaction. In this article, we outline the motivations behind this approach, describe the principal components of our implementation, discuss architectural consequences, and show how these support new forms of interactions with large personal document spaces.
Testing implications of data dependencies
Authors: Maier David , Mendelzon Alberto O. , Sagiv Yehoshua
Published: July 2002

Presented is a computation method—the
chase
—for testing implication of data dependencies by a set of data dependencies. The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman. The chase includes previous tableau computation methods as special cases. By interpreting tableaux alternately as mappings or as templates for relations, it is possible to test implication of join dependencies (including multivalued dependencies) and functional dependencies by a set of dependencies.
An Algorithm for the Chromatic Number of a Graph
Authors: Wang Chung C.
Published: July 2002

Christofides' algorithm for finding the chromatic number of a graph is improved both in speed and memory space by using a depth-first search rule to search for a shortest path in a reduced subgraph tree.
The theory of direct probability redistribution and its application to rare event simulation
Authors: Haraszti Zsolt , Townsend J. Keith
Published: July 2002

Rare event simulation is an important area of simulation theory, producing algorithms that can significantly reduce the simulation time when analyzing problems that involve rare events. However, existing rare event simulation techniques are rather restrictive, i.e., applicable only to systems with modest complexity. In this paper, we first develop a Markov chain transformation theory that can redistribute steady-state probabilities in a finite-size discrete-time Markov chain in an arbitrary and controlled manner. We descriptively name the theoretical procedure “direct probability redistribution” (DPR). In the second part of the paper, we develop DPR theory into a simulation algorithm that uses trajectory splitting to realize the DPR effect without knowledge of the transition probability matrix, thus allowing for easy application to systems with realistic complexity. DPR-based splitting can significantly reduce the simulation time by increasing the visitng frequency of rare states, and it avoids the problems associated with the decreasing likelihood ratio, which can be a limitation in conventional Importance Sampling techniques. The main advantage of the DPR-based simulation technique over existing splitting techniques is that DPR does not impose any restrictions on the state transitions and it provides asymptotically unbiased estimates even if the rare event set overlaps many splitting partitions. We conclude by providing examples where DPR-based simulation has been successfully applied to nontrivial queuing problems, including a system with flow control.
Efficient parallel algorithms for some graph problems
Authors: Chin Francis Y. , Lam John , Chen I-Ngo
Published: July 2002

We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses
K
processors for finding the connected components of an undirected graph. In particular, an
O
(log
2
n
) time bound can be achieved using only
K
=
n
⌈
n
/log
2
n
⌉ processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods.
Decentralized extrema-finding in circular configurations of processors
Authors: Hirschberg D. S. , Sinclair J. B.
Published: July 2002

This note presents an efficient algorithm, requiring
O
(
n
log
n
) message passes, for finding the largest (or smallest) of a set of
n
uniquely numbered processors arranged in a circle, in which no central controller exists and the number of processors is not known a priori.
An optimal insertion algorithm for one-sided height-balanced binary search trees
Authors: Räihä Kari-Jouko , Zweben Stuart H.
Published: July 2002

An algorithm for inserting an element into a one-sided height-balanced (OSHB) binary search tree is presented. The algorithm operates in time
O
(log
n
), where
n
is the number of nodes in the tree. This represents an improvement over the best previously known insertion algorithms of Hirschberg and Kosaraju, which require time
O
(log
2
n
). Moreover, the
O
(log
n
) complexity is optimal.

Earlier results have shown that deletion in such a structure can also be performed in
O
(log
n
) time. Thus the result of this paper gives a negative answer to the question of whether such trees should be the first examples of their kind, where deletion has a smaller time complexity than insertion. Furthermore, it can now be concluded that insertion, deletion, and retrieval in OSHB trees can be performed in the same time as the corresponding operations for the more general AVL trees, to within a constant factor. However, the insertion and deletion algorithms for OSHB trees appear much more complicated than the corresponding algorithms for AVL trees.
Computing standard deviations
Authors: Chan Tony F. , Lewis John Gregg
Published: July 2002

Four algorithms for the numerical computation of the standard deviation of (unweighted) sampled data are analyzed. Two of the algorithms are well-known in the statistical and computational literature; the other two are new algorithms specifically intended for automatic computation. Our discussion is expository, with emphasis on reaching a suitable definition of “accuracy.” Each of the four algorithms is analyzed for the conditions under which it will be accurate. We conclude that all four algorithms will provide accurate answers for many problems, but two of the algorithms, one new, one old, are substantially more accurate on difficult problems than are the other two.
SP/k
Authors: Holt R. C. , Wortman D. B. , Barnard D. T. , Cordy J. R.
Published: July 2002

SP/k is a compatible subset of the PL/I language that has been designed for teaching programming. The features of the SP/k language were chosen to encourage structured problem solving by computers, to make the language easy to learn and use, to eliminate confusing and redundant constructs, and to make the language easy to compile. The resulting language is suitable for introducing programming concepts used in various applications, including business data processing, scientific calculations and non-numeric computation. SP/k is actually a sequence of language subsets called SP/1, SP/2, … SP/8. Each subset introduces new programming language constructs while retaining all the constructs of preceding subsets. Each subset is precisely defined and can be learned or implemented without the following subsets.
Shifting garbage collection overhead to compile time
Authors: Barth Jeffrey M.
Published: July 2002

This paper discusses techniques which enable automatic storage reclamation overhead to be partially shifted to compile time. The paper assumes a transaction oriented collection scheme, as proposed by Deutsch and Bobrow, the necessary features of which are summarized. Implementing the described optimizations requires global flow analysis to be performed on the source program. It is shown that at compile time certain program actions that affect the reference counts of cells can be deduced. This information is used to find actions that cancel when the code is executed and those that can be grouped to achieve improved efficiency.
A computer science course program for small colleges
Authors: Engel Gerald L.
Published: July 2002

The ACM Subcommittee on Small College Programs of the Committee on Curriculum in Computer Science (C
3
S) was appointed in 1969 to consider the unique problems of small colleges and universities, and to make recommendations regarding computer science programs at such schools. This report, authorized by both the subcommittee and C
3
S, supplies a set of recommendations for courses and necessary resources.

Implementation problems are discussed, specifically within the constraints of limited faculty and for the purposes of satisfying a wide variety of objectives. Detailed descriptions of four courses are given; suggestions are made for more advanced work; and an extensive library list is included.
A university's educational program in computer science
Authors: Forsythe George E.
Published: July 2002

After a review of the power of contemporary computers, computer science is defined in several ways. The objectives of computer science education are stated, and it is asserted that in a North American university these will be achieved only through a computer science department. The program at Stanford University is reviewed as an example. The appendices include syllabi of Ph.D. qualifying examinations for Stanford's Computer Science Department.
Improved master theorems for divide-and-conquer recurrences
Authors: Roura Salvador
Published: July 2002

This paper presents new theorems to analyze divide-and-conquer recurrences, which improve other similar ones in several aspects. In particular, these theorems provide more information, free us almost completely from technicalities like floors and ceilings, and cover a wider set of toll functions and weight distributions, stochastic recurrences included.
sTeam
Authors: Hampel Thorsten , Keil-Slawik Reinhard
Published: July 2002

Learning is a socially embedded design process. But most of todays hypermedia systems fail to properly support the design-related and the social aspects of learning. Authoring and Web-publishing systems aim to support the authors design processes. Consequently, the activities of learners are confined to selecting and reading. Based on some fundamental reflections on the role of technology in learning processes, we conclude that top priority must be given to the construction of infrastructures that support cooperative learning processes if we are to properly harness the technologys potential.

We present a learner-centered, wholly Web-based approach for structuring information in teams (sTeam). In sTeam the key concept is virtual space. It draws cooperation and communication together, while at the same time embodying the common external memory of a (virtual) learning group. Hence, the focus is not on interactive systems for individual access of knowledge bases, but on the cooperative management and structuring of distributed knowledge bases.
Electronic calendars in the office: an assessment of user needs and current technology
Authors: Kincaid Christine M. , Dupont Pierre B. , Kaye A. R.
Published: July 2002

Manufacturers of integrated electronic office systems have included electronic versions of the calendar in almost every system they offer. This paper describes a survey of office workers, carried out to examine their use both of paper calendars and of electronic calendars that are commercially available as part of integrated office systems. It assesses the degree to which electronic calendars meet the needs of users. Our survey shows that the simple paper calendar is a tool whose power and flexibility is matched by few, if any, of the current commercially available electronic calendars. Recommendations for features that should be included in electronic calendars and automatic schedulers are included.
Reading and writing with computers: a framework for explaining differences in performance
Authors: Hansen Wilfred J. , Haas Christina
Published: July 2002

Several factors can influence the behavior of users as they read and write with computers. Recent research indicates that both quality and quantity depend upon page size, legibility, responsiveness and tangibility.
A thinning algorithm by contour generation
Authors: Kwok Paul
Published: July 2002

A new contour generating serial algorithm is faster and more efficient than conventional contour tracing and parallel algorithms
The spiritual life of projects
Authors: Armour Phillip G.
Published: July 2002

The human factor in software development is the ingredient that ultimately gives a project team its soul.
A note on the height of binary search trees
Authors: Devroye Luc
Published: July 2002

Let

H
n

be the height of a binary search tree with
n
nodes constructed by standard insertions from a random permutation of 1, … ,
n
. It is shown that

H
n

/log
n
→
c
= 4.31107 … in probability as
n
→ ∞, where
c
is the unique solution of
c
log((2
e
)/
c
) = 1,
c
≥ 2. Also, for all
p
> 0, lim

n
→∞

E
(

H
p
n

)/ log

p
n

=

c
p

. Finally, it is proved that

S
n

/log
n
→
c
*
= 0.3733 … , in probability, where
c
*
is defined by
c
log((2
e
)/
c
) = 1,
c
≤ 1, and

S
n

is the saturation level of the same tree, that is, the number of full levels in the tree.
Another look at automatic text-retrieval systems
Authors: Salton Gerard
Published: July 2002

Evidence from available studies comparing manual and automatic text-retrieval systems does not support the conclusion that intellectual content analysis produces better results than comparable automatic systems.
Password cracking: a game of wits
Authors: Seeley Donn
Published: July 2002

The following report has been gleaned from "A Tour of the Worm," an in-depth account of the November Internet infection. The author found the worm's crypt algorithm a frustrating, yet engaging, puzzle.
Efficient decoding of prefix codes
Authors: Hirschberg Daniel S. , Lelewer Debra A.
Published: July 2002

A special case of the data compression problem is presented, in which a powerful encoder transmits a coded file to a decoder that has severely constrained memory. A data structure that achieves minimum storage is presented, and alternative methods that sacrifice a small amount of storage to attain faster decoding are described.
Genetic Diversity in Hominoid Primates
Authors: Ruvolo M.
Published: July 2002

Humans are only one of the species produced by the hominoid evolutionary radiation. Common and pygmy chimpanzees (our closest relatives), gorillas, orangutans, and the lesser apes also belong to this group. In humans, patterns of genetic variation are becoming increasingly better characterized by modern molecular methods. Understanding human variation in an evolutionary context, however, requires comparison of human patterns with those of other hominoids, to reveal features shared among hominoids and those unique to humans. Genetic variation among chimpanzees, gorillas, and orangutans is beginning to be characterized, so that comparisons are now possible.

From genetic data, several different kinds of information can be reconstructed, including the evolutionary relatedness of subspecies and populations, time estimates for evolutionary divergences, past population dynamics, extent of gene flow over geographical landscapes, and group social structure. Knowledge of hominoid genetic variation is also relevant to applied fields such as primate conservation and medicine.
Into the Light: The Origin of Anthropoidea
Authors: Ross Callum F.
Published: July 2002

▪ Abstract  Anthropoidea is a clade of primates including Platyrrhini and Catarrhini. Definitive fossil anthropoids include the early Oligocene Propliopithecidae and the late Eocene–early Oligocene Parapithecidae and Oligopithecidae. Middle Eocene Eosimiidae are probable fossil anthropoids from Asia. Relationships of anthropoids to other primates are debated, although parsimony argues for a tarsier-anthropoid clade (Haplorhini) arising within omomyiforms. Distinctive features of the anthropoid visual system related to diurnality include highly convergent orbits, small corneal diameter/posterior nodal distance, high concentrations of cones and ganglion cells, and extreme magnification of foveal and parafoveal regions of the visual field in the visual cortex. Anthropoid origins was associated with a shift from a nocturnal visually predatory ancestor to diurnal visual predation at small body size (<100 g). This shift may have occurred in the stem lineage of the tarsier-anthropoid clade. The early anthropoids were insectivore-frugivores with unfused mandibular symphyses, small brains, and either dichromatic or trichromatic vision. The evolution of larger brains, symphyseal fusion, and definitive trichromacy occurred later in anthropoid evolution.
PLANT CELL WALL PROTEINS
Authors: Cassab Gladys I.
Published: July 2002

▪ Abstract  The nature of cell wall proteins is as varied as the many functions of plant cell walls. With the exception of glycine-rich proteins, all are glycosylated and contain hydroxyproline (Hyp). Again excepting glycine-rich proteins, they also contain highly repetitive sequences that can be shared between them. The majority of cell wall proteins are cross-linked into the wall and probably have structural functions, although they may also participate in morphogenesis. On the other hand, arabinogalactan proteins are readily soluble and possibly play a major role in cell-cell interactions during development. The interactions of these proteins between themselves and with other wall components is still unknown, as is how wall components are assembled. The possible functions of cell wall proteins are suggested based on repetitive sequence, localization in the plant body, and the general morphogenetic pattern in plants.
COMPACT GROUPS OF GALAXIES
Authors: Hickson Paul
Published: July 2002

▪ Abstract  Compact groups of galaxies have posed a number of challenging questions. Intensive observational and theoretical studies are now providing answers to many of these and, at the same time, are revealing unexpected new clues about the nature and role of these systems. Most compact groups contain a high fraction of galaxies having morphological or kinematical peculiarities, nuclear radio and infrared emission, and starburst or active galactic nuclei (AGN) activity. They contain large quantities of diffuse gas and are dynamically dominated by dark matter. They most likely form as subsystems within looser associations and evolve by gravitational processes. Strong galaxy interactions result and merging is expected to lead to the ultimate demise of the group. Compact groups are surprisingly numerous and may play a significant role in galaxy evolution.
Frequency Allocation: The First Forty Years
Authors: Robinson Brian
Published: July 2002

▪ Abstract  In 1960 ICSU set up an Inter-Union Commission (IUCAF) on the Allocation of Frequencies for Space Research and Radio Astronomy, to keep key parts of the radio spectrum clear for passive, scientific use. IUCAF represents URSI, IAU and COSPAR at World Radio Conferences (WRCs) convened by the International Telecommunications Union (ITU) in Geneva; the WRCs establish the international law which governs users of the radio spectrum. This review recounts many serious threats posed to passive scientific research by commercial and military operations, particularly those involving radio emissions from aircraft and spacecraft. The continual conflict between commercial greed and scientific curiosity has often put the future of radio astronomy, space research, and earth exploration in jeopardy. The conflict increases as we move into the Information Age.
Structural Mechanism of Muscle Contraction
Authors: Geeves M. A. , Holmes K. C.
Published: July 2002

▪ Abstract  X-ray crystallography shows the myosin cross-bridge to exist in two conformations, the beginning and end of the “power stroke.” A long lever-arm undergoes a 60° to 70° rotation between the two states. This rotation is coupled with changes in the active site (OPEN to CLOSED) and phosphate release. Actin binding mediates the transition from CLOSED to OPEN. Kinetics shows that the binding of myosin to actin is a two-step process which affects ATP and ADP affinity. The structural basis of these effects is not explained by the presently known conformers of myosin. Therefore, other states of the myosin cross-bridge must exist. Moreover, cryoelectronmicroscopy has revealed other angles of the cross-bridge lever arm induced by ADP binding. These structural states are presently being characterized by site-directed mutagenesis coupled with kinetic analysis.
The Road Less Traveled: Emerging Principles of Kinesin Motor Utilization
Authors: Goldstein Lawrence S. B. , Philp Alastair Valentine
Published: July 2002

▪ Abstract  Proteins of the kinesin superfamily utilize a conserved catalytic motor domain to generate movements in a wide variety of cellular processes. In this review, we discuss the rapid expansion in our understanding of how eukaryotic cells take advantage of these proteins to generate force and movement in diverse functional contexts. We summarize several recent examples revealing that the simplest view of a kinesin motor protein binding to and translocating a cargo along a microtubule track is inadequate. In fact, this paradigm captures only a small subset of the many ways in which cells harness force production to the generation of intracellular movements and functions. We also highlight several situations where the catalytic kinesin motor domain may not be used to generate movement, but instead may be used in other biochemical and functional contexts. Finally, we review some recent ideas about kinesin motor regulation, redundancy, and cargo attachment strategies.
Settlement of Marine Organisms in Flow
Authors: Abelson Avigdor , Denny Mark
Published: July 2002

A feature common to many benthic marine plants and animals is the release of propagules that serve as the organism's only mechanism of dispersal. Successful dispersal depends to a large extent on the process of settlement—the transient phase between the pelagic life of the propagule and the benthic existence of the adult. The flow of water may affect settlement on three levels: 1. Flow can act by exerting hydrodynamic forces on settling propagules. These forces may affect the propagule's encounter with the substratum, its behavior following encounter, or both. 2. Flow may provide a settlement cue that induces active behavior of motile propagules. 3. Flow may act to mediate various settlement cues (e.g. sediment load and the concentration of attractants). We discuss these three levels of flow effects as a means of examining the potential importance of flow in the settlement process, and then we explore the ecological consequences of settlement in different flow-regimes in light of the direct effects of flow and flow-derived factors.
FUTURE TECHNOLOGIES FOR ENERGY-EFFICIENT IRON AND STEEL MAKING
Authors: de Beer Jeroen , Worrell Ernst , Blok Kornelis
Published: July 2002

▪ Abstract  Techniques for the reduction of the specific energy consumption for iron and steel making are identified and characterized to assess the potential for future energy-efficiency improvement and research and development priorities. Worldwide average specific energy consumption for steel making is estimated to be 24 GJ/tonne. The most energy-efficient process requires 19 GJ/tonne for primary steel and 7 GJ/tonne for secondary steel. Seven specific smelting reduction processes and four groups of near-net-shape casting techniques are described and evaluated. In the longer term, the specific energy consumption for making steel from iron ore can be reduced to 12.5 GJ of primary steel per tonne. A further reduction of up to 2.5 GJ of crude steel per tonne may be achieved when techniques are developed that can recover and apply heat from the hot steel at a high temperature. The specific energy consumption for secondary steel making can be reduced to 3.5 GJ/tonne by energy-efficient melting and shaping techniques.
METHYL tert-BUTYL ETHER AS A GASOLINE OXYGENATE: Lessons for Environmental Public Policy
Authors: Erdal Serap , Goldstein Bernard D.
Published: July 2002

▪ Abstract  We assess the environmental health impact and policy implications of the widespread addition of methyl tert-butyl ether (MTBE) as a chemical that is used as an oxygenate to much of the gasoline supply in the United States. Initial concerns about short-term and long-term adverse health consequences following the substantial increase in MTBE use in the winter of 1992–1993 have been supplemented by the discovery in 1996 of what is now relatively widespread contamination of groundwater. We identify 14 governmental initiatives during the 10-year period 1989–1999 in which the potential adverse consequences of MTBE were considered and a nearly identical research agenda was proposed. The lessons from the ongoing MTBE episode show that: (a) research should precede rather than follow environmental health policy decisions; (b) the extent of potential human and environmental exposure should be an important criterion in determining the amount of information needed before making an environmental policy decision; (c) a better understanding of nonspecific human symptoms associated with environmental exposures is needed; (d) the boundaries between the US Environmental Protection Agency program offices should be as porous as the boundaries between environmental media; (e) the US Environmental Protection Agency needs to focus more on public health rather than on legal approaches to environmental management; (f) it is more difficult to remove a chemical once it is in commerce than it is to prevent its use; (g) resolution of uncertainty is best accomplished through research rather than through repetitive review; and (h) better tools are needed to evaluate risk/risk trade-offs. The ongoing replacement of MTBE by other, less well studied oxygenates such as tertiary amyl methyl ether indicates that these environmental public policy lessons have not been learned.