Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for id:"handle:10754/623124". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


King Abdullah University of Science and Technology

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

Degree: 2017, King Abdullah University of Science and Technology

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…

Advisors/Committee Members: Moshkov, Mikhail, Computer, Electrical and Mathematical Sciences and Engineering (CEMSE) Division, Keyes, David E., Gao, Xin, Boros, Endre.

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

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th Edition):

AbouEisha, Hassan M. “Optimization of Algorithms Using Extensions of Dynamic Programming.” 2017. Thesis, King Abdullah University of Science and Technology. Accessed December 17, 2017. 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 (7th Edition):

AbouEisha, Hassan M. “Optimization of Algorithms Using Extensions of Dynamic Programming.” 2017. Web. 17 Dec 2017.

Vancouver:

AbouEisha HM. Optimization of Algorithms Using Extensions of Dynamic Programming. [Internet] [Thesis]. King Abdullah University of Science and Technology; 2017. [cited 2017 Dec 17]. 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

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.