Presentation for the Introductory topic of Algorithms

Algorithms

1. Institute for Personal Robots in Education
(IPRE)
CSC 170
Computing: Science and Creativity

2. ●
Alan Winfield of Bristol Robotics Laboratory
●
A Robot tries to save one and then two robots
from falling int a hole |_
Early Algorithms

3. What is an algorithm?
●
An algorithm is any well-defined
computational procedure that takes some
value or set of values as input and produces
some value or set of values as output
●
The decimal equivalent of a binary number
●
Algorithms can be non computer based
●
Cake recipe, instructions to get to from here to
there, find a number in a phonebook
–Or how back up your contact list on a cell phone
●
Algorithms are much older than computers

4. ●
Dances, ceremonies,
recipes, and building
instructions are all
conceptually similar to
algorithms
●
Babylonians defined some
fundamental mathematical
procedures ~3,600 years
ago
●
Genes contain algorithms!
●
step-by-step processes to
transcribe genes and
produce proteins
Algorithms
Photo credit: Daniel Niles

5. Algorithms You Might have Used this week
Tie your shoe laces
Wasn’t easy, was it?
Log in to D2L
Enter UA Net ID and
password, press
something
Attended CSc 170
Wake up, do your
routine, drove, walked
or biked nearby …..
Study for a test
Is there really any easy
way?

6. Algorithms You've Seen in CSC 170
●
Determine a letter grade if..else
●
Interact with the user ask
●
Help a player guess a word in fewer tries
repeat until loop
●
Find if a digit is in a number for loop
●
Create a 5 digit number? secretNumber

7. Algorithms You Might have Used this week
Luhn algorithm
Credit card number
validation
Recommenders
You might also be
interested in …
PageRank
Google’s way of
measuring “reputation” of
web pages
EdgeRank
Facebook’s method for
determining what is
highest up on your news
feed

8. Forms of control in algorithms
Sequencing
Application of each step of
an algorithm in order
(sometimes: find order)
Selection
Use of Boolean condition
to select execution parts
Iteration
Repetition of part of an
algorithm until a condition
is met
Recursion
Repeated application of
the same part of
algorithm on smaller
problems

9. Properties of Algorithms
●
Algorithm + Algorithm = Algorithm
●
Part of Algorithm = Algorithm
●
Several algorithms may solve the same problem,
but in differrent time
●
Much of Computer Science research involves
development of algorithms that solve difficult problems
●
And then implementing them in a programming
language to do it as quickly as possible
●
Believe it or not, it can take seconds or decades

10. Proving QUARKS exist
●
Kenneth G. Wilson, winner of the 1982
Nobel Prize in physics, found he didn’t
have adequate computing power to
solve his theory numerically, so he
wanted easy ways to use large
numbers of parallel processors.”
●
“He was decades ahead of his time with
respect to computing and networks..”
●
So Wilson became a pioneer in the
field of supercomputing (Cornell)
●
UofA CS and BIOr now looking
forpatterns in terabytes, or trillions
(1,000,000,000,000) of genomic data

11. Algorithm Correctness
●
We don't only want algorithms to be fast and
efficient; we also want them to be correct!
●
We also have probabalistic and stochastic
algorithms that have a randomness or
probability to report an answer
●
File download time
●
Weather predictions
●
Potential Friends on Facebook
●
Translating text using probabilistic text generation
●
Predicting forest fire danger
●
Discovering terroristic activities
●
Ask the Magic eight ball
https://eightball.tridelphia.net/

12. How to Express Algorithms…
●
A programmer’s spouse tells him: “Run to the
store and pick up a loaf of bread. If they have
eggs, get a dozen.”
●
The programmer comes home with 12 loaves of bread
●
Algorithms need to be expressed in a context-
free, unambiguous way for all participants

13. Ways to Express Algorithms
●
Natural Language
●
Pseudo Code
●
Programming
Language
●
Snap! Blocks

14. Let’s write an algorithm in a natural language
●
Write an algorithm in English that takes a
binary number such as 1010101010 and
reports the decimal equivalent
1101
2
= 1x2
3
+ 1x2
2
+ 0x2
1
+ 1x2
0

= 8 + 4 + 0 + 1 = 13
10