{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69561"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69561","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Topics in the Design and Analysis of Combinatorial Algorithms","abstract":"This thesis presents topics in the analysis and design of Combinatorial Algorithms. The second chapter introduces a technique for obtaining more precise closed form solutions of recurrence relations defined by minimization and maximization operators. Since such recurrences arise quite frequently in the analysis of the complexity and performance of algorithms it is important to develop techniques for their solution. The technique used is next applied to give precise solutions for the cost of optimal "lopsided trees." These trees model a number of problems arising in practise.","abstract_html":"This thesis presents topics in the analysis and design of Combinatorial Algorithms. The second chapter introduces a technique for obtaining more precise closed form solutions of recurrence relations defined by minimization and maximization operators. Since such recurrences arise quite frequently in the analysis of the complexity and performance of algorithms it is important to develop techniques for their solution. The technique used is next applied to give precise solutions for the cost of optimal "lopsided trees." These trees model a number of problems arising in practise.","abstract_has_math":false,"creators":["Kapoor, Sanjiv"],"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:48Z","date_published":"2014-12-15T19:25:48Z","updated_at":"2026-07-22T22:26:01Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8701524"],"render_values":[{"text":"(UMI)AAI8701524","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69561","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Kapoor, Sanjiv"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:25:48Z","10000-01-01","1986"]},{"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/69561","(UMI)AAI8701524"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis presents topics in the analysis and design of Combinatorial Algorithms. The second chapter introduces a technique for obtaining more precise closed form solutions of recurrence relations defined by minimization and maximization operators. Since such recurrences arise quite frequently in the analysis of the complexity and performance of algorithms it is important to develop techniques for their solution. The technique used is next applied to give precise solutions for the cost of optimal "lopsided trees." These trees model a number of problems arising in practise.","The next chapter deals with self-organizing data structures. These data structures allow efficient access of the data elements when the elements are accessed according to an unknown probability distribution. We show that rearrangment rules from a certain general class can be modified so as to reduce the number of data moves, while leaving unchanged the asymptotic behaviour of the mean and variance of the cost of a data access. Since a data movement usually costs at least as much as a single probe the modified rule eventually leads to savings in total cost (the sum of the costs of comparisons and data movements).","In the third chapter we show that a certain problem, called the Linear Net Routing Problem, which arises in VLSI applications is NP-Complete. We also describe an heuristic for this problem which was proposed by K. J. Supowit.","In the last chapter an algorithm for optimization convex quadratic forms over polytopes is described. This is an extension of the linear programming algorithm presented by Karmarkar and is joint work with P. Vaidya. We also use the linear programming algorithm to present an algorithm for multi-commodity flows.","Made available in DSpace on 2014-12-15T19:25:48Z (GMT). No. of bitstreams: 1 8701524.pdf: 4165890 bytes, checksum: a0e6c868e055f9d33619b217bfe38489 (MD5) Previous issue date: 1986","Embargo set by: Seth Robbins for item 69727 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","148 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1986."]},{"key":"dc:title","label":"Title","values":["Topics in the Design and Analysis of Combinatorial Algorithms"]}]}],"canonical_facts":{"dc:creator":["Kapoor, Sanjiv"],"dc:date":["2014-12-15T19:25:48Z","10000-01-01","1986"],"dc:description":["This thesis presents topics in the analysis and design of Combinatorial Algorithms. The second chapter introduces a technique for obtaining more precise closed form solutions of recurrence relations defined by minimization and maximization operators. Since such recurrences arise quite frequently in the analysis of the complexity and performance of algorithms it is important to develop techniques for their solution. The technique used is next applied to give precise solutions for the cost of optimal "lopsided trees." These trees model a number of problems arising in practise.","The next chapter deals with self-organizing data structures. These data structures allow efficient access of the data elements when the elements are accessed according to an unknown probability distribution. We show that rearrangment rules from a certain general class can be modified so as to reduce the number of data moves, while leaving unchanged the asymptotic behaviour of the mean and variance of the cost of a data access. Since a data movement usually costs at least as much as a single probe the modified rule eventually leads to savings in total cost (the sum of the costs of comparisons and data movements).","In the third chapter we show that a certain problem, called the Linear Net Routing Problem, which arises in VLSI applications is NP-Complete. We also describe an heuristic for this problem which was proposed by K. J. Supowit.","In the last chapter an algorithm for optimization convex quadratic forms over polytopes is described. This is an extension of the linear programming algorithm presented by Karmarkar and is joint work with P. Vaidya. We also use the linear programming algorithm to present an algorithm for multi-commodity flows.","Made available in DSpace on 2014-12-15T19:25:48Z (GMT). No. of bitstreams: 1 8701524.pdf: 4165890 bytes, checksum: a0e6c868e055f9d33619b217bfe38489 (MD5) Previous issue date: 1986","Embargo set by: Seth Robbins for item 69727 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","148 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1986."],"dc:identifier":["http://hdl.handle.net/2142/69561","(UMI)AAI8701524"],"dc:subject":["Computer Science"],"dc:title":["Topics in the Design and Analysis of Combinatorial 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"}