Topics in the Design and Analysis of Combinatorial Algorithms

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.

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

• Kapoor, Sanjiv

• Computer Science

Identifier

(UMI)AAI8701524

OAI identifier oai:identifier

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