Our understanding of the functions played by RNA molecules is expanded with the understanding of RNA structures. Except for primary structure, RNA molecules present pairings within a sequence, which is called RNA secondary structure. Since its discovery, RNA secondary structure has drawn considerable attention because it is widely appeared. Many programs for RNA secondary structure prediction have been developed, including [4, 20, 38, 39, 46]. Based on our knowledge, however, there is a family of RNA secondary structure which can not be covered by any of these algorithms. And even without considering this family, none of programs can cover all other structures in Rfam data-set. These structures are found to be important in many biological processes, for example, chromosome maintenance, RNA processing, protein biosynthesis. And efficient structure prediction can give direction for experimental investigations. Here, we present a general algorithm with a new grammar: Vertical Tree Grammar (VTG) which has stochastic context-free grammar architecture for RNA secondary structure prediction. VTG significantly expands the class of structures that can be handled, including all structures that can be covered by other paper, and all structures in Rfam data-set. Our algorithm runs in O(n^6) time, and it's precision is reasonable high, with average sensitivity and specificity over 70%. / published_or_final_version / Computer Science / Master / Master of Philosophy

Job scheduling, which greatly impacts on the system performance, is a fundamental problem in computer science. In this thesis, we study three kinds of scheduling problems, that is, deadline scheduling, due date scheduling, and flow time scheduling. Traditionally, the major concern for scheduling problems is the system performance, i.e. the “Quality of Service" (QoS). Different scheduling problems use different QoS measurements. For deadline scheduling, the most common QoS to optimize is the throughput; for due date scheduling, it is the total quoted lead time; and for flow time scheduling, it is the total (weighted) flow time. Recently, energy efficiency is becoming more and more important. Many modern processors adopt technologies like dynamic speed scaling and sleep management to reduce energy usage. Much work is done on energy efficient scheduling. In this thesis, we study this topic for all three kinds of scheduling mentioned above. Meanwhile, we also revisit the traditional flow time scheduling problem to optimize the QoS. However, we consider the problem in a more realistic model that makes the problem much more challenging. Below is the summary of the problems studied in the thesis. First, we consider the tradeoff between energy and throughput for deadline scheduling. Specifically, each job is associated with a value (or importance) and a deadline. A scheduling algorithm is allowed to discard some of the jobs, and the objective is to minimize total energy usage plus total value of discarded jobs. When processor's maximum speed is unbounded, we propose an O(1)-competitive algorithm. When processor's maximum speed is bounded, we show a strong lower bound and give an algorithm with a competitive ratio close to that lower bound. Second, we study energy efficient due date scheduling. Jobs arrive online with different sizes and weights. An algorithm needs to assign a due date to each job once it arrives, and complete the job by the due date. The quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We propose a competitive algorithm for minimizing the sum of the total quoted lead time and energy usage. Next, we consider flow time scheduling with power management on multiple machines. Jobs with arbitrary sizes and weights arrive online. Each machine consumes different amount of energy when processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage and, meanwhile, guarantee high QoS. Our result is an O(1)-competitive algorithm to minimize total weighted flow time plus energy usage. Finally, we consider the traditional preemptive scheduling to minimize total flow time. Previous theoretical results often assume preemption is free, which is not true for most systems. We investigate the complexity of the problem when a processor has to perform a certain amount of overhead before it resumes the execution of a job preempted before. We first show an Ω(n^(1/4)) lower bound, and then, propose a (1+ε)-speed (1+ 1/ε )-competitive algorithm in resource augmentation model. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Shape representation is a fundamental topic in geometric modeling, which is ubiquitous in computer graphics. Compared with the explicit and implicit shape representations, the medial representation possesses many advantages. It provides a comprehensive understanding of the shapes, since it gives direct access to both the boundaries and the interiors of the shapes. Although there are many medial axis computation algorithms which are able to filter noises in the medial axis, introduced by the perturbations on the boundary, and generate stable medial axis transforms of the input shapes, the medial axis transforms are usually represented in a redundant way with numerous primitives, which brings down the flexibility of the medial axis transform and hinders the popularity of the medial axis transform in geometric applications. In this thesis, we propose compact representations of the medial axis transforms for 2D and 3D shapes. The first part of this thesis proposes a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in the 3D space to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. The second part of this thesis discusses improvements on the existing medial axis computation algorithms, and represent the medial axis transform of a 3D shape in a compact way. The CVT remeshing framework is applied on an initial medial axis transform to promote the mesh quality of the medial axis. The simplified medial axis transform is then optimized by minimizing the approximation error of the shape reconstructed from the medial axis transform to the original 3D shape. Our results on various 2D and 3D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D and 3D shapes. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Not available / text

Not available / text

Not available / text

Not available / text

Not available / text

Not available / text

Not available / text