M Tech Dissertations
Permanent URI for this collectionhttp://ir.daiict.ac.in/handle/123456789/3
Browse
3 results
Search Results
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.