Problems and Algorithms for Sequence Segmentations

The analysis of sequential data is required in many diverse areas such as telecommunications, stock market analysis, and bioinformatics. A basic problem related to the analysis of sequential data is the sequence segmentation problem. A sequence segmentation is a partition of the sequence into a number of non-overlapping segments that cover all data points, such that each segment is as homogeneous as possible. This problem can be solved optimally using a standard dynamic programming algorithm. In the first part of the thesis, we present a new approximation algorithm for the sequence segmentation problem. This algorithm has smaller running time than the optimal dynamic programming algorithm, while it has bounded approximation ratio. The basic idea is to divide the input sequence into subsequences, solve the problem optimally in each subsequence, and then appropriately combine the solutions to the subproblems into one final solution. In the second part of the thesis, we study alternative segmentation models that are devised to better fit the data. More specifically, we focus on clustered segmentations and segmentations with rearrangements. While in the standard segmentation of a multidimensional sequence all dimensions share the same segment boundaries, in a clustered segmentation the multidimensional sequence is segmented in such a way that dimensions are allowed to form clusters. Each cluster of dimensions is then segmented separately. We formally define the problem of clustered segmentations and we experimentally show that segmenting sequences using this segmentation model, leads to solutions with smaller error for the same model cost. Segmentation with rearrangements is a novel variation to the segmentation problem: in addition to partitioning the sequence we also seek to apply a limited amount of reordering, so that the overall representation error is minimized. We formulate the problem of segmentation with rearrangements and we show that it is an NP-hard problem to solve or even to approximate. We devise effective algorithms for the proposed problem, combining ideas from dynamic programming and outlier detection algorithms in sequences. In the final part of the thesis, we discuss the problem of aggregating results of segmentation algorithms on the same set of data points. In this case, we are interested in producing a partitioning of the data that agrees as much as possible with the input partitions. We show that this problem can be solved optimally in polynomial time using dynamic programming. Furthermore, we show that not all data points are candidates for segment boundaries in the optimal solution.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Natural convection in rectangular cavities at high Rayleigh number

Natural convection in rectangular two-dimensional cavities with differentially heated side walls is a standard problem in numerical heat transfer. Most of the existing studies has considered the low Ra laminar regime. The general thrust of the present research is to investigate higher Ra flows extending into the unsteady and turbulent regimes where the physics is not fully understood and appropriate models for turbulence are not yet established. In the present study the Boussinesq approximation is being used, but the theoretical background and some preliminary results have been obtained[1] for flows with variable properties.

Time-dependent flows of rotating and stratified fluids in geometries with non-uniform cross-sections

Unsteady rotating and stratified flows in geometries with non-uniform cross-sections are investigated under Oseen approximation using Laplace transform technique. The solutions are obtained in closed form and they reveal that the flow remains oscillatory even after infinitely large time. The existence of inertial waves propagating in both positive and negative directions of the flow is observed. When the Rossby or Froude number is close to a certain infinite set of critical values the blocking and back flow occur and the flow pattern becomes more and more complicated with increasing number of stagnant zones when each critical value is crossed. The analogy that is observed in the solutions for rotating and stratified flows is also discussed.

Transient response of coupled non-linear non-conservative systems

This paper deals with an approximate method of analysis of non-linear, non-conservative systems of two degrees of freedom. The approximate equations for amplitude and phase are obtained by a generalized averaging technique based on the ultraspherical polynomial approximation. The method is illustrated by an example of a spring-mass-damper system.

Approximate solution for the redistribution of impurities during second oxidation

The impurity profile for the second oxidation, used in MOST fabrication, has been obtained by Margalit et al. [1]. The disadvantage of this technique is that the accuracy of their solution is directly dependent on the computer time. In this article, an analytical solution is presented using the approximation of linearizing the second oxidation procedure.

Ising ferromagnet with biquadratic exchange

A spin one Ising system with biquadratic exchange, is investigated, using Green's function technique in random phase approximation (RPA). Transition temperature Tc and <(Sz)2> at Tc, are found to increase with biquadratic exchange parameter α for sc, bcc and fcc lattices. The variation of <(Sz)2> at Tc with α is found to be the same for the above lattices.

Study of third-order non-linear systems- Variation of parameters approach

In this paper, the transient response of a third-order non-linear system is obtained by first reducing the given third-order equation to three first-order equations by applying the method of variation of parameters. On the assumption that the variations of amplitude and phase are small, the functions are expanded in ultraspherical polynomials. The expansion is restricted to the constant term. The resulting equations are solved to obtain the response of the given third-order system. A numerical example is considered to illustrate the method. The results show that the agreement between the approximate and digital solution is good thus vindicating the approximation.

Antiferromagnetic spin-wave states in a linear chain with nearest- and next-nearest-neighbour interactions

The spectrum of short-closed chains up to N=12 are studied by exact diagonalization to obtain the spin-wave spectrum of the Hamiltonian H=2J Sigma i=1Nsi.si+1+2J alpha Sigma i=1Nsi.si+2, -1.0approximation (1952). The results of short chains indicate that S=0 bound magnon states lie partly below the spin-wave states with S=1 only for alpha >or=0.3 and alpha

Rotational cut-off and anharmonicity effects on thermodynamic properties of gases at high temperatures

The exact expressions for the partition function (Q) and the coefficient of specific heat at constant volume (Cv) for a rotating-anharmonic oscillator molecule, including coupling and rotational cut-off, have been formulated and values of Q and Cv have been computed in the temperature range of 100 to 100,000 K for O2, N2 and H2 gases. The exact Q and Cv values are also compared with the corresponding rigid-rotator harmonic-oscillator (infinite rotational and vibrational levels) and rigid-rotator anharmonic-oscillator (infinite rotational levels) values. The rigid-rotator harmonic-oscillator approximation can be accepted for temperatures up to about 5000 K for O2 and N2. Beyond these temperatures the error in Cv will be significant, because of anharmonicity and rotational cut-off effects. For H2, the rigid-rotator harmonic-oscillator approximation becomes unacceptable even for temperatures as low as 2000 K.

Modeling ecological and evolutionary processes in spatially structured populations

Many species inhabit fragmented landscapes, resulting either from anthropogenic or from natural processes. The ecological and evolutionary dynamics of spatially structured populations are affected by a complex interplay between endogenous and exogenous factors. The metapopulation approach, simplifying the landscape to a discrete set of patches of breeding habitat surrounded by unsuitable matrix, has become a widely applied paradigm for the study of species inhabiting highly fragmented landscapes. In this thesis, I focus on the construction of biologically realistic models and their parameterization with empirical data, with the general objective of understanding how the interactions between individuals and their spatially structured environment affect ecological and evolutionary processes in fragmented landscapes. I study two hierarchically structured model systems, which are the Glanville fritillary butterfly in the Åland Islands, and a system of two interacting aphid species in the Tvärminne archipelago, both being located in South-Western Finland. The interesting and challenging feature of both study systems is that the population dynamics occur over multiple spatial scales that are linked by various processes. My main emphasis is in the development of mathematical and statistical methodologies. For the Glanville fritillary case study, I first build a Bayesian framework for the estimation of death rates and capture probabilities from mark-recapture data, with the novelty of accounting for variation among individuals in capture probabilities and survival. I then characterize the dispersal phase of the butterflies by deriving a mathematical approximation of a diffusion-based movement model applied to a network of patches. I use the movement model as a building block to construct an individual-based evolutionary model for the Glanville fritillary butterfly metapopulation. I parameterize the evolutionary model using a pattern-oriented approach, and use it to study how the landscape structure affects the evolution of dispersal. For the aphid case study, I develop a Bayesian model of hierarchical multi-scale metapopulation dynamics, where the observed extinction and colonization rates are decomposed into intrinsic rates operating specifically at each spatial scale. In summary, I show how analytical approaches, hierarchical Bayesian methods and individual-based simulations can be used individually or in combination to tackle complex problems from many different viewpoints. In particular, hierarchical Bayesian methods provide a useful tool for decomposing ecological complexity into more tractable components.

Performance reliability of high-maintenance systems

The time–history of the performance of a system is treated as a stochastic corrective process, in which deterioration due to aging is counteracted at brief maintenance checks. Using a diffusion approximation for the deterioration, simple models are proposed for describing maintenance either by component replacement or by performance restoration. Equilibrium solutions of the models show that the performance has a probability distribution with exponential tails: the uncritical use of Gaussians can grossly underestimate the probability of poor performance. The proposed models are supported by recent observational evidence on aircraft track-keeping errors, which are shown to follow the modified exponential distribution derived here. The analysis also brings out the relation between the deterioration characteristics of the system and the intensity of the maintenance effort required to achieve a given performance reliability.

A curve shortening flow rule for closed embedded plane curves with a prescribed rate of change in enclosed area

Motivated by a problem from fluid mechanics, we consider a generalization of the standard curve shortening flow problem for a closed embedded plane curve such that the area enclosed by the curve is forced to decrease at a prescribed rate. Using formal asymptotic and numerical techniques, we derive possible extinction shapes as the curve contracts to a point, dependent on the rate of decreasing area; we find there is a wider class of extinction shapes than for standard curve shortening, for which initially simple closed curves are always asymptotically circular. We also provide numerical evidence that self-intersection is possible for non-convex initial conditions, distinguishing between pinch-off and coalescence of the curve interior.

Ellipsometric study of Atomic Layer Deposited TiO2 thin films

Atomic layer deposition was used to obtain TiO2 thin films on Si (100) and fused quartz, using a novel metal organic precursor. The films were grown at 400 degrees C, varying the amount of oxygen used as the reactive gas. X-ray diffraction showed the films to be crystalline, with a mixture of anatase and rutile phases. To investigate their optical properties, ellipsometric measurements were made in the UV-Vis-NIR range (300-1700 nm). Spectral distribution of various optical constants like refractive index (n), absorption index (k), transmittance (T), reflectance (R), absorption (A) were calculated by employing Bruggemann's effective medium approximation (BEMA) and Maxwell-Garnet effective medium approximation, in conjunction with the Cauchy and Forouhi-Bloomer (FB) dispersion relations. A layered optical model has been proposed which gives the thickness, elemental and molecular composition, amorphicity and roughness (morphology) of the TiO2 film surface and and the film/substrate interface, as a function of oxygen flow rate The spectral distribution of the optical band gap (E-g(opt)), complex dielectric constants (epsilon' and epsilon''), and optical conductivity (sigma(opt)), has also been determined.