2026-09-19T03:47:47Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/69534 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Richards, Dana Scott 2014-12-15T19:25:34Z 2014-12-15T19:25:34Z 10000-01-01 1984 1984 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. Made available in DSpace on 2014-12-15T19:25:34Z (GMT). No. of bitstreams: 1 8422804.pdf: 4037878 bytes, checksum: a6cd620e662478b9c3a2472f9d3ae12a (MD5) Previous issue date: 1984 Embargo set by: Seth Robbins for item 69700 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs U of I Only 144 p. Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984. http://hdl.handle.net/2142/69534 (UMI)AAI8422804 Computer Science Problems in Sorting and Graph Algorithms text Computer Science Computer Science University of Illinois at Urbana-Champaign Dissertation Ph.D.