{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69534"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69534","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Problems in Sorting and Graph Algorithms","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Richards, Dana Scott"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:25:34Z","date_published":"2014-12-15T19:25:34Z","updated_at":"2026-07-22T22:26:01Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8422804"],"render_values":[{"text":"(UMI)AAI8422804","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69534","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Richards, Dana Scott"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:25:34Z","10000-01-01","1984"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69534","(UMI)AAI8422804"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["Problems in Sorting and Graph Algorithms"]}]}],"canonical_facts":{"dc:creator":["Richards, Dana Scott"],"dc:date":["2014-12-15T19:25:34Z","10000-01-01","1984"],"dc:description":["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."],"dc:identifier":["http://hdl.handle.net/2142/69534","(UMI)AAI8422804"],"dc:subject":["Computer Science"],"dc:title":["Problems in Sorting and Graph Algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:01Z"}