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
-
Creating a digital start line and finish line with micro:bits (Years 7-8)
The following activity suggests one-way Digital Technologies could be integrated into a unit where vehicles are being designed and produced.
-
Features of the micro:bit!
Learn about the micro:bit.features.
-
Micro:bit projects
Check out these projects that you can build with your micro:bit.
-
micro:bit Tutorial Series Part 1: Getting Started
In this episode, we examine the micro:bit and program it to scroll the phrase "Hello!" across the LED display.
-
The MicroPython guide to BBC micro:bit
Use this guide to learn about using the micro:bit with BBC's online MicroPython code editor.
-
Classroom ideas: Micro:bit Environmental Measurement (visual and general-purpose programming) (Years 5-8)
Investigating environmental data with Micro:bits: This tutorial shows the coding needed for digital solutions of some environmental issues that can be created using pseudocode and visual programming.
-
DT Challenge - 7/8 Arduino - Sound
-
DT Challenge - 7/8 Python - Chatbot
Write code to create word games and develop a Pirate Chatbot. Arrr, me hearties!