Files in this item
Files  Description  Format 

application/pdf 8502276.pdf (4MB)  (no description provided) 
Description
Title:  Topics in Combinatorial Algorithms 
Author(s):  Ramanan, Prakash V. 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computer Science 
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, kary trees, is studied. A pair of kary tree traversals is used to assign a permutation of the integers 1,2,(' . . .) to each kary tree T. A pair of traversals in a kary tree Representation Scheme (kRS), if it does not assign the same permutation to two distinct kary trees. Such pairs of traversals are characterized. Some interesting properties of kRS 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 NPCompleteness is considered. There are two main approaches that can be fruitful in dealing with NPComplete 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 NPComplete. Efficient algorithms are presented for some special cases of the problem. The second approach in dealing with NPcomplete problems is to look for heuristic or approximation algorithms. This approach is followed for the onedimensional bin packing problem. This problem has been studied extensively, and is known to be NPComplete. New lineartime online approximation algorithms are presented for this problem. Their performance is better than that of previously known online algorithms. Also, the results extend to orthogonal packings in two dimension. 
Issue Date:  1984 
Type:  Text 
Description:  147 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1984. 
URI:  http://hdl.handle.net/2142/69538 
Other Identifier(s):  (UMI)AAI8502276 
Date Available in IDEALS:  20141215 
Date Deposited:  1984 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois