Home Search CS Unplugged: Field guide: Complexity and tractability

CS Unplugged: Field guide: Complexity and tractability

An online resource for teaching Computer Science to students, this chapter focusses on complexity and tractability. This chapter covers problems where it's easy to tell the computer what to do --- by writing a program --- but the computer can’t do what we want because it takes far too long. Find out about what is meant by tractable and an intractable problem. Learn about complexity, why its an important concept and how it relates to algorithms.

Additional details

Year band(s)	7-8, 9-10
Format	Web page
Core and overarching concepts	Algorithms
Australian Curriculum Digital Technologies code(s)	AC9TDI8P05 Design algorithms involving nested control structures and represent them using flowcharts and pseudocode AC9TDI8P06 Trace algorithms to predict output for a given input and to identify errors AC9TDI8P10 Evaluate existing and student solutions against the design criteria, user stories and possible future impact AC9TDI10P05 Design algorithms involving logical operators and represent them as flowcharts and pseudocode AC9TDI10P06 Validate algorithms and programs by comparing their output against a range of test cases AC9TDI10P09 Implement, modify and debug modular programs, applying selected algorithms and data structures, including in an object-oriented programming language
Keywords	Tractable, Intractable, Algorithms, Sorting, Searching, Complexity
Organisation	University of Canterbury, New Zealand
Copyright	University of Canterbury, New Zealand. Creative Commons BY-NC-SA 4.0.