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
-
A matter of style
In this lesson sequence, students using the Zen Garden website reflect on criteria for effective design.
-
Google CS First: Storytelling
CS First: Storytelling guides students to use block-based coding in Scratch projects through a series of themed activities.
-
Baringa State Primary School: Implementation of STEM
Baringa PS uses a cross-disciplinary approach that integrates STEM disciplines around relevant contexts (ie a problem, question, product or issue).
-
Parramatta Marist High: Building a programming mindset
Kelly Bauer explains how video games are the starting point for Year 7 students at Parramatta Marist High to learn about coding.
-
Torrens Valley Christian School: New subject at Year 10
Fiona Clayton describes how their Year 10 Digital Technologies subject has had an impact on numbers opting to go on and study in this area.