Paper Info
Title
Teaching dynamic programming techniques using permutation graphs
Abstract
Dynamic programming is one of important techniques in algorithm design. The permutation graph is a special type of graphs with theoretical significance and practical applications. Many graph problems such as the domination, and independent set problems can be solved efficiently using dynamic programming schemes by exploring the structural properties of permutation diagrams. Most of current algorithm textbooks use the knapsack problem and matrix chain product as examples for teaching this technique. This paper introduces an incremental and comprehensive approach to teaching dynamic programming using permutation graphs.
Year
DOI
Venue
1995
10.1145/199688.199721
SIGCSE '95 Proceedings of the twenty-sixth SIGCSE technical symposium on Computer science education
Keywords
Field
DocType
algorithm design,permutation graph,independent set,dynamic programming,knapsack problem
Permutation graph,Dynamic programming,Graph,Algorithm design,Computer science,Permutation,Theoretical computer science,Random permutation,Independent set,Knapsack problem
Conference
Volume
Issue
ISSN
27
1
0097-8418
ISBN
Citations 
PageRank 
0-89791-693-X
1
0.41
References 
Authors
10
1
Name
Order
Citations
PageRank
Y. Daniel Liang115314.93