Recursos de colección

ETD at Indian Institute of Science (3.216 recursos)

Repository of Theses and Dissertations of Indian Institute of Science, Bangalore, India. The repository has been developed to capture, disseminate and preserve research theses of Indian Institute of Science.

Computer Science and Automation (csa)

Mostrando recursos 1 - 20 de 135

  1. Identification and Quantification of Important Voids and Pockets in Proteins

    Raghavendra, G S
    Many methods of analyzing both the physical and chemical behavior of proteins require information about its structure and stability. Also various other parameters such as energy function, solvation, hydrophobic/hydrophilic effects, surface area and volumes too play an important part in such analysis. The contribution of cavities to these parameters are very important. Existing methods to compute and measure cavities are limited by the inherent inaccuracies in the method of acquisition of data through x-ray crystallography and uncertainities in computation of radii of atoms. We present a topological framework that enables robust computation and visualization of these structures. Given a fixed...

  2. Transducer-based Algorithmic Verification of Retransmission Protocols over Noisy Channels

    Thakkar, Jay
    Unreliable communication channels are a practical reality. They add to the complexity of protocol design and verification. In this work, we consider noisy channels which can corrupt messages. We present an approach to model and verify protocols which combine error detection and error control to provide reliable communication over noisy channels. We call these protocols retransmission protocols as they achieve reliable communication through repeated retransmissions of messages. These protocols typically use cyclic redundancy checks and sliding window protocols for error detection and control respectively. We propose models of these protocols as regular transducers operating on bit strings. Deterministic streaming string...

  3. Rainbow Colouring and Some Dimensional Problems in Graph Theory

    Rajendraprasad, Deepak
    This thesis touches three different topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices is connected by atleast one path in which no two edges are coloured the same. The rainbow connection number of a graph is the minimum number of colours required to rainbow colour it. In this thesis we give upper bounds on rainbow connection number based on graph invariants like minimum degree, vertex connectivity, and radius. We also give some computational complexity results for special graph classes. Product dimension...

  4. Constructing Provably Secure Identity-Based Signature Schemes

    Chethan Kamath, H
    An identity-based cryptosystem (IBC) is a public-key system where the public key can be represented by any arbitrary string such as an e-mail address. The notion was introduced by Shamir with the primary goal of simplifying certificate management. An identity-based signature(IBS) is the identity-based counter part of a digital signature. In the first (and primary) part of the work, we take a closer look at an IBS due to Galindo and Garcia–GG-IBS, for short. GG-IBS is derived through a simple and elegant concatenation of two Schnorr signatures and, importantly, does not rely on pairing. The security is established through two algorithms...

  5. A Theoretical Study of the Synergy and Lazy Annotation Algorithms

    Jayaram, Sampath
    Given a program with assertions, the assertion checking problem is to tell whether there is an execution of the program that violates one of the assertions. One approach to this problem is to explore different paths towards assertion violations, and to learn “blocking” conditions whenever a path is blocked from reaching the violations. The Synergy algorithm of Gulavani et al. [FSE 2006] and the Lazy Annotation algorithm of McMillan [CAV2010] are two recent algorithms that follow this approach to assertion checking. Each technique has its own advantages. Synergy uses concrete tests which are very cheap as compared to theorem prover calls....

  6. Investigations on CPI Centric Worst Case Execution Time Analysis

    Ravindar, Archana
    Estimating program worst case execution time (WCET) is an important problem in the domain of real-time systems and embedded systems that are deadline-centric. If WCET of a program is found to exceed the deadline, it is either recoded or the target architecture is modified to meet the deadline. Predominantly, there exist three broad approaches to estimate WCET- static WCET analysis, hybrid measurement based analysis and statistical WCET analysis. Though measurement based analyzers benefit from knowledge of run-time behavior, amount of instrumentation remains a concern. This thesis proposes a CPI-centric WCET analyzer that estimates WCET as a product of worst case...

  7. Improving the Precision of a Scalable Demand-Driven Null- Dereference Verification for Java

    Margoor, Amogh
    The problem addressed in this thesis is sound, scalable, demand-driven null-dereference verification for Java programs via over-approximated weakest preconditions analysis. The base version of this analysis having been described in a previous publication, in this thesis we focus primarily on describing two major optimizations that we have incorporated that allow for longer program paths to be traversed more efficiently, hence increasing the precision of the approach. The first optimization is to bypass certain expensive-to-analyze constructs, such as virtual calls with too many possible targets, by directly transferring dataflow facts from points after the construct to points before along def-use edges...

  8. Reconstruction of 3D Neuronal Structures

    Kumar, Kanuj
    Microscopic analysis of biological structures can be significantly enhanced by representing the object of study as a three-dimensional entity. To assist neurobiologists investigate the molecular mechanisms involved in neurite formation requires an adequate visual model or at least some measurable data. Reconstruction helps analysis of biological structures by representing the object of study as a three-dimensional entity. It helps gain insight into the morphological variation observed in each class of neurons and for simulations of neuronal behavior. To perform the reconstruction, biologists today have to rely on time-consuming manual or semi-manual methods which either doesn't exhibit robustness against noise of...

  9. Construction of Secure and Efficient Private Set Intersection Protocol

    Kumar, Vikas
    Private set intersection(PSI) is a two party protocol where both parties possess a private set and at the end of the protocol, one party (client) learns the intersection while other party (server) learns nothing. Motivated by some interesting practical applications, several provably secure and efficient PSI protocols have appeared in the literature in recent past. Some of the proposed solutions are secure in the honest-but-curious (HbC) model while the others are secure in the (stronger) malicious model. Security in the latter is traditionally achieved by following the classical approach of attaching a zero knowledge proof of knowledge (ZKPoK) (and/or using...

  10. An Optimizing Code Generator for a Class of Lattice-Boltzmann Computations

    Pananilath, Irshad Muhammed
    Lattice-Boltzmann method(LBM), a promising new particle-based simulation technique for complex and multiscale fluid flows, has seen tremendous adoption in recent years in computational fluid dynamics. Even with a state-of-the-art LBM solver such as Palabos, a user still has to manually write his program using the library-supplied primitives. We propose an automated code generator for a class of LBM computations with the objective to achieve high performance on modern architectures. Tiling is a very important loop transformation used to improve the performance of stencil computations by exploiting locality and parallelism. In the first part of the work, we explore diamond tiling, a...

  11. Parameterized Complexity of Maximum Edge Coloring in Graphs

    Goyal, Prachi
    The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints. We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to...

  12. A Systems Perspective of Software Runtime Bloat - Origin, Mitigation and Power-Performance Implications

    Bhattacharya, Suparna
    Large flexible software systems tend to incur “bloat”, here defined as the runtime overhead induced by the accumulation of excess functionality and objects. Removing bloat is hard as these overheads are a side-effect of the same trends that have fuelled software growth. Even defining and measuring bloat is non-trivial, as software doesn’t come with built-in labels that indicate which portions of computation are necessary for a given application and which lead to bloat. Much progress has been made in novel analysis tools that aid (human experts in) the process of finding bloat by highlighting signs of excessive activity and data...

  13. Online Learning and Simulation Based Algorithms for Stochastic Optimization

    Lakshmanan, K
    In many optimization problems, the relationship between the objective and parameters is not known. The objective function itself may be stochastic such as a long-run average over some random cost samples. In such cases finding the gradient of the objective is not possible. It is in this setting that stochastic approximation algorithms are used. These algorithms use some estimates of the gradient and are stochastic in nature. Amongst gradient estimation techniques, Simultaneous Perturbation Stochastic Approximation (SPSA) and Smoothed Functional(SF) scheme are widely used. In this thesis we have proposed a novel multi-time scale quasi-Newton based smoothed functional (QN-SF) algorithm for...

  14. Automatic Storage Optimization of Arrays Affine Loop Nests

    Bhaskaracharya, Somashekaracharya G
    Efficient memory usage is crucial for data-intensive applications as a smaller memory footprint ensures better cache performance and allows one to run a larger problem size given a axed amount of main memory. The solutions found by existing techniques for automatic storage optimization for arrays in a new loop-nests, which minimize the storage requirements for the arrays, are often far from good or optimal and could even miss nearly all storage optimization potential. In this work, we present a new automatic storage optimization framework and techniques that can be used to achieve intra-array as well as inter-array storage reuse within...

  15. Reeb Graphs : Computation, Visualization and Applications

    Harish, D
    Level sets are extensively used for the visualization of scalar fields. The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. It is obtained by mapping each connected component of a level set to a point. The Reeb graph and its loop-free version called the contour tree serve as an effective user interface for selecting meaningful level sets and for designing transfer functions for volume rendering. It also finds several other applications in the field of scientific visualization. In this thesis, we focus on designing algorithms for efficiently computing the Reeb graph of...

  16. Designing Energy-Aware Optimization Techniques through Program Behaviour Analysis

    Kommaraju, Ananda Varadhan
    Green computing techniques aim to reduce the power foot print of modern embedded devices with particular emphasis on processors, the power hot-spots of these devices. In this thesis we propose compiler-driven and profile-driven optimizations that reduce power consumption in a modern embedded processor. We show that these optimizations reduce power consumption in functional units and memory subsystems with very low performance loss. We present three new techniques to reduce power consumption in processors, namely, transition aware scheduling, leakage reduction in data caches using criticality analysis, and dynamic power reduction in data caches using locality analysis of data regions. A novel...

  17. Bayes Optimal Feature Selection for Supervised Learning

    Saneem Ahmed, C G
    The problem of feature selection is critical in several areas of machine learning and data analysis such as, for example, cancer classification using gene expression data, text categorization, etc. In this work, we consider feature selection for supervised learning problems, where one wishes to select a small set of features that facilitate learning a good prediction model in the reduced feature space. Our interest is primarily in filter methods that select features independently of the learning algorithm to be used and are generally faster to implement compared to other types of feature selection algorithms. Many common filter methods for feature...

  18. Variants and Generalization of Some Classical Problems in Combinatorial Geometry

    Bharadwaj, Subramanya B V
    In this thesis we consider extensions and generalizations of some classical problems in Combinatorial Geometry. Our work is an offshoot of four classical problems in Combinatorial Geometry. A fundamental assumption in these problems is that the underlying point set is R2. Two fundamental themes entwining the problems considered in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’...

  19. Hitting Geometric Range Spaces using a Few Points

    Ashok, Pradeesha
    A range space (P, S) consists of a set P of n elements and a collection S = {S1,...,Sm} of subsets of P , referred to as ranges. A hitting set for this range space refers to a subset H of P such that every Si in S contains at least one element of H. The hitting set problem is studied for many geometric range spaces where P is a set of n points in Rd and the ranges are defined by the intersection of geometric objects with P . The algorithmic question of finding the minimum-sized hitting set for...

  20. Effective Automatic Computation Placement and Data Allocation for Parallelization of Regular Programs

    Chandan, G
    Scientific applications that operate on large data sets require huge amount of computation power and memory. These applications are typically run on High Performance Computing (HPC) systems that consist of multiple compute nodes, connected over an network interconnect such as InfiniBand. Each compute node has its own memory and does not share the address space with other nodes. A significant amount of work has been done in past two decades on parallelizing for distributed-memory architectures. A majority of this work was done in developing compiler technologies such as high performance Fortran (HPF) and partitioned global address space (PGAS). However, several...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.