Advanced search options

You searched for `id:"handle:10754/623124"`

. One record found.

▼ Search Limiters

1. AbouEisha, Hassan M. Optimization of Algorithms Using Extensions of Dynamic Programming.

Degree: 2017, King Abdullah University of Science and Technology

URL: http://hdl.handle.net/10754/623124

We study and answer questions related to the complexity of various important problems such as: multi-frontal solvers of hp-adaptive 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 multi-frontal solvers along with cost functions reflecting various complexity measures such as: time and space. It then introduces dynamic programming algorithms for multi-stage and bi-criteria 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 non-adaptive 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 non-adaptive algorithms for a variant of the majority problem are introduced. Adaptive algorithms are modeled as decision trees whose depth reflects the worst-case time complexity and average depth indicates the average-case time complexity. Non-adaptive algorithms are represented as decision tests whose size expresses the worst-case time complexity. Finally, we present a dynamic programming algorithm that finds a minimum decision test (minimum reduct) for a given decision table.

We study and answer questions related to the complexity of various important problems such as: multi-frontal solvers of hp-adaptive 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…

Subjects/Keywords: Dynamic programming; hp-FEM; bounds; decision tests; Decision trees; element partition trees

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

AbouEisha, H. M. (2017). Optimization of Algorithms Using Extensions of Dynamic Programming. (Thesis). King Abdullah University of Science and Technology. Retrieved from http://hdl.handle.net/10754/623124

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^{th} Edition):

AbouEisha, Hassan M. “Optimization of Algorithms Using Extensions of Dynamic Programming.” 2017. Thesis, King Abdullah University of Science and Technology. Accessed May 21, 2018. http://hdl.handle.net/10754/623124.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

AbouEisha, Hassan M. “Optimization of Algorithms Using Extensions of Dynamic Programming.” 2017. Web. 21 May 2018.

Vancouver:

AbouEisha HM. Optimization of Algorithms Using Extensions of Dynamic Programming. [Internet] [Thesis]. King Abdullah University of Science and Technology; 2017. [cited 2018 May 21]. Available from: http://hdl.handle.net/10754/623124.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

AbouEisha HM. Optimization of Algorithms Using Extensions of Dynamic Programming. [Thesis]. King Abdullah University of Science and Technology; 2017. Available from: http://hdl.handle.net/10754/623124

Not specified: Masters Thesis or Doctoral Dissertation