Article
Developing a project-based curriculum for the design and analysis of algorithms for intractable problems
Journal of Computing Sciences in Colleges
(2012)
Abstract
In Computer Science, problems for which no fast algorithms are known are called intractable. The class of NP-complete problems is an important collection of intractable problems. The need to solve intractable problems arises in numerous practical settings. However, the only algorithms that are known to solve these problems at the present time require an exponential amount of time. In recent years, algorithm designers have focused their attention on feasible techniques for solving these problems such as approximate algorithms, probabilistic algorithms, and others. Approximate algorithms will compute a sub-optimal solution that is guaranteed to be within a factor of the optimal solution. Probabilistic algorithms may only guarantee that a solution will be found with a certain probability. These algorithms can be used to develop software programs that solve some instances of intractable problems. As computers have continued to become more powerful and affordable, the computing power available in industry and research is increasingly sufficient to run these solvers on useful, often large, instances of some intractable problems.
Keywords
- Analysis of algorithms,
- Computational complexity theory,
- Project-based learning,
- Curriculum,
- Randomized algorithm,
- NP-complete,
- Optimization problem
Disciplines
Publication Date
June, 2012
Citation Information
Andrea F. Lobo and Ganesh Baliga. "Developing a project-based curriculum for the design and analysis of algorithms for intractable problems" Journal of Computing Sciences in Colleges Vol. 27 Iss. 6 (2012) p. 68 - 69 ISSN: 1937-4771 Available at: http://works.bepress.com/ganesh-baliga/2/