Introduction to Algorithms & Analysing Existing Algorithms
What is an algorithm, and how do we know if one is efficient?
- Define an algorithm and explain its role in computing and robotics
- Identify the key characteristics of an efficient algorithm
- Analyse a sample algorithm for time and space complexity (informally)
Overview
Every robot follows an algorithm — a finite, ordered set of steps to solve a problem. This week we start with a familiar example (making a cup of tea) and work our way to real search and sort algorithms, learning to count operations and talk about best, worst and average case.
What is an algorithm?
An algorithm is a finite, ordered set of steps that solves a problem or completes a task. Recipes, bus timetables and robot control programs are all algorithms. In computing, algorithms take inputs, process them, and produce outputs.
Characteristics of a good algorithm
An efficient algorithm is correct (produces the right output), finite (ends in a reasonable time), unambiguous (each step is clear) and general (works on more than one input). We prefer algorithms that use fewer steps and less memory.
Best, worst and average case
The same algorithm can be fast on lucky inputs and slow on unlucky ones. Linear search finds the item on the first try in the best case, on the last try in the worst case, and roughly halfway on average. Knowing these cases helps us pick the right algorithm.
Trace bubble sort on 5 numbers
- Write the numbers 5, 2, 4, 1, 3 on paper.
- Perform bubble sort by comparing each adjacent pair and swapping if needed.
- Count how many comparisons and how many swaps you make.
- Compare your counts with a partner and discuss the worst case.
- Define an algorithm.
Reveal answer
A finite, ordered set of steps that solves a problem.
- List two characteristics of a good algorithm.
Reveal answer
Correct and finite (also: unambiguous, general, efficient).
- What is the worst case of linear search on 100 items?
Reveal answer
100 comparisons — the item is last or not in the list.
Describe one algorithm you use every day (getting ready for school, cooking rice). Break it into numbered steps.