Assessment of a project-based curriculum for algorithm design and NP-completeness centered on the traveling salesperson problem
Andrea F. Lobo, Ganesh R. Baliga · Journal of computing sciences in colleges · 2016
Algorithms and complexity are fundamental to Computer Science (CS). This paper describes the evaluation of an NSF-funded, project-based curriculum for algorithm design that includes strategies for intractable problems. This curriculum is a sequence of laboratory projects comprising increasingly sophisticated solvers for a single intractable problem. The curriculum is designed to integrate into existing, one-term, undergraduate courses that teach algorithm design and/or intractability. Three versions of the curriculum have been developed to facilitate its sustained adoption, each centered on a well-known problem: Traveling Salesperson (TSP), Satisfiability (SAT) and Sudoku. Over the past decade, the authors have adopted many versions of the curriculum to teach the Design and Analysis of Algorithms course that is required for CS majors at their institution. In the fall semester of 2014, they adopted and assessed a version of the TSP curriculum. The data shows that the curriculum enables the CS2013 core tier-1 and core tier-2 learning outcomes on Algorithms and Complexity. Additionally, the curriculum enables the CS2013 learning outcomes on Advanced Computational Complexity and some learning outcomes in Advanced Data Structures, Algorithms and Analysis. Thus, the curriculum enables students to engage with intractability and learn about NP-Completeness, while also learning the content of traditional undergraduate courses on algorithms.