Files in this item
|(no description provided)|
|Title:||Topics in Combinatorial Algorithms|
|Author(s):||Ramanan, Prakash V.|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Abstract:||The study of algorithm design is of fundamental importance in Computer Science. The study of algorithms includes the study of efficient data structures. This thesis deals with various aspects of combinatorial algorithms and data structures.
An important class of data structures, k-ary trees, is studied. A pair of k-ary tree traversals is used to assign a permutation of the integers 1,2,(' . . .) to each k-ary tree T. A pair of traversals in a k-ary tree Representation Scheme (k-RS), if it does not assign the same permutation to two distinct k-ary trees. Such pairs of traversals are characterized. Some interesting properties of k-RS are also studied.
The computational complexity of a problem is of universal interest, both to algorithm design, and to an understanding of the nature of computation. New algorithms for the selection problem are presented and analyzed. The performance of these algorithms improve over that of previously known algorithms.
The problem of finding the maximal elements of a set of n elements in E('d) is studied. The complexity of the problem as a function of both n, the number of points in the input set, and m, the number of maximal elements of the set, is studied.
Finally, the aspect of NP-Completeness is considered. There are two main approaches that can be fruitful in dealing with NP-Complete problems. The first one is to find efficient algorithms for some special cases of the problem. This approach is followed for a personnel assignment problem. The general assignment problem is shown to be NP-Complete. Efficient algorithms are presented for some special cases of the problem.
The second approach in dealing with NP-complete problems is to look for heuristic or approximation algorithms. This approach is followed for the one-dimensional bin packing problem. This problem has been studied extensively, and is known to be NP-Complete. New linear-time on-line approximation algorithms are presented for this problem. Their performance is better than that of previously known on-line algorithms. Also, the results extend to orthogonal packings in two dimension.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984.
|Date Available in IDEALS:||2014-12-15|