We study and answer questions related to the complexity of various important problems such as: multifrontal solvers of hpadaptive finite element method, sorting and majority. We advocate the use of dynamic programming as a viable tool to study optimal algorithms for these problems. The main approach used to attack these problems is modeling classes of algorithms that may solve this problem using a discrete model of computation then defining cost functions on this discrete structure that reflect different complexity measures of the represented algorithms. As a last step, dynamic programming algorithms are designed and used to optimize those models (algorithms) and to obtain exact results on the complexity of the studied problems.
The first part of the thesis presents a novel model of computation (element partition tree) that represents a class of algorithms for multifrontal solvers along with cost functions reflecting various complexity measures such as: time and space. It then introduces dynamic programming algorithms for multistage and bicriteria optimization of element partition trees. In addition, it presents results based on optimal element partition trees for famous benchmark meshes such as: meshes with point and edge singularities. New improved heuristics for those benchmark meshes were ob tained based on insights of the optimal results found by our algorithms.
The second part of the thesis starts by introducing a general problem where different problems can be reduced to and show how to use a decision table to model such problem. We describe how decision trees and decision tests for this table correspond to adaptive and nonadaptive algorithms for the original problem. We present exact bounds on the average time complexity of adaptive algorithms for the eight elements sorting problem. Then bounds on adaptive and nonadaptive algorithms for a variant of the majority problem are introduced. Adaptive algorithms are modeled as decision trees whose depth reflects the worstcase time complexity and average depth indicates the averagecase time complexity. Nonadaptive algorithms are represented as decision tests whose size expresses the worstcase time complexity. Finally, we present a dynamic programming algorithm that finds a minimum decision test (minimum reduct) for a given decision table.
Date of Award  Apr 9 2017 

Original language  English 

Awarding Institution   Computer, Electrical and Mathematical Science and Engineering


Supervisor  Mikhail Moshkov (Supervisor) 

 Dynamic programming
 hpFEM
 bounds
 decision tests
 Decision trees
 element partition trees