Midterm conflicts
The alternate midterm time is: Wednesday October 22nd from 3 p.m. to 6 p.m.
The alternative to these two is to have make assignments worth 40% and the final exam 60%
If you have a conflict, please e-mail Vladimir (vladimir.reinharz [at] mail.mcgill.ca)
Linear Search
There are numbers behind the doors. You are asked to find if the number 11 is behind any of the doors
Linear Search
Given an array of N items, and a target to search
For every position i in the array {
if the item as position i is our target{
Finish! We found our target!
}
}
Binary Search
Given an array A of N items, and a target to search
Let start = 0, end = N-1
while target not found{
Set mid = (start + end)/2
if A[mid] is our target{
Finish! We found our target!
}
else{
if A[mid] < target{
set start = mid + 1
}
else if A[mid] > target{
set end = mid - 1
}
}
}
In the worst case, how many comparisons do we make?
Given an array of N items, and a target that is not in the array
For Linear Search:
- We have to do N comparisons
- For an array of 8 elements: 8 comparisons
- For an array of 128 elements: 128 comparisons
- For an array of N elements: N comparisons
In the worst case, how many comparisons do we make?
Given an array of N items, and a target that is not in the array
For Binary Search:
- We have to do as many comparisons as we can split the array in 2.
- We have to do as many comparisons as we can split the array in 2, plus 1.
- For an array of 8 elements: we split 8 into 4, 4 into 2, 2 into 1, and the compare the last element. 4 comparisons
- For an array of 128 elements: 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1, plus the final comparison. 8 comparisons
- For an array of N elements: N → N/2 → N/4 → ... → 2 → 1, plus the final comparison. log(N) + 1 comparisons.
How much faster is binary than linear search?
We say that an algorithm is faster than another if it performs less operations
In this case, the operations we measure are the number of comparisons
Sorting
To take items that are out of order and put them in some order (e.g. ascending order)
The items need to be comparable
Sorting
To take items that are out of order and put them in some order (e.g. ascending order)
The items need to be comparable
- Names in a phone book
- Grades in a class
- Scores in a competition
Sorting
To take items that are out of order and put them in some order (e.g. ascending order)
The items need to be comparable
- Names in a phone book
- Grades in a class
- Scores in a competition
Bubble sort!
Start with an unsorted array A with N items
while the array is unsorted{
For every position between 1 and N {
if A[i] and A[i-1] are
not in the correct order{
Swap A[i] and A[i-1]
}
}
}
Insertion sort!
Start with an unsorted array A with N items
For every pos between 1 and N-1 {
Let j = pos
Let ITEM = A[pos]
While j > 0
and ITEM is greater than A[j -1] {
Set A[j] = A[j-1]
Decrease j by 1
}
Set A[j] = ITEM
}
How fast is insertion sort?
Why is insertion sort faster?
How fast is insertion sort?
Can we do better?
We can do better
Divide your problem into easier (smaller) subproblems
Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together
We can do even better
Divide your problem into easier (smaller) subproblems
Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together
Idea 2: instead of sorting a list of size N/2 , sort two lists of size N/4 and merge them together
We can do EVEN better than before
Divide your problem into easier (smaller) subproblems
Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together
Idea 2: instead of sorting a list of size N/2 , sort two lists of size N/4 and merge them together
Idea 3: instead of sorting a list of size N/4 , sort two lists of size N/8 and merge them together
We can go all the way down to the bottom!
Divide your problem into easier (smaller) subproblems
Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together
Idea 2: instead of sorting a list of size N/2 , sort two lists of size N/4 and merge them together
Idea 3: instead of sorting a list of size N/4 , sort two lists of size N/8 and merge them together
...
...
...
Idea K: instead of sorting a list of size 2 , sort two lists of size 1 and merge them together
We can go all the way down
Divide your problem into easier (smaller) subproblems
Idea 1: instead of sorting a list of size N , sort two lists of size N/2 and merge them together
Idea 2: instead of sorting a list of size N/2 , sort two lists of size N/4 and merge them together
Idea 3: instead of sorting a list of size N/4 , sort two lists of size N/8 and merge them together
...
...
...
Idea i : instead of sorting a list of size N/(2^(i-1)) , sort two lists of size N/(2^i) and merge them together
...
...
...
Idea K: instead of sorting a list of size 2 , sort two lists of size 1 and merge them together
How do we merge two sorted lists?
Start with TWO sorted arrays:
A with N items, and B with M items
Create an empty array R with size N+M
Let i = 0, and j = 0
While i + j < N + M {
if i == N{
// Reached the end of array A
R[i+j] = B[j]
j = j + 1
}
else if j == M{
// Reached the end of array B
R[i+j] = A[i]
i = i + 1
}
else if A[i] ≤ B[j] {
R[i+j] = A[i]
i = i + 1
}
else if A[i] ≥ B[j] {
R[i+j] = B[j]
j = j + 1
}
}
How fast is our new algorithm?
/
