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
-
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.
-
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.
-
Codecademy
This site provides tutorials on web design tools. Requires free registration.
-
code.org
Code.org provides courses for F-12 year levels to increase knowledge in computer science. Free log in enables access to resources and more functionality.
-
Algorithms – 7 learner guides
This site offers a range of resources to help teach algorithms and their components.
-
A-Z Handbook on Teaching Introductory Programming
This book viewable online using the 'look inside' feature or purchased in hard copy provides a comprehensive guide to programming for all levels.
-
Computational thinking
This comprehensive online guide, provides a background to computational thinking which refers to the skills and approaches used in computing, programming, and digital solutions to analyse problems and determine how to solve them.
-
Object-oriented programming (OOP)
This comprehensive online guide, explores ways the OOP method of programming (or paradigm) is different to the procedural paradigm, which many programmers start out with on their learning journey. This topic introduces objects and how they can be defined and worked with in a computer system.