10:00 - 1PM Introduction
Defining an algorithm
Time/space complexity
Goal of algorithms
Sorting
1:00 - 2:00 Lunch
2:00 - 5:00 Searching
Data Structures
Primes
Conclusion
"A repeatable process for determining the solution to a problem."
What's an algorithm that you used today?
Write out the steps for doing it?
How do you know if your algorithm is good?
How do you compare algorithms?
The less complex the better!
Saves time, but requires you to have a large car
Lower time complexity
Higher space complexity
Takes a long time, but doesn't require a car
Higher time complexity
Lower space complexity
How long does an algorithm take?
laundry.drop()
How long does the algorithm take?
How long does the algorithm take?
Dumping out my laundry takes 2 seconds
#items | #seconds |
---|---|
4 | 2 |
8 | 2 |
16 | 2 |
If N = items of clothing,
it takes (N*0 + 2) => O(2) => O(1).
var piles = {'shirts': [], 'socks': []}
for (var i = 0; i < clothing.length; i++) {
piles[clothing[i].type].push(clothing[i]);
}
for (var pile in piles) {
for (var i = 0; i < pile.length; i++) {
pile[i].hangUp();
}
}
How long does the algorithm take?
Putting an item in a pile takes 10 seconds.
Hanging an item up takes 30 seconds.
#items | #seconds |
---|---|
4 | (4*10 + 4*30) = 160 |
8 | (8*10 + 8*30) = 320 |
16 | (16*10 + 16*30) = 640 |
If N = items of clothing,
it takes (N*10 + N*30) => O(N).
Addition: We sort our clothes as we hang them up in the closet.
var piles = {'shirts': [], 'socks': []}
for (var i = 0; i < clothing.length; i++) {
piles[clothing[i].type].push(clothing[i]);
}
for (var type in piles) {
for (var i = 0; i < piles[type].length; i++) {
var section = closetSections[type];
for (var j = 0; j < section.length; j++) {
if (pile[i].color > section[j].color) {
pile[i].hangUp();
}
}
}
}
Now we must loop through closet section items
each time we hang up an item.
Each look at an item takes 2 seconds.
items | section | items | seconds |
---|---|---|---|
4 | 4 | (4*10 + 4*30 + 4*4*2) | 192 |
8 | 8 | (8*10 + 8*30 + 8*8*2) | 448 |
1024 | 1024 | (1024*10 + 1024*30 + 1024*1024*2) | 2138112 |
If N = # items of clothing and # items in section,
it takes (N*10 + N*30 + N*N*2) => O(N^2)
Order of growth | Name | Description | Example |
---|---|---|---|
1 | constant | statement | add two numbers |
logN | logarithmic | divide in half | binary search |
N | linear | loop | find the maximum |
NlogN | linearithmic | divide + conquer | merge sort |
N^{2} | quadratic | double loop | check all pairs |
N^{3} | cubic | triple loop | check all triples |
2^{N} | exponential | exhaustive search | check all subsets |
skipping to the front of a line
O(1) - Constant
O(n) - Linear
O(n^2) - Quadratic
waiting in a line
O(1) - Constant
O(n) - Linear
O(n^2) - Quadratic
skipping half of a line
O(1) - Constant
O(n) - Linear
O(n^2) - Quadratic
sorting your books in alphabetical order
O(1) - Constant
O(n) - Linear
O(n^2) - Quadratic
looking up an element in an array
var things = ["raindrops", "roses", "whiskers", "kittens"]
things[2]
O(1) - Constant
O(n) - Linear
O(n^2) - Quadratic
iterating over an array
var things = ["raindrops", "roses", "whiskers", "kittens"]
for (var i = 0; i < things.length; i++) {
things[i]
}
O(1) - Constant
O(n) - Linear
O(n^2) - Quadratic
making every pair combination of items in array
var things = ["raindrops", "roses", "whiskers", "kittens"]
for (var i = 0; i < things.length; i++) {
for (var j = i + 1; j < things.length; j++) {
things[i] + things[j]
}
}
// raindrops + roses
// raindrops + whiskers
// raindrops + kittens
// roses + whiskers
// roses + kittens
// whiskers + kittens
O(1) - Constant
O(n) - Linear
O(n^2) - Quadratic
How much space does sorting items of clothing into piles take?
Assume: piles of clothing can be infinitely high.
N = number of pieces of clothing,
M = number of piles.
Worst case: M = N
Best case: M = 1
Average: N/2
What is the space complexity?
How much space does the algorithm take?
Each item takes 10cm^3 in the car
#items | #cm^3 |
---|---|
4 | (4*10) = 40 |
8 | (8*10) = 80 |
16 | (16*100) = 160 |
If N = number of grocery items,
it takes (N*10) => O(N).
How much space does the algorithm take?
Each item takes 10cm^3 in the tote bag
#items | #cm^3 |
---|---|
4 | (10) = 10 |
8 | (10) = 10 |
16 | (10) = 10 |
If N = number of grocery items,
it takes (10) => O(1).
Designing algorithms is about making decisions. Decisions have tradeoffs.
You may want to optimize to complete the task:
What's the time requirement of your algorithm?
What's the space requirement of your algorithm?
Many algorithms operate on lists of things
In programming, basic lists are called arrays
[4, Q, 5, A, J, 10, K]
What sort of algorithms can you do on a deck of cards?
Sort, search, shuffle, etc.
Rearrange items in a sequence by some property about each item.
(like numerical or alphabetical order)
[4, Q, 5, A, J, 10, K]
->
[4, 5, 10, J, Q, K, A]
A simple but not very efficient sorting algorithm.
For I = 0 to N - 2
For J = 0 to N - 2
If (A(J) > A(J + 1)
Temp = A(J)
A(J) = A(J + 1)
A(J + 1) = Temp
End-If
End-For
End-For
What factors determine time?
N = number of items in sequence.
What is the best case? | What is the worst case? |
---|---|
Already sorted array N comparisons. O(N) |
Reverse sorted array N*N comparisons. O(N^{2}) |
Only requires 1 extra temporary variable.
All differ in performance, and performance often depends on sequence characteristics.
Wikipedia: Comparison of algorithm performance, Sorting Algorithms Visualization
(Who says programmers don't know how to let loose?)
"A particularly ineffective sorting algorithm"
Find an item with a particular value in a sorted sequence.
Find 'J' in sequence:
[4, 5, J, 10, Q, K, A]
J is the 3rd element (index 2).
Find an item by repeatedly halving the search space.
To find the index of element e with a certain value:
BinarySearch(array, value) {
low = 0
high = array.length - 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid
}
return not_found
}
What factors determine time?
N = number of items in sequence.
Since algorithm splits array in half every time, at most log_{2}N steps are performed.
Performance varies depending on sequence characteristics (distribution)
A way to store data (so that it can be used as desired)
A good way to approach an algorithm is to think about the data structures that you know.
What are their properties, and how can they be used to your advantage?
Prime number: a number that is only divisible by 1 and itself.
Why should computer scientists care?
Encryption!
Easy: 3 * 11 * 127 * 113327 = 474953457
Hard: 474953457 = 3 * 11 * 127 * 113327
How would you find the first 1000 primes?
How would you find all primes under 1000?
What are the tradeoffs?