CS2040S

Data Structures and Algorithms

Last
wee
kend
… Welcome!

https://hacknroll2023.devpost.com/project-gallery
is open
How to Search!

Algorithm Analysis
– Big-O Notation
– Model of computation

Searching

Peak Finding
– 1-dimension
– 2-dimensions
Admin
Archipelago
– With some browsers/devices don’t redirect properly from
the link.
– So… 404 error
– No workaround yet… try different browser/device?

Coursemology
– Safari V.14:
– Misplaced title bar
– Cannot access assignment 2.
– Use different browser or upgrade safari.
Admin

Tutorial and Recitations

DO NOT make any changes directly on ModReg.

All changes have to go through Coursemology appeal.

– If you change directly, you risk being dropped from the

class.
– Please do not e-mail me or the module staff directly if you
are unhappy with your slot.
Admin

Tutorial and Recitations

– Current assignment available on ModReg.
– 99% / 97% got one of their first choices.

– But 16 (tutorial) and 15 (recitation) still do not have

slots.
Admin

Tutorial and Recitation Registration

– There is an appeal form available on Coursemology
– Swaps (where both parties agree) are okay.
– Otherwise, we will allow changes into available
sessions.
– (If a session has no space, we will not move you
there.)
Admin

Tutorial Availability
Much availability: Overfull:
Wed. 3-5pm Tues. 12-2pm
Wed. 4-6pm Tues. 2-4pm

Some availability: At capacity:

Wed. 11-1pm Tues. 1-3pm.
Tues. 3-5pm Wed. 9-11am
Admin

Recitation Availability
Availability: Overfull:
Thurs. 2-3pm Thurs. 1-2pm
Thurs. 3-4pm
Fri. 11-12pm

Some availability:
Thur. 12-1pm
Fri. 1-2pm
How to Search!

Algorithm Analysis
– Big-O Notation
– Model of computation

Searching

Peak Finding
– 1-dimension
– 2-dimensions
Algorithm Analysis
Warm up: which takes longer?
void pushAll(int k) { void pushAdd(int k) {
for (int i=0; for (int i=0; i<= k; i++)
i<= 100*k; {
i++) for (int j=0; j<= k; j++){
{ stack.push(i+j);
stack.push(i); }
} }
} }

On Zoom
Algorithm Analysis
Warm up: which takes longer?
void pushAll(int k) { void pushAdd(int k) {
for (int i=0; for (int i=0; i<= k; i++)
i<= 100*k; {
i++) for (int j=0; j<= k; j++){
{ stack.push(i+j);
stack.push(i); }
} }
} }

100k push operations k2 push operations

 Which grows faster?

T(k) = 100k T (k) = k2

T (0) = 0 T (0) = 0

T (1) = 100 T (1) = 1

T (100) = 10,000 T (100) = 10,000

T(1000) = 100,000 T(1000) = 1,000,000

Always think of big input
Big-O Notation
How does an algorithm scale?
– For large inputs, what is the running time?
– T(n) = running time on inputs of size n

Time
T(n)

n
Big-O Notation

Definition: T(n) = O(f (n)) if T grows no faster than f

T(n) = O(f (n)) if:

– there exists a constant c > 0
– there exists a constant n0 > 0

such that for all n > n0:

T(n) ≤ c f (n)
Big-O Notation

T(n)

n
Big-O Notation

T(n) = O(f(n))

c f(n)

T(n)

n=n0 n
Big-O Notation
c f(n)

T(n) = O(f(n))

T(n)

n=n0 n
Big-O Notation

Example proof: T(n) = O(n2)

T(n) = 4n2 + 24n + 16

< 4n2 + 24n2 + n2 (for n > n0= 4)
= 29n2
= O(n2) (for c = 29)
 Example

T(n) big-O

T(n) = 1000n T(n) = O(n)

T(n) = 1000n T(n) = O(n2)

Not
T(n) = n2 T(n) ≠ O(n) tight

T(n) = 13n2 + n T(n) = O(n2)

Big-O Notation

Definition: T(n) = O(f (n)) if T grows no faster than f

T(n) = O(f (n)) if:

– there exists a constant c > 0
– there exists a constant n0 > 0

such that for all n > n0:

T(n) ≤ c f (n)
 Big-O Notation as Upper Bound
f(n)
T(n) = O(f(n))
Time
Namely, T(n) cannot be faster
than O(f (n))
T(n)

n
How about Lower bound?
 How about Lower bound?

Time

Namely, T(n) cannot be slower

than O(f (n))
T(n)

f(n)

n=n0
n
Big-O Notation

Definition: T(n) = W(f (n)) if T grows no slower than f

T(n) = W(f (n)) if:

– there exists a constant c > 0
– there exists a constant n0 > 0

such that for all n > n0:

T(n) ≥ c f(n)
 Example

T(n) Asymptotic

T(n) = 1000n T(n) = W(1)

T(n) = n T(n) = W(n)

T(n) = n2 T(n) = W(n)

T(n) = 13n2 + n T(n) = W(n2)

Big-O Notation

Exercise:
True or false:
“f (n) = O(g(n)) if and only if g (n) = W(f (n))”
Prove that your claim is correct using the definitions
of O and W or by giving an example.
Big-O Notation

Definition: T(n) = Q(f (n)) if T grows at the same rate as f

T(n) = Q(f (n)) if and only if:

– T(n) = O(f (n)) and
– T(n) = W(f (n))
Big-O Notation

T(n) = Q(f(n))

c1 f(n)
T(n)

c2 f(n)

n
 Example

T(n) big-O

T(n) = 1000n T(n) = Q(n)

T(n) = n T(n) ≠ Q(1)

T(n) = 13n2 + n T(n) = Q(n2)

T(n) = n3 T(n) ≠ Q(n2)

Big-O Notation

Some simple rules for most cases…

Big-O Notation
Function Name
5 Constant
loglog(n) double log
log(n) logarithmic
Order or size: log2(n) Polylogarithmic
n linear
nlog(n) log-linear
n3 polynomial
n3log(n)
n4 polynomial
2n exponential
22n
n! factorial
Big-O Notation

Rules:
If T(n) is a polynomial of degree k then:

T(n) = O(nk)

Example:
10n5 + 50n3 + 10n + 17 = O(n5)
Big-O Notation

Rules:
If T(n) = O(f(n)) and S(n) = O(g(n)) then

T(n) + S(n) = O(f(n) + g(n))

Example:
10n2 = O(n2)
5nlog(n) = O(nlog(n))
10n2 + 5nlog(n) = O(n2 + nlog(n)) = O(n2)
Big-O Notation

Rules:
If T(n) = O(f (n)) and S(n) = O(g(n)) then:

T(n)*S(n) = O(f (n)*g(n))

Example:
10n2 = O(n2)
5n = O(n)
(10n2)(5n) = 50n3 = O(n*n2) = O(n3)
Why don’t you try a few?

is open
 4n2log(n) + 8n + 16 = ?

1. O(log n)
2. O(n)
3. O(nlog n)
4. O(n2log n)
5. O(2n)
 22n + 2n + 2 =
1. O(n)
2. O(n6)
3. O(2n)
4. O(22n)
5. O(nn)
 log(n!) =
1. O(log n)
2. O(n)
3. O(n log n)
4. O(n2)
5. O(2n)
 log(n!) =
1. O(log n)
2. O(n)
3. O(n log n)
4. O(n2)
5. O(2n)

Hint: Sterling’s Approximation

p ⇣ n ⌘n
n! ⇡ 2⇡n
e
In General
Model of Computation?

Different ways to “compute”:

– Sequential (RAM) model of computation
– Parallel (PRAM, BSP, Map-Reduce)
– Circuits
– Turing Machine
– Counter machine
– Word RAM model
– Quantum computation
– Etc.
Model of Computation

Sequential Computer
– One thing at a time

– All operations take constant time

Addition, subtraction, multiplication, comparison
Algorithm Analysis
Example:
void sum(int k, int[] intArray) {
1 assignment

int total=0;
1 assignment
for (int i=0; i<= k; i++){ k+1 comparisons
total = total + intArray[i]; k increments
}
k array access
return total; k addition
} k assignment

1 return

Total: 1 + 1 + (k+1) + 3k + 1 = 4k+4 = O(k)

Algorithm Analysis
What is the cost of this
operation?
Example:
void sum(int k, int[] intArray) {
int total=0;
String name="Stephanie";
for (int i=0; i<= k; i++){
total = total + intArray[i];
name = name + "?"
}
return total;
Not 1!
} Not constant!
Not k!
Moral: all costs are not 1.
Rules
Loops
cost = (# iterations)x(max cost of one iteration)

int sum(int k, int[] intArray) {

int total=0;
for (int i=0; i<= k; i++){
total = total + intArray[i];
}
return total;
}
Rules
Nested Loops
cost = (# iterations)(max cost of one iteration)

int sum(int k, int[] intArray) {

int total=0;
for (int i=0; i<= k; i++){
for (int j=0; j<= k; j++){
total = total + intArray[i];
}
}
return total;
}
Rules
Sequential statements
cost = (cost of first) + (cost of second)

int sum(int k, int[] intArray) {

for (int i=0; i<= k; i++)
intArray[i] = k;
for (int j =0; j<= k; j++)
total = total + intArray[i];
return total;
}
Rules
if / else statements
cost = max(cost of first, cost of second)
<= (cost of first) + (cost of second)
void sum(int k, int[] intArray) {
if (k > 100)
doExpensiveOperation();
else
doCheapOperation();
return;
}
Rules
For recursive function calls…..
Recurrences
T(n) = 1 + T(n - 1) + T(n - 2)
= O(2n)
T(n-1) T(n-1)

int fib(int n) {
if (n <= 1)
return n;
else
return fib(n-1) + fib(n-2);
}
 What is the running time?

for (int i = 0; i<n; i++)

for (int j = 0; j<i; j++)
store[i] = i + j;
1. O(1)
2. O(n)
3. O(n log n)
4. O(n2)
5. O(n2 log n)
6. O(2n)
is open
Today: Divide and Conquer!

Algorithm Analysis
– Big-O Notation
– Model of computation

Searching

Peak Finding
– 1-dimension
– 2-dimensions
 (Courtesy: MIT Puzzle Hunt, 2019)
Puzzle of the Week: Bubbly
• Two player game
• Players alternate popping bobbles
• The last player to pop a bubble wins.

Find the best

first move.
Pop(H)
Today: Divide and Conquer!

Algorithm Analysis
– Big-O Notation
– Model of computation

Searching

Peak Finding
– 1-dimension
– 2-dimensions
Binary Search
Sorted array: A[0..n-1]

Search for k in array A.

Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element: 7
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element: 7
– Compare 17 to middle element: 17 > 7
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element: 7
– Compare 17 to middle element: 17 > 7
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element: 7
– Compare 17 to middle element: 17 > 7
– Recurse on right half
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element
– Compare 17 to middle element
– Recurse
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element
– Compare 17 to middle element
– Recurse
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element
– Compare 17 to middle element
– Recurse
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element
– Compare 17 to middle element
– Recurse
Binary Search
Sorted array: A[0..n-1]

Search for 17 in array A.

– Find middle element
– Compare 17 to middle element
– Recurse
Problem Solving: Reduce the Problem
Sorted array: A[0..n-1]

Reduce-and-Conquer:
– Start with n elements to search.
– Eliminate half of them.
– End with n/2 elements to search.
– Repeat.
How hard is binary search?

How many of you think you could write a correct

implementation of binary search, right now?

is open
Jon Bentley
Jon Bentley
How hard is binary search?

How many of you think you could write a correct

implementation of binary search, right now?
Try it yourself!
Binary Search (buggy)
Sorted array: A[0..n-1]

Search(A, key, n)
begin = 0 is open
end = n
while begin != end do:
if key < A[(begin+end)/2] then
end = (begin+end)/2 – 1
else begin = (begin+end)/2
return A[begin]
Bug 1
Sorted array: A[0..n-1]

Search(A, key, n)
begin = 0
array out of bounds!
end = n
while begin != end do:
if key < A[(begin+end)/2] then
end = (begin+end)/2 – 1
else begin = (begin+end)/2
return A[end]
Bug 1
Sorted array: A[0..n-1]

Search(A, key, n)
array out of bounds!
begin = 0 (Can’t happen because of other bugs…)
end = n
while begin != end do:
if key < A[(begin+end)/2] then
end = (begin+end)/2 – 1
else begin = (begin+end)/2
return A[end]
Bug 1
Sorted array: A[0..n-1]

Search(A, key, n)
begin = 0
end = n-1
while begin != end do:
if key < A[(begin+end)/2] then
end = (begin+end)/2 – 1
else begin = (begin+end)/2
return A[end]
Bug 2 Example: search(7)
• begin = 0, end = 1
Sorted array:• A[0..n-1]
mid = (0+1)/2 = 0
• key >= A[mid] è begin = 0

5 10

Search(A, key, n)
begin = 0 May not terminate!
end = n-1
while begin != end do: round down
if key < A[(begin+end)/2] then
end = (begin+end)/2 – 1
else begin = (begin+end)/2
return A[end]
Bug 2 Example: search(2)
• begin = 0, end = 1
Sorted array:• A[0..n-1]
mid = (0+1)/2 = 0
• key < A[mid] è end = 0 – 1 = -1

5 10

Search(A, key, n)
begin = 0 end < begin
end = n-1
while begin != end do: subtract?
if key < A[(begin+end)/2] then
end = (begin+end)/2 – 1
else begin = (begin+end)/2
return A[end]
Bug 3
Sorted array: A[0..n-1]

Search(A, key, n)
begin = 0
end = n-1
while begin != end do:
if key < A[(begin+end)/2] then
end = (begin+end)/2 – 1
else begin = (begin+end)/2
return A[end] Useful return value?
Binary Search

Specification:
– Returns element if it is in the array.
– Returns “null” if it is not in the array.

Alternate Specification:
– Returns index if it is in the array.
– Returns -1 if it is not in the array.
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n)

begin = 0
end = n-1
while begin < end do:
if key <= A[(begin+end)/2] then
end = (begin+end)/2
else begin = 1+(begin+end)/2
return (A[begin]==key) ? begin : -1
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n)

less-than-or-equal
begin = 0
end = n-1
while begin < end do:
if key <= A[(begin+end)/2] then
end = (begin+end)/2
else begin = 1+(begin+end)/2
return (A[begin]==key) ? begin : -1
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n)

strictly greater than
begin = 0
end = n-1
while begin < end do:
if key <= A[(begin+end)/2] then
end = (begin+end)/2
else begin = 1+(begin+end)/2
return (A[begin]==key) ? begin : -1
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n) Array of out

begin = 0 bounds?

end = n-1
while begin < end do:
if key <= A[(begin+end)/2] then
end = (begin+end)/2
else begin = 1+(begin+end)/2
return (A[begin]==key) ? begin : -1
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n) Array of out

begin = 0 bounds?
No: division
end = n-1 rounds down.
while begin < end do:
if key <= A[(begin+end)/2] then
end = (begin+end)/2
else begin = 1+(begin+end)/2
return (A[begin]==key) ? begin : -1
Bug 4
Sorted array: A[0..n-1]

int search(A, key, n)

What if begin > MAX_INT/2?
begin = 0
end = n-1
while begin < end do:
if key <= A[(begin+end)/2] then
end = (begin+end)/2
else begin = 1+(begin+end)/2
return (A[begin]==key) ? begin : -1
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n) What if begin > MAX_INT/2?

begin = 0
Overflow error: begin+end > MAX_INT
end = n-1
while begin < end do:
if key <= A[(begin+end)/2] then
end = (begin+end)/2
else begin = 1+(begin+end)/2
return (A[begin]==key) ? begin : -1
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n)

begin = 0
end = n-1
while begin < end do:
mid = begin + (end-begin)/2;
if key <= A[mid] then
end = mid
else begin = mid+1
return (A[begin]==key) ? begin : -1
Moral of the Story

Easy algorithms are *hard* to write correctly.

Binary search is 9 lines of code.

If you can’t write 9 correct lines of code, how do
you expect to write thousands of lines of bug-free
code??
Precondition and Postcondition

Precondition:
– Fact that is true when the function begins.
– Usually important for it to work correctly.

Postcondition:
– Fact that is true when the function ends.
– Usually useful to show that the computation was
done correctly.
Binary Search
is open
Sorted array: A[0..n-1]

int search(A, key, n)

What are useful
begin = 0 preconditions and
end = n-1 postconditions?
while begin < end do:
mid = begin + (end-begin)/2;
if key <= A[mid] then
end = mid
else begin = mid+1
return (A[begin]==key) ? begin : -1
Binary Search
Functionality:
– If element is in the array, return index of element.
– If element is not in array, return -1.
Binary Search
Functionality:
– If element is in the array, return index of element.
– If element is not in array, return -1.

Preconditions: Good practice:

Validate pre-conditions
– Array is of size n when possible.

– Array is sorted
Binary Search
Functionality:
– If element is in the array, return index of element.
– If element is not in array, return -1.

You can usually check

Preconditions: this directly.
– Array is of size n
– Array is sorted
Binary Search
Functionality:
– If element is in the array, return index of element.
– If element is not in array, return -1.

Preconditions:
– Array is of size n
– Array is sorted
Should we do input
validation to make sure
array is sorted??

or on Zoom.
Binary Search
Functionality:
– If element is in the array, return index of element.
– If element is not in array, return -1.

Preconditions:
– Array is of size n
– Array is sorted
Should we do input
validation to make sure
array is sorted??
NO! Too slow!
Binary Search
Functionality:
– If element is in the array, return index of element.
– If element is not in array, return -1.

Preconditions:
– Array is of size n
– Array is sorted

Postcondition:
– If element is in the array: A[begin] = key
Invariants

Invariant:
– relationship between variables that is always true.
Invariants

Invariant:
– relationship between variables that is always true.

Loop Invariant:
– relationship between variables that is true at the
beginning (or end) of each iteration of a loop.
Binary Search
is open
Sorted array: A[0..n-1]

int search(A, key, n)

begin = 0 What are useful
invariants?
end = n-1
while begin < end do:
mid = begin + (end-begin)/2;
if key <= A[mid] then
end = mid
else begin = mid+1
return (A[begin]==key) ? begin : -1
Binary Search
Loop invariant:
– A[begin] £ key £ A[end]

Interpretation:
– The key is in the range of the array

begin end
Binary Search
Loop invariant:
– A[begin] £ key £ A[end]

Interpretation:
– The key is in the range of the array

Validation (in debug mode; disable for production?):

if ((A[begin] > key) or (A[end] < key))
System.out.println(“error”);
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n)

Is the loop invariant always true?
begin = 0
end = n-1 or on Zoom.
while begin < end do:
mid = begin + (end-begin)/2;
if key <= A[mid] then
end = mid
else begin = mid+1
return (A[begin]==key) ? begin : -1
Binary Search
Sorted array: A[0..n-1]

int search(A, key, n)

To enforce invariant, we would
begin = 0 need an extra step. Or we can
end = n-1 refine the invariant.
while begin < end do:
mid = begin + (end-begin)/2;
if key <= A[mid] then
end = mid
else begin = mid+1
return (A[begin]==key) ? begin : -1
Binary Search

n/2

n/4

n/8
Binary Search
Sorted array: A[0..n-1]

Iteration 1: (end – begin) = n

Iteration 2: (end – begin) = n/2
Iteration 3: (end – begin) = n/4
Another invariant!
…
Iteration k: (end – begin) <= n/2k

n/2k = 1 è k = log(n)
Key Invariants:
Correctness:
– A[begin] £ key £ A[end]

Performance:
– (end-begin) <= n/2k in iteration k.
Binary Search
Sorted array: A[0..n-1]

Not just for searching arrays:

– Assume a complicated function:
int complicatedFunction(int s)
– Assume the function is always increasing:
complicatedFunction(i) < complicatedFunction(i+1)
– Find the minimum value j such that:
complicatedFunction(j) > 100
A problem…
Tutorial allocation
A problem…
Tutorial allocation
T1

T2

T3
Tutorials
(in order T4
of tutor
preference)
T5

T6

T7

T8
A problem…
Tutorial allocation
T1 Students want
certain tutorials.
T2

T3
Tutorials
(in order T4
of tutor
preference)
T5

T6

T7

T8
A problem…
Tutorial allocation
T1 Students want
certain tutorials.
T2

T3 We want each
Tutorials tutorial to have
(in order T4
of tutor < 18 students..
preference)
T5

T6

T7

T8
A problem…
Tutorial allocation
T1 Students want
certain tutorials.
T2

T3 We want each
Tutorials tutorial to have
(in order T4
of tutor < 18 students..
preference)
T5

T6 How many tutorials

do we need to run?
T7

T8
A problem…
Tutorial allocation
T1 Students want
certain tutorials.
T2

T3 We want each
Tutorials tutorial to have
(in order T4
of tutor < 18 students..
preference)
T5

T6 How many tutorials

do we need to run?
T7

T8
A problem…
Tutorial allocation
T1 Can we do
greedy allocation?
T2
First, fill T1.
T3 Then fill T2.
Tutorials Then fill T3.
(in order T4 …
of tutor
preference) Stop when all
T5 students are
allocated
T6

T7

T8 or on Zoom.
A problem…
Tutorial allocation
T1 Can we do
greedy allocation?
T2
NO
T3
Tutorials Assume max
(in order T4 tutorial size is 1.
of tutor
preference)
T5 Assign student 1 to
tutorial 1.
T6
Now we need all 8
T7 tutorials.
T8
A problem…
Tutorial allocation
T1 Can we do
greedy allocation?
T2
NO
T3
Tutorials Assume max
(in order T4 tutorial size is 1.
of tutor
preference)
T5 Assign student 1 to
tutorial 1.
T6
Now one student
T7 has no feasible
allocation!
T8
A problem…
Tutorial allocation
T1 Assume we can
solve allocation
T2 problem:

T3 Given a fixed set of

tutorials and a fixed
Tutorials
(in order T4 set of students, find
of tutor an allocation where
preference)
T5 every student has a
slot.
T6
Warning:
• may be > 18 students in
T7 a slot!
• minimizes max students
T8 in a slot.
A problem…
Tutorial allocation
T1 How to find
minimum number
T2 of tutorials that we
need to open to
T3 ensure: no tutorial
Tutorials has more than 18
(in order T4 students.
of tutor
preference)
T5

T6

T7

T8
A problem…
Tutorial allocation
T1 Observation:

T2 Number of
students in
T3 BIGGEST tutorial
Tutorials only decreases as
(in order T4 number of tutorials
of tutor
preference) increases.
T5

T6 Monotonic
function of
T7 number of
tutorials!
T8
A problem…
Tutorial allocation
T1
Monotonic
T2
function of
number of
T3
tutorials!
Tutorials
(in order T4
of tutor
preference)
T5

T6 Binary Search

T7

T8
A problem… T1

T2

Tutorial allocation T3

T4

Solution: T5

T6
Binary Search
T7

Define:
T8

MaxStudents(x) = number of students in most crowded tutorial,

if we offer x tutorials.
Binary Search
T1

T2

T3

T
4

MaxStudents(x) = number of students in most T5

crowded tutorial, T
6

if we offer x tutorials. T7

Search(n) T
8

begin = 0
end = n-1
while begin < end do:
mid = begin + (end-begin)/2;
if MaxStudents(mid) <= 18 then
end = mid
else begin = mid+1
return begin
Binary Search
Sorted array: A[0..n-1]

Not just for searching arrays:

– Assume a complicated function:
int complicatedFunction(int s)
– Assume the function is always increasing:
complicatedFunction(i) < complicatedFunction(i+1)
– Find the minimum value j such that:
complicatedFunction(j) > 100
Today: Divide and Conquer!

Algorithm Analysis
– Big-O Notation
– Model of computation

Searching

Peak Finding
– 1-dimension
– 2-dimensions