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. |
Related resources
-
Data compression
Students will learn how the information in a pixel can be manipulated to change the image, and apply a bitmask filter to an image to remove some information and reduce the memory size of the file.
-
Pencil code program: Lady MacBeth Chat Bot
Use this program to create an interactive chat bot who answers questions as if she is Lady Macbeth.
-
Card switches
In this challenge students are taught the steps in volved in Bubble sort algorithms by comparing and switching unsorted cards.
-
Convenient stores
In this activity, students learn about Voroni algorithms and how they are used to determine with certainty the shortest distance to key locations on a map.
-
Cellular automoji
Students apply an algorithm, described by a simple set of rules, to create a self replicating emoji patterns across a grid.