Problems in Sorting and Graph Algorithms

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Richards, Dana Scott

• Computer Science

Identifier

(UMI)AAI8422804

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/69534