Algorithms
What are they?
● A process or set of rules for solving a problem
● Simply - a series of steps
Robot example
Problem : Get the robot to make coffee
1. Add water to coffee machine
2. Add coffee
3. Start machine
4. Wait for beep
……..
When coding an algo
● Clearly understand the steps you need to
○ Write them on a paper or draw a picture or a diagram
○ Understand the different actions
○ Maybe write some pseudo -code
■ This is like code but not computer understandable
■ English -like
● Think of improvements:
○ Find the quickest way for your code to solve the problem.
Simple example - Find max
Simple example - Find max
Steps:
1. Assume the first card is the max and remember its value
2. Scan through all the cards
3. If you see a higher card, then remember that higher value
The last
max was 7
Simple example - Find max
Pseudo code
last_max = first card To remember the last highest number
while (stack has cards)
do
card_value = read next card
if ( card_value > last_max )
then
last_max = card_value
done
Answer : last_max
Simple example - Find min
Pseudo code
last_min = first card
while (stack has cards)
do
card_value = read next card
if ( card_value < last_min )
then
last_min = card_value
Done
Answer : last_min
Simple example - Find both max min
First loop thru and find max
last_max = first card
while (stack has cards)
do
card_value = read next card
if ( card_value >last_max )
then
last_max = card_value
Done
Then loop thru again and find min
last_min = first card
while (stack has cards)
do
card_value = read next card
if ( card_value <last_min )
then
last_min = card_value
Done
Answer: last_min and last_max
Simple example - Find both max min
● But you had to loop thru twice
○ That takes twice the time!
● How to do do better
○ Can we loop thru only once ?
Simple example - Find both min and max
● Remember two numbers
○ The last lowest
○ The last highest
Last max Last min
was 7 was 2
Simple example - Find both min and max
Pseudo code
last_max = first card
last_min = first card
while (stack has cards)
do
card_value = read next card
if ( card_value > last_max )
then
last_max = card_value
else if ( card_value < last_min )
then
last_min = card_value
Done
Answer: last_min and last_max
Was it better?
● You need only one loop
○ Great for long lists!
○ Saves time
● But you need to remember 2 numbers at the same time
○ So a little bit more memory
Example Sorting numbers
Arrange numbers in increasing order
(think only about steps now, not the pseudo code)
Example Sorting numbers
Steps
1. Start with the first 2 numbers and order them
2. Then take the next 2 numbers and order them
3. Go back to the 2 numbers before and order them
Example Sorting numbers
Example Sorting numbers
Example Sorting numbers
● Keep going to the end
● This sorting method is called bubble sort
○ Each number is “bubbled” up to its right position
● How many times do you have to compare (and maybe move)?
○ i.e. how many steps are needed?
Example Sorting numbers: Bubble sort
● If there are N numbers in the list, it can be up to
N2
○ Gets really big with long lists
With a long lists of 1000s
● Will burn up your computer!
● (realistically take a very long time)
Sort - better than bubble sort
A divide and conquer algorithm
Sort - better than bubble sort
Sort smaller sets
Then merge and sort again - Keep repeating
Sort - Merge sort better than bubble sort
● This is “merge” sort
○ Needs fewer comparisons
N . log (N)
○ Saves time
● Need to track the ‘splits’
○ A bit more memory for that
Improve an algo
● Fewer steps (or computations/comparisons)
● Lesser things to remember or (use less memory)
In code that means
Aim for :
● Fewer loops
○ Avoid loops inside loops if you can
● Fewer variables
Traveling salesman
Visit a number of towns and return home
Problem: Find the shortest total distance
A
55
40
45
H 75
B
40
35
C
Traveling salesman
One solution:
Step 1: Make a list of all possible routes
Step 2: Calculate the distance traveled for each route
Step 3: Choose the route with the lowest distance
40 170
170 55
H 55
A 40
B 35
C H 40
C 35
B 40
A
205 70 205 55
H A C B H 70
B 35
C 45
A
55 45 35
210
195 70 55
H 70
B 40
A 45
C
H 40 C 45 A 40 B
Traveling salesman
● With home plus 3 towns - we had to compare 6 routes
● What if we have home plus 4 towns?
● Home plus 5 towns?
….
● Can you algo handle any number of towns?...
○ N towns
Traveling salesman
You will have to compare N! (factorial) routes
- Thats a lot N gets larger and larger
- For just 5 towns, you have 120 routes
- For 8 towns : 40,320 & for ten towns, 3.6 million!!
A few more and you will just burn your
computer !
Traveling salesman
● There is no good algorithm today for this today
So computer scientists have some “short cut” smart approaches
● Get “greedy” - e.g. just go to the next closest town
● Sometimes works just as well
Traveling salesman
● A “greedy” algorithm
○ Just go the next closest town
A
55
40
3
4
H B
1
2 =170
40
35
C
Real life example - school bus route
● Edison school district uses a
route software
● It needs to calculate the best
routes for about a hundred
pick up points !
Real life example - Google search
Web crawler
This is a multi-stage algorithm
1. Find all web pages on the internet
2. Track every word and the pages it
appears on
a. Write a dictionary of words to their
web pages
Web crawler
3. Track how many other pages link to
every page
Real life example - Google search
When a user enters a search query..
Step 1. Find all important words in the user’s query
Step 2. Check the dictionary for web pages with those words
Step 3. Sort the web pages by number of links to that page
Show the results