An Interactive Tutorial for NP-Completeness

Simple item page
dc.contributor.authorMaji, Nabanitaen
dc.contributor.committeechairShaffer, Clifford A.en
dc.contributor.committeememberNorth, Christopher L.en
dc.contributor.committeememberHeath, Lenwood S.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2015-06-19T08:00:51Zen
dc.date.available2015-06-19T08:00:51Zen
dc.date.issued2015-06-18en
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
dc.description.degreeMaster of Scienceen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:5937en
dc.identifier.urihttp://hdl.handle.net/10919/52973en
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectNP Completenessen
dc.subjectComplexity Theoryen
dc.subjectReductionsen
dc.subjectAlgorithm Visualizationen
dc.subjectComputer Science Educationen
dc.subjectAutomated Assessmenten
dc.titleAn Interactive Tutorial for NP-Completenessen
dc.typeThesisen
thesis.degree.disciplineComputer Science and Applicationsen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Maji_N_T_2015.pdf
Size:
4.2 MB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses