JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Sahni, Sartaj"
Now showing items 15 of 5

Computing Partitions with Applications to the Knapsack Problem
Horowitz, Ellis; Sahni, Sartaj (Cornell University, 197207)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 01 unidimensional knapsack problem. ... 
On Computing the Determinant of Matrices with Polynomial Entries
Horowitz, Ellis; Sahni, Sartaj (Cornell University, 197307)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, 197208)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, 197403)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 NPcomplete, but ... 
Some Related Problems from Network Flows, Game Theory and Integer Programming
Sahni, Sartaj (Cornell University, 197207)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.