Week 2.2. What Are Algorithms
Motivation
Computer scientists solve problems and automate solutions.
Why automate?
- Overcome human limitations - try adding up 1,000,000 numbers!
- Reduce tedium - let people be creative not repetitive
- Reduce errors - computers don't make mistakes
How to program a computer
Before we go to the computer, we need to know:
- What is the problem?
- What are the inputs?
- What are the outputs?
- What is the algorithm? – how do we get from input to output?
At the computer - Turn the algorithm into code – Java, Python, etc
Writing code is the easy part!
Algorithms
An algorithm is the recipe for solving a problem.
We use algorithms every day.
Finding your way
Algorithm: sequence of steps and turns
- Walk forward 100 yards
- Turn left down Rosemary Street
- Continue for 200 yards...
Planning a night out
Algorithm:
- Identify something to do
- Find out who wants to join in
- Organise a time to go
- Plan where to meet...
Solving quadratic equations
Finding roots of:
$$ax^2 + bx + c = 0$$
Algorithm:
Root 1: $x=\frac{-b+\sqrt{b^2-4ac}}{2a}$
Root 2: $x=\frac{-b-\sqrt{b^2-4ac}}{2a}$
Why are algorithms hard?
Humans don't do precision...
- We don't explicitly write down the steps
- We learn "by example"
- We show rather than tell
- We rely on "judgment"
- Shared background assumptions and knowledge
- E.g. "take the next left" does not mean entering a driveway
How do we get good at algorithms?
Practice, practice, practice...
while (true) { practice(); }
Basic programming requires very little knowledge.
It's a mental skill. You gain skill by doing, not by reading.
How to practice
- Surgeries / labs / checkpoints - do your exercises!
- What algorithms do you follow?
- Think about this on the bus
- E.g. how do you cook pasta?
- You don’t just boil for 10 mins, you test it, when do you test it?
- Your own mini projects
- Test out things you learn
- E.g. count lines in a file
- Websites like Project Euler have a list of problems
- Interactive fiction