Theses and Dissertations

Permanent URI for this collectionhttp://ir.daiict.ac.in/handle/123456789/1

Browse

Has files: YesSubject: search.filters.subject.Computational complexity

Search Results

Now showing 1 - 6 of 6
  • Thumbnail Image
    ItemOpen Access
    Comparative Study: Neural Networks on MCUs at the Edge
    (2021) Anand, Harshita; Bhatt, Amit
    Computer vision has evolved excessively over the years, the sizes of the processor and camera shrinking, rising the computational complexity and power and also becoming affordable, making it achievable to be integrated onto embedded systems. It has several critical applications that require a Huge accuracy and vast real-time response in order to achieve a good user experience. The Neural network (NN) poses as an attractive choice for embedded vision architectures due to their superior performance and better accuracy in comparison to the traditional processing algorithms. Due to the security and latency issues which make larger systems unattractive for certain time-dependent applications, we require an always-on system; this application has a highly constrained power budget and needs to be typically run on tiny microcontroller systems having limited memory and compute capability. The NN design model must consider these above constraints. We have performed NN model explorations and evaluated the embedded vision applications including person detection, object detection, image classifications, and facial recognition on resource-constrained microcontrollers. We trained a variety of neural network architectures present in the literature, comparing their accuracies and memory/compute requirements. We present the possibility of optimizing the NN architectures in a way for them to be able to fit among the computational and memory criteria for the microcontroller systems without salvaging the accuracy. We also delve into the concepts of the depth-wise separable convolutional neural network (DS-CNN) and convolutional neural network (CNN) both of which are utilized in MobileNet Architecture. This thesis aims to present a comparative analysis based on the performance of edge devices in the field of embedded computer vision. The three parameters under major focus are latency, accuracy, and million operations, in this study.
  • Thumbnail Image
    ItemOpen Access
    Algebraic approach to Nash equilibria for finite normal form games
    (Dhirubhai Ambani Institute of Information and Communication Technology, 2011) Gandhi, Ratnik; Chatterji, Samaresh
    In this work we consider methods for computing Nash equilibria of finite normal form games that emphasize use of polynomial algebra. Nash equilibria of a game can be characterized as solutions to a system of polynomial equations that we call the game system (GS). We adopt this characterization of Nash equilibria and apply polynomial algebra as a computational framework. Our work is concerned with finding all Nash equilibria given a single equilibrium (a sample equilibrium), without repeating the solution procedure for the sample equilibrium. In the present work we consider two subclasses of finite normal form games. The class of rational payoff irrational equilibria(RPIE) games consists of the games where all the game payooff values are rational numbers while all equilibria are irrational number tuples. The class of integer payooff irrational equilibria (IPIE) games is defined similarly. The main emphasis in our work is algorithmic. We develop in detail two major algorithms required for each of the classes under consideration: a membership algorithm and an equilibria computation algorithm. We develop in detail the underlying computational techniques from polynomial algebra, and present proofs of their correctness. We compare these techniques with other algorithms and discuss their computational complexity. We also discuss approaches for constructing examples of these classes of games. Our overall philosophy is to exploit the following: Galois groups of univariate polynomials in the ideal I of GS and a single sample solution of the GS. We use group action by Galois groups on a sample solution to extend our knowledge about the remaining solutions of the GS, which include all the Nash equilibria. The primary setting of our work remains Galois theory over the field of rational numbers. As we progress to IPIE games, we use the more generalized Galois theory over commutative rings. Accordingly, several subsidiary results of an essentially algebraic nature are derived in the course of our development. We also briefly consider the possibility of games over finite fields. For the problem of computing all the Nash equilibria of the classes of games, we present two separate but similar algorithms for RPIE and IPIE games. The algorithms work in two phases: computation of a sample solution of the GS, followed by computation of Nash equilibria using the Galois group action. For RPIE games, in the first phase, computation of a sample solution is carried out by identifying a Grobner basis for the ideal I of the GS, while the same computation for another algorithm for IPIE games is performed with multivariate Newton Raphson method(MVNRM). The next phase { that of computing all other solutions { involves application of the Galois group over a sample solution. However, not all of these solutions correspond to Nash equilibria. Hence we resort to the Nash equilibrium verification algorithm to reject superfluous solutions and retain only the solutions corresponding to Nash equilibria. We derive an important condition on the polynomial ideal I of GS to reduce repeated factorizations and substitutions, further reducing computational complexity of the presented algorithms. Further a condition is derived for computing equilibria of subclasses of games in closed form. We present algorithms that use knowledge of a sample solution to compute other equilibria of the games. The presented methods do not require repeated factorizations and provide exact solutions. The work enables us to use algebraic properties and structure available in the GS of a game. It highlights some important interrelations of the equilibria of a game. The research reported in this work opens up interesting connections between algebraic geometry and game theory, thereby expanding the horizon of the problem of computing equilibria in game theory.
  • Thumbnail Image
    ItemOpen 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.
  • Thumbnail Image
    ItemOpen 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 given
  • Thumbnail Image
    ItemOpen 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.
  • Thumbnail Image
    ItemOpen Access
    On path complexities of heapsort algorithm and the class stack
    (Dhirubhai Ambani Institute of Information and Communication Technology, 2007) Mangal, Anupam; Amin, Ashok T.
    A measure of program complexity, called Path Complexity, based on the number of program execution paths as a function of the input size n, is proposed in [AJ05]. This measure can be used to compare the complexity of two different programs even with isomorphic control flow graphs. Using this measure, we determine the path complexity of the Heapsort algorithm. The notion of path complexity of a program is further extended to introduce the path complexity of a class. In particular, the path complexity of the Stack class is determined. We also provide an upper bound, and a lower bound based on catalan numbers, on the path complexity of the Stack class.