Theses and Dissertations
Permanent URI for this collectionhttp://ir.daiict.ac.in/handle/123456789/1
Browse
7 results
Search Results
Item Open Access Exact algorithm for segment based sequence alignment(Dhirubhai Ambani Institute of Information and Communication Technology, 2015) Tailor, Divyesh; Divakaran, SrikrishnanIn bioinformatics, proteins, large biological molecules consisting long chain of amino acids, are described by a sequence of 20 amino acids. To analyze these protein sequences pairwise alignment is being used, which identify regions of similarity that may be a result of structural, functional and/or evolutionary relationship between them. Traditional pairwise alignment algorithms work on residue level; it does not account structural or functional information that protein carries. A new approach for protein sequence analysis is being proposed here, pairwise alignment of two protein sequences based on segments. Segments of the sequences can be formed on the basis of protein feature, i.e., functional sites or secondary structure of the protein. Each segment carries a type and weight for the alignment process. Algorithm should align two sequences such that segments with weight higher than threshold value must align with the similar type of segment and score for the alignment must be maximal for given scoring function. Here, we are proposing a generic framework to understand, explore and experiment proteins based on their features, i.e. structure, function, and evolution.Item Open Access Disparity estimation by stereo using particle swarm optimization and graph cuts(Dhirubhai Ambani Institute of Information and Communication Technology, 2010) Nahar, Sonam; Joshi, Manjunath V.Stereo vision is based on the process of obtaining the disparity from a left and a right view of a scene. By obtaining the disparity, we find the distance (depth) of each object point from the camera so that we can construct a 3-D form of a scene. A disparity map indicates the depth of the scene at various points. In this thesis we first discuss the local window based approaches like correlation window and adaptive window for finding the disparity map. These local approaches perform well in highly textured regions, non repetitive and in irregular patterns. However they produce noisy disparities in texture less region and fail to account for occluded areas. We then discuss the particle swarm optimization and graph cuts as global optimization techniques as the tools to obtain better estimates for the disparity map. These algorithms make smoothness assumption explicitly and solve the problem by minimizing the specified energy function. Particle swarm optimization, a bio inspired optimization technique is simple to implement but has high time complexity whereas graph cuts converges very fast yielding better estimates. In this thesis, we use rectified stereo pairs. This reduces the correspondence search to 1-D. To demonstrate the effectiveness of the algorithms, the experimental results from the stereo pairs including the ones with ground truth values for quantitative comparison is presented. Our results show that the disparity estimated using the graph cuts minimization performs better than the particle swarm optimization and local window based approaches in terms of quantitative measures with fast convergence.Item Open Access Path complexity of the class binary search tree(Dhirubhai Ambani Institute of Information and Communication Technology, 2009) Doshi, Nishant; Amin, Ashok T.Path complexity of a program is defined as the number of program execution paths as a function of input size n. This notion of program complexity has been extended to complexity of a class as follows. Class had data members and data operations. The notion of state for the class is defined based on structural representation of a class. We are assuming only those data operations that change state of a class. The path complexity of a class is defined to be the number of valid input sequences, each of them containing n data operations. We have analyzed the path complexity of the class Binary Search Tree (BST) based on the algorithms for insert and delete data operations. Later we modify program for delete operation to facilitate determination of path complexity for the class BST. The bounds for the path complexity of the class BST are determined. A program is developed to obtain path complexity of the class BST.Item Open Access Path complexity of maximum segment sum problem(Dhirubhai Ambani Institute of Information and Communication Technology, 2009) Mishra, Devesh; Amin, Ashok T.Various software complexity metrics have been proposed in literature. A program complexity measure called path complexity is proposed in [1]. Path complexity P(A,n) of an algorithm A is defined to be the number of program execution paths of A over all inputs of size n. It defines a partition of input space of program A into equivalence classes on the basis of different program execution paths. All the inputs belonging to an equivalence class are equivalent to each other in a sense that they follow same execution path. We present path complexity analysis of four different algorithms for one-dimensional maximum segment sum problem which shows that algorithms with different computational complexity may be equivalent to each other in their path complexity. We also present lower bounds on one dimensional as well as two dimensional maximum segment-sum problems. A different perspective and several observations on one dimensional problem are givenItem Open Access On size balanced binary search trees(Dhirubhai Ambani Institute of Information and Communication Technology, 2009) Kumar, Anand; Amin, Ashok T.History independent data structures are useful when security and privacy are of primary concern. Even if an adversary gets copy of the data structure, he cannot obtain any additional information beyond its content. Important property of history independent data structure is that it has no trace visible in its memory layout about the history of operations performed on it. Buchbinder and Petrank [7] in their paper provided lower bounds for obtaining the Strong History Independence for large class of data structures. They also proposed complementary upper bounds for comparison based models and gave an implementation of Weakly History Independent Heap Abstract data structure. In the paper “A Short Note on Perfectly Balance Binary Tree” by A. P. Korah and M. R. Kaimal [14] an algorithm for insertion of a node in a perfectly balanced binary search tree is presented in which successive data displacement is performed in an inorder fashion to keep the binary tree size balanced. This algorithm has worst case performance linear with the number of nodes in the tree. Binary search tree is a very useful data structure and is used in many applications such as dictionary, priority queue and supports many operations, such as SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE. Balanced binary trees such as height balanced binary trees, weight balanced binary trees, etc. support these operations in O (lg n) time in worst-case. Size balanced binary search tree is a balanced binary tree in which number of nodes in one subtree cannot exceed by one than the number of nodes in the other sub tree at every node in the tree. In this thesis, Characterizing Size Balanced Binary Search Tree (SB-BST), I determine the number of Size Balanced Binary Search Trees of a given size. I also provide algorithms to insert into and to delete a node from an SB-BST. Delete operation is followed by Maintain in order to maintain the size balance of Binary Search Tree. These operations require O (n) worst-case run time.Item Open Access Efficient ASIC implementation of advanced encryption standard(Dhirubhai Ambani Institute of Information and Communication Technology, 2008) Joshi, Ashwini Kumar; Nagchoudhuri, DipankarIn spite of the many defense techniques, software vulnerabilities like buffer overflow, format string vulnerability and integer vulnerability is still exploited by attackers. These software vulnerabilities arise due to programming mistakes which allows security bugs to be exploited. Buffer overflow occurs when buffer is given more data than the capacity of it. Format string vulnerability arises when data supplied by attacker is passed to formatting functions as format string argument. Integer vulnerability occurs when program evaluates an integer to unexpected value due to integer overflows, underflows, truncation errors or signed conversion errors. The hardware based solution called tagged architecture protects a system against mentioned vulnerabilities. In tagged architecture, each memory byte is appended with one tag bit to mark data that comes from I/O. Whenever I/O supplied data is used to transfer control of a system or to access memory, an alert is raised and program is terminated. This thesis proposes a weakness of tagged architecture by finding false positives and false negatives on it. It also proposes the improvements to the tagged architecture to avoid found false positives on it. The prototype implementation of improved tagged architecture is done in SimpleScalar simulator. The SimpleScalar simulator is a architectural simulator. The security evaluation is done for tagged architecture and improved tagged architecture through benchmarks and synthetic vulnerable programs.Item Open Access Embedding binary trees and caterpillars into the hypercube(Dhirubhai Ambani Institute of Information and Communication Technology, 2008) Srivastava, Abhishek; Sunitha, V.Embedding graphs is an important and well-studied theory in parallel computing. Finding the embedding of trees into hypercubes is an important, interesting and difficult problem. This work studies the embedding of binary trees and caterpillars into hypercubes. We give an embedding for a special type of binary tree into its optimal hypercube. We also present embedding of generalized ladders as subgraph into the hypercube. Through an embedding of caterpillars into generalized ladders, we have obtained an embedding of a class of caterpillars into their optimal hypercube.