back Back to all Seminars

PhD Defense | Extensions of Dynamic Programming: Decision Trees, Combinatorial Optimization, and Data Mining

Start Date: June 22, 2016
End Date: June 22, 2016

By Shahid Hussain, PhD Candidate of Professor Mikhail Moshkov ( KAUST )
This thesis is devoted to the development of extensions of dynamic programming to the study of decision trees. The considered extensions allow us to make multi-stage optimization of decision trees relative to a sequence of cost functions, to count the number of optimal trees, and to study relationships: cost vs cost and cost vs uncertainty for decision trees by construction of the set of Pareto-optimal points for the corresponding bi-criteria optimization problem. The applications include study of totally optimal (simultaneously optimal relative to a number of cost functions) decision trees for Boolean functions, improvement of bounds on complexity of decision trees for diagnosis of circuits, study of time and memory trade-off for corner point detection, study of decision rules derived from decision trees, creation of new procedure (multi-pruning) for construction of classifiers, and comparison of heuristics for decision tree construction. Part of these extensions (multi-stage optimization) was generalized to well-known combinatorial optimization problems: matrix chain multiplication, binary search trees, global sequence alignment, and optimal paths in directed graphs.
Biography: Shahid Hussain received his BS from Mohammad Ali Jinnah University in Karachi, Pakistan, his MS from King Fahd University of Petroleum and Minerals (KFUPM) in Dhahran, Saudi Arabia and since 2009 he is with KAUST as founding PhD student of Prof. Mikhail Moshkov. He has been working both with developing theory and software system for construction, optimization, and application of decision trees.  Mr. Hussain has authored (and co-authored) many publications in different journals and conferences and presented his work at several conferences, and served as a reviewer and as a member of conference program committees. He has been twice recipient of Academic Excellence Award in 2010/11 and 2013/14 as well as received prestigious Provost Award in 2009/10. 

More Information:

​For more info contact: PhD Candidate Shahid Hussain; email:

Date: Wednesday 22 June 2016
Time: 10:30
Location: Building 1, level 3, Room 3119