Show simple item record

dc.contributor.authorMaji, Nabanitaen_US
dc.date.accessioned2015-06-19T08:00:51Z
dc.date.available2015-06-19T08:00:51Z
dc.date.issued2015-06-18en_US
dc.identifier.othervt_gsexam:5937en_US
dc.identifier.urihttp://hdl.handle.net/10919/52973
dc.description.abstractA Theory of Algorithms course is essential to any Computer Science curriculum at both the undergraduate and graduate levels. It is also considered to be difficult material to teach or to learn. In particular the topics of Computational Complexity Theory, reductions, and the NP-Complete class of problems are considered difficult by students. Numerous algorithm visualizations (AVs) have been developed over the years to portray the dynamic nature of known algorithms commonly taught in undergraduate classes. However, to the best of our knowledge, the instructional material available for NP-Completeness is mostly static and textual, which does little to alleviate the complexity of the topic. Our aim is to improve the pedagogy of NP-Completeness by providing intuitive, interactive, and easy-to-understand visualizations for standard NP Complete problems, reductions, and proofs. In this thesis, we present a set of visualizations that we developed using the OpenDSA framework for certain NP-Complete problems. Our paradigm is a three step process. We first use an AV to illustrate a particular NP-Complete problem. Then we present an exercise to provide a first-hand experience with attempting to solve a problem instance. Finally, we present a visualization of a reduction as a part of the proof for NP-Completeness. Our work has been delivered as a collection of modules in OpenDSA, an interactive eTextbook system developed at Virginia Tech. The tutorial has been introduced as a teaching supplement in both a senior undergraduate and a graduate class. We present an analysis of the system use based on records of online interactions by students who used the tutorial. We also present results from a survey of the students.en_US
dc.format.mediumETDen_US
dc.publisherVirginia Techen_US
dc.rightsThis Item is protected by copyright and/or related rights. Some uses of this Item may be deemed fair and permitted by law even without permission from the rights holder(s), or the rights holder(s) may have licensed the work for use under certain conditions. For other uses you need to obtain permission from the rights holder(s).en_US
dc.subjectNP Completenessen_US
dc.subjectComplexity Theoryen_US
dc.subjectReductionsen_US
dc.subjectAlgorithm Visualizationen_US
dc.subjectComputer Science Educationen_US
dc.subjectAutomated Assessmenten_US
dc.titleAn Interactive Tutorial for NP-Completenessen_US
dc.typeThesisen_US
dc.contributor.departmentComputer Scienceen_US
dc.description.degreeMaster of Scienceen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.levelmastersen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Science and Applicationsen_US
dc.contributor.committeechairShaffer, Clifford A.en_US
dc.contributor.committeememberNorth, Christopher L.en_US
dc.contributor.committeememberHeath, Lenwood S.en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record