Now showing items 1-5 of 5

    • Computing Partitions with Applications to the Knapsack Problem 

      Horowitz, Ellis; Sahni, Sartaj (Cornell University, 1972-07)
      Given $r$ numbers $s_{1}, \ldots, s_{r}$, algorithms are investigated for finding all possible combinations of these numbers which sum to $M$. This problem is a particular instance of the 0-1 unidimensional knapsack problem. ...
    • On Computing the Determinant of Matrices with Polynomial Entries 

      Horowitz, Ellis; Sahni, Sartaj (Cornell University, 1973-07)
      We consider the problem of computing the determinant of a matrix of polynomials. Four algorithms are compared: expansion by minors, Gaussian elimination over the integers, a method based on evaluation and interpolation, ...
    • On the Computation of Powers of a Class of Polynomials 

      Horowitz, Ellis; Sahni, Sartaj (Cornell University, 1972-08)
      A general class of polynomials is defined which includes as subcases sparse and dense polynomials. For any polynomial $P$ within this class a host of algorithms are analyzed for computing $P^{n}$. While the Homomorphism ...
    • On the Computational Complexity of Scheme Equivalence 

      Constable, Robert L.; Hunt, Harry B., III; Sahni, Sartaj (Cornell University, 1974-03)
      We consider the computational complexity of several decidable problems about program schemes and simple programming languages. In particular, we show that the equivalence problem for Ianov schemes is NP-complete, but ...
    • Some Related Problems from Network Flows, Game Theory and Integer Programming 

      Sahni, Sartaj (Cornell University, 1972-07)
      We consider several important problems for which no polynomially time bounded algorithm is known. These problems are shown to be related in that a polynomial algorithm for one implies a polynomial algorrithm for the others.