Modifying Existing Algorithms & Code
How can we make an existing algorithm run better?
- Identify three ways to modify an algorithm — alternative algorithm, better input, better hardware
- Modify a given pseudocode to improve its efficiency
- Predict the effect of a modification before testing it
Overview
Rewriting a whole program from scratch is rare. In real work we take an existing algorithm and tune it. This week we swap linear search for binary search, tidy up loops, and see why sorted input can make an algorithm much faster.
Three ways to modify an algorithm
1) Use a different algorithm (e.g. binary search instead of linear search). 2) Change the input — sort the data first, or use a smaller data set. 3) Change the hardware — faster CPU, more RAM, or a GPU for parallel work.
Predict, then test
Good engineers predict the effect before running the code. If we replace linear search on 1,000 items with binary search, we expect ~10 comparisons instead of up to 1,000. If the timing does not match, something else in the code is the bottleneck.
Refactoring for readability
Some modifications do not make code faster but make it easier to read and maintain: naming variables clearly, removing repeated code, splitting long routines into small functions. Robot code that is easy to read is easy to fix.
Speed up a search
- Given a linear-search pseudocode that scans 1,000 sorted numbers, write a binary-search version.
- Predict how many comparisons each version needs in the worst case.
- (Optional) Implement both in Scratch or Python and time them.
- Write a 5-line reflection on how the modification changed the result.
- Name three ways to modify an algorithm.
Reveal answer
Use an alternative algorithm, change the input, change the hardware.
- Why does binary search need sorted input?
Reveal answer
It only works if the middle element tells you which half to keep — that requires order.
- What is refactoring?
Reveal answer
Rewriting code to improve its structure without changing its behaviour.
Find a piece of Scratch code online and describe one modification you would make to improve it.