Files in this item



application/pdf8422804.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Problems in Sorting and Graph Algorithms
Author(s):Richards, Dana Scott
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Five disjoint problems are discussed. The first problem concerns the determination of optimal algorithms with respect to a new model for evaluating sorting algorithms. We did an exhaustive search for such algorithms. The second problem concerns a conjecture that every sorting algorithm on some input involves every key in O(log n) comparisons. We give partial results. The third problem concerns finding efficient algorithms for finding cycles of small fixed length in graphs. We give algorithms for general graphs and O(n log n) algorithms for cycles of length 5 or 6 in planar graphs. The fourth problem concerns the NP-completeness of a wire-routing problem. Specifically, the problem asks for vertex-disjoint paths connecting pairs of points in certain planar graphs. The fifth problem concerns automata traversing graphs in a myopic fashion. We study several cases and show when this can be done and when it is impossible.
Issue Date:1984
Description:144 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984.
Other Identifier(s):(UMI)AAI8422804
Date Available in IDEALS:2014-12-15
Date Deposited:1984

This item appears in the following Collection(s)

Item Statistics