Pick-Up Midterms!
Corrections due Friday 3/18!
+(0.5 x points) for corrections
Due Friday 3/18 in-class!
Use a pen for corrections - bring back to lecture Friday!
HW6 Released!
1. Welcome to COMP 285
Lecture 21: Midterm Overview
COMP - 285
Advanced Algorithms
Lecturer: Luis Perez (laperez@ncat.edu)
Today (Welcome back!)
5
Overall Distribution (Points)
A
> 74
A-
> 64
B+
> 54
B
> 41
B-
> 31
F, D, D+, C-,C,C+
Median: 40
Section 1 - Median: 5
f(n) | N = 1,000,000 |
n log n | ~6,000,000 |
n2 | ~1,000,000,000,000 |
√n | ~1,000 |
2022 | 2022 |
~1,000,007,003,022
<= | Big-O |
= | Big-Theta |
>= | Big-Omega |
False
<= | Big-O |
= | Big-Theta |
>= | Big-Omega |
Section 2
O(n)
O(n)
O(1)
Time Complexity: O(n2)
Space Complexity: O(1)
O(n)
O(1)
Space: O(n)
Time Complexity: O(n)
Space Complexity: O(n)
Section 3
1
2
5
10
14
An example
3
1
2
5
10
14
Brute Force
O(n)
Divide & Conquer
0
1
2
3
5
8
10
0
1
2
3
4
5
6
A[0] + n/2
A[n/2]
Case 1
A[n/2] = A[0] + n/2
Divide & Conquer
0
1
3
4
5
8
10
0
1
2
3
4
5
6
Case 2
A[n/2] > A[0] + n/2
Divide & Conquer
-1
0
1
2
3
4
5
0
1
2
3
4
5
6
Case 3
A[n/2] < A[0] + n/2
Divide & Conquer
Case 1
Case 2
Walk Through Examples
1
2
5
10
14
1
2
2
3
0
1
2
3
5
8
10
Walk Through Examples
4
8
10
3
5
3
5
3
0
1
3
4
5
8
10
Walk Through Examples
2
3
0
1
1
3
1
How Fast is It?
Section 4
Algorithm | Worst-Case Running Time | Comparison-Based |
QuickSort | O(n log n) | Yes |
MergeSort | O(n log n) | Yes |
RadixSort | O(d(n + r)) | No |
Counting Sort | O(n + r) | No |
Selection Sort | O(n2) | Yes |
Insertion Sort | O(n2) | Yes |
False
True
Contiguous Subarray Sums
-10
4
11
-9
1
start = 0
end = 1
sum = -10
Contiguous Subarray Sums
-10
4
11
-9
1
start = 0
end = 2
sum = -6
Contiguous Subarray Sums
-10
4
11
-9
1
start = 0
end = 3
sum = 5
Contiguous Subarray Sums
-10
4
11
-9
1
start = 0
end = 4
sum = -4
Contiguous Subarray Sums
-10
4
11
-9
1
start = 0
end = 5
sum = -3
Contiguous Subarray Sums
-10
4
11
-9
1
start = 1
end = 2
sum = 4
Contiguous Subarray Sums
-10
4
11
-9
1
start = 1
end = 3
sum = 15
Contiguous Subarray Sums
-10
4
11
-9
1
start = 1
end = 4
sum = 6
Contiguous Subarray Sums
-10
4
11
-9
1
start = 1
end = 5
sum = 7
Contiguous Subarray Sums
-10
4
11
-9
1
start = 2
end = 3
sum = 11
Contiguous Subarray Sums
-10
4
11
-9
1
start = 2
end = 4
sum = 2
Contiguous Subarray Sums
-10
4
11
-9
1
start = 2
end = 5
sum = 3
Contiguous Subarray Sums
-10
4
11
-9
1
start = 3
end = 4
sum = -9
Contiguous Subarray Sums
-10
4
11
-9
1
start = 3
end = 5
sum = -8
Contiguous Subarray Sums
-10
4
11
-9
1
start = 4
end = 5
sum = 1
Contiguous Subarray Sums
-10
4
11
-9
1
start = 5
end = 5
sum = 0
-10
4
11
-9
1
start = 5
end = 5
sum = 0
Brute Force
Brute Force - Pseudocode
O(n3)
O(n2)
-4
10
2
-20
5
6
-4
-4
10
2
-20
5
6
4
-4
10
2
-1
5
8
-4
-4
10
2
-20
5
6
-4
-4
10
2
-20
5
6
-4
-4
10
2
-20
5
6
-4
-4
10
2
-20
5
6
-4
-4
10
2
-20
5
6
-4
0
10
2
-20
5
6
0
-4
10
2
-20
5
6
-4
10
2
5
6
-4
10
2
-20
5
6
-4
12
11
-4
10
2
-20
5
6
-4
12
12
11
-4
10
2
-20
5
6
-4
-20
-20
12
11
-4
10
2
-20
5
6
-4
-18
-18
12
11
-4
10
2
-20
5
6
-4
-8
-8
12
11
-4
10
2
-20
5
6
-4
-8
-12
12
11
-4
10
2
-20
5
6
-4
-8
5
5
12
11
-4
10
2
-20
5
6
-4
-8
11
11
12
11
-4
10
2
-20
5
6
-4
-8
7
11
12
11
-4
10
2
-20
5
6
-4
-8
11
+
3
=
T(n) = 2T(n/2) + O(n)
O(n log n)
Section 5
Section 6
19
1
5
1
-3
6
8
33
1
-3
26
-3
7
Find Height
O(n)
Section 7
+
= 22
17
+
= 22
13
+
+
= 22
2
+
+
= 22?
=17?
= 17?
= 22?
=17?
= 17?
=11?
=11?
= 9?
= 9?
= 22?
=17?
= 17?
=11?
No!
= 9?
= 9?
=5?
=5?
=-4?
=-4?
=4?
=2?
= 22?
=17?
= 17?
=11?
No!
= 9?
= 9?
No!
=5?
No!
No!
=4?
=2?
=4?
=4?
=0?
=0?
=3?
=3?
= 22?
=17?
= 17?
=11?
No!
= 9?
= 9?
No!
=5?
No!
No!
=4?
=2?
No!
No!
Yes!
Yes!
No!
No!
= 22?
=17?
= 17?
=11?
No!
No!
= 9?
No!
No!
No!
Yes!
= 22?
=17?
= 17?
No!
No!
No!
Yes!
= 22?
No!
Yes!
Yes!
O(n) Runtime
Section 8
| Node 0 | Node 1 | Node 2 | Node 3 |
Node 0 | | | | |
Node 1 | | | | |
Node 2 | | | | |
Node 3 | | | | |
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
Midterm Corrections!
Due Friday 3/18!
How was the pace?
107