Skip to main content
Article
A project-based curriculum for algorithm design and intractability centered on the traveling salesperson problem
Journal of Computing Sciences in Colleges (2014)
  • Andrea F. Lobo, Rowan University
  • Ganesh Baliga, Rowan University
Abstract
This paper presents an award-winning, project-based curriculum for algorithm design that includes techniques for intractable problems. This curriculum is a sequence of laboratory projects comprising increasingly sophisticated solvers for a single intractable problem. The curriculum was designed for integration into existing, one-term, undergraduate courses on algorithm design without sacrificing traditional course content. The curriculum includes feasible approaches for tackling intractable problems, such as developing approximate or probabilistic algorithms. The National Science Foundation (NSF) is supporting the development and evaluation of multiple versions of the project-based curriculum, and also of tools to facilitate their adoption. This paper presents the version of the curriculum that is centered on the Traveling Salesperson Problem, including student learning outcomes, project descriptions, many recommended project sequences, and preliminary assessment results.
Keywords
  • Travelling salesman problem,
  • Project-based learning,
  • Algorithm design,
  • Curriculum,
  • Computational complexity theory,
  • Randomized algorithm,
  • Undergraduate education
Disciplines
Publication Date
June, 2014
Citation Information
Andrea F. Lobo and Ganesh Baliga. "A project-based curriculum for algorithm design and intractability centered on the traveling salesperson problem" Journal of Computing Sciences in Colleges Vol. 29 Iss. 6 (2014) p. 108 - 114 ISSN: 1937-4771
Available at: http://works.bepress.com/ganesh-baliga/1/