1.

2 Five Representative Problems

 Interval Scheduling

Input. Set of jobs with start times and finish times.

Goal. Find maximum cardinality subset of mutually compatible
jobs.
jobs don't overlap

h Time
0 1 2 3 4 5 6 7 8 9 10 11

2
 Weighted Interval Scheduling

Input. Set of jobs with start times, finish times, and weights.
Goal. Find maximum weight subset of mutually compatible jobs.

23

12

20

26

13

20

11

16 Time
0 1 2 3 4 5 6 7 8 9 10 11

3
 Bipartite Matching

Input. Bipartite graph.

Goal. Find maximum cardinality matching.

A 1

B 2

C 3

D 4

E 5

4
 Independent Set

Input. Graph.
Goal. Find maximum cardinality independent set.
subset of nodes such that no two
joined by an edge

1 2

4 5
3

6 7

5
 Competitive Facility Location

Input. Graph with weight on each each node.

Game. Two competing players alternate in selecting nodes. Not
allowed to select a node if any of its neighbors have been
selected.

Goal. Select a maximum weight subset of nodes.

10 1 5 15 5 1 5 1 15 10

Second player can guarantee 20, but not 25.

6
 Five Representative Problems

Variations on a theme: independent set.

Interval scheduling: n log n greedy algorithm.

Weighted interval scheduling: n log n dynamic programming
algorithm.
Bipartite matching: nk max-flow based algorithm.
Independent set: NP-complete.
Competitive facility location: PSPACE-complete.

7
 Polynomial-Time

Brute force. For many non-trivial problems, there is a natural

brute force search algorithm that checks every possible solution.

Typically takes 2N time or worse for inputs of size N.

Unacceptable in practice.
n ! for stable matching
with n men and n women

Desirable scaling property. When the input size doubles, the

algorithm should only slow down by some constant factor C.

There exists constants c > 0 and d > 0 such that on

every input of size N, its running time is bounded by c
Nd steps.

Def. An algorithm is poly-time if the above scaling property holds.

choose C = 2d

8
 Worst-Case Analysis

Worst case running time. Obtain bound on largest possible

running time of algorithm on input of a given size N.

Generally captures efficiency in practice.

Draconian view, but hard to find effective alternative.

Average case running time. Obtain bound on running time of

algorithm on random input as a function of input size N.

Hard (or impossible) to accurately model real instances by
random distributions.

Algorithm tuned for a certain distribution may perform poorly
on other inputs.

9
 Worst-Case Polynomial-Time

Def. An algorithm is efficient if its running time is polynomial.

Justification: It really works in practice!


Although 6.02 × 1023 × N20 is technically poly-time, it would be
useless in practice.

In practice, the poly-time algorithms that people develop
almost always have low constants and low exponents.

Breaking through the exponential barrier of brute force
typically exposes some crucial structure of the problem.

Exceptions.

Some poly-time algorithms do have high constants and/or
exponents, and are useless in practice.

Some exponential-time (or worse) algorithms are widely used
because the worst-case instances seem to be rare.
simplex method
Unix grep

10
Why It Matters

11
2.2 Asymptotic Order of Growth
 Asymptotic Order of Growth

Upper bounds. T(n) is O(f(n)) if there exist constants c > 0 and n 0

≥ 0 such that for all n ≥ n0 we have T(n) ≤ c · f(n).

Lower bounds. T(n) is Ω(f(n)) if there exist constants c > 0 and n0

≥ 0 such that for all n ≥ n0 we have T(n) ≥ c · f(n).

Tight bounds. T(n) is Θ(f(n)) if T(n) is both O(f(n)) and Ω(f(n)).

Ex: T(n) = 32n2 + 17n + 32.


T(n) is O(n2), O(n3), Ω(n2), Ω(n), and Θ(n2) .

T(n) is not O(n), Ω(n3), Θ(n), or Θ(n3).

13
 Notation

Slight abuse of notation. T(n) = O(f(n)).


Asymmetric:
– f(n) = 5n3; g(n) = 3n2
– f(n) = O(n3) = g(n)
– but f(n) ≠ g(n).

Better notation: T(n) ∈ O(f(n)).

Meaningless statement. Any comparison-based sorting algorithm

requires at least O(n log n) comparisons.

Statement doesn't "type-check."

Use Ω for lower bounds.

14
 Properties

Transitivity.

If f = O(g) and g = O(h) then f = O(h).

If f = Ω(g) and g = Ω(h) then f = Ω(h).

If f = Θ(g) and g = Θ(h) then f = Θ(h).

Additivity.

If f = O(h) and g = O(h) then f + g = O(h).

If f = Ω(h) and g = Ω(h) then f + g = Ω(h).

If f = Θ(h) and g = O(h) then f + g = Θ(h).

15
 Asymptotic Bounds for Some Common Functions

Polynomials. a0 + a1n + … + adnd is Θ(nd) if ad > 0.

Polynomial time. Running time is O(nd) for some constant d

independent of the input size n.

Logarithms. O(log a n) = O(log b n) for any constants a, b > 0.

can avoid specifying the

base

Logarithms. For every x > 0, log n = O(nx).

log grows slower than every

polynomial

Exponentials. For every r > 1 and every d > 0, nd = O(rn).

every exponential grows faster than every

polynomial

16
2.4 A Survey of Common Running Times
 Linear Time: O(n)

Linear time. Running time is at most a constant factor times the

size of the input.

Computing the maximum. Compute maximum of n numbers a1,

…, an.
max ← a1
for i = 2 to n {
if (ai > max)
max ← ai
}

18
 Linear Time: O(n)

Merge. Combine two sorted lists A = a1,a2,…,an with B = b1,b2,…,bn

into sorted whole.

i = 1, j = 1
while (both lists are nonempty) {
if (ai ≤ bj) append ai to output list and increment i
else(ai ≤ bj)append bj to output list and increment j
}
append remainder of nonempty list to output list

Claim. Merging two lists of size n takes O(n) time.

Pf. After each comparison, the length of output list increases by
1.
19
 O(n log n) Time

O(n log n) time. Arises in divide-and-conquer algorithms.

also referred to as linearithmic time

Sorting. Mergesort and heapsort are sorting algorithms that

perform O(n log n) comparisons.

Largest empty interval. Given n time-stamps x1, …, xn on which

copies of a file arrive at a server, what is largest interval of time
when no copies of the file arrive?

O(n log n) solution. Sort the time-stamps. Scan the sorted list in
order, identifying the maximum gap between successive time-
stamps.

20
 Quadratic Time: O(n2)

Quadratic time. Enumerate all pairs of elements.

Closest pair of points. Given a list of n points in the plane (x1, y1),
…, (xn, yn), find the pair that is closest.

O(n2) solution. Try all pairs of points.

min ← (x1 - x2)2 + (y1 - y2)2

for i = 1 to n {
for j = i+1 to n {
d ← (xi - xj)2 + (yi - yj)2 don't need to
take square roots
if (d < min)
min ← d
}
}

Remark. Ω(n2) seems inevitable, but this is just an illusion. see chapter 5

21
 Cubic Time: O(n3)

Cubic time. Enumerate all triples of elements.

Set disjointness. Given n sets S1, …, Sn each of which is a subset

of
1, 2, …, n, is there some pair of these which are disjoint?

O(n3) solution. For each pairs of sets, determine if they are

disjoint.
foreach set Si {
foreach other set Sj {
foreach element p of Si {
determine whether p also belongs to Sj
}
if (no element of Si belongs to Sj)
report that Si and Sj are disjoint
}
}

22
 Polynomial Time: O(nk) Time

Independent set of size k. Given a graph, are there k nodes such

that no two are joined by an edge? k is a constant

O(nk) solution. Enumerate all subsets of k nodes.

foreach subset S of k nodes {

check whether S in an independent set
if (S is an independent set)
report S is an independent set
}
}


Check whether S is an independent set = O(k2).

Number of k element subsets =⎛n ⎞ n (n −1) (n − 2) L (n − k +1) nk
⎜ ⎟= ≤

O(k2 nk / k!) = O(nk). ⎝ ⎠
k k (k −1) (k − 2) L (2) (1) k!
poly-time for k=17,
but not practical

23
 Exponential Time

Independent set. Given a graph, what is maximum size of an

independent set?

O(n2 2n) solution. Enumerate all subsets.

S* ← φ
foreach subset S of nodes {
check whether S in an independent set
if (S is largest independent set seen so far)
update S* ← S
}
}

24
Chapter 5
Divide and
Conquer

Slides by Kevin Wayne.

Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.

25
 Divide-and-Conquer

Divide-and-conquer.

Break up problem into several parts.

Solve each part recursively.

Combine solutions to sub-problems into overall solution.

Most common usage.


Break up problem of size n into two equal parts of size ½n.

Solve two parts recursively.

Combine two solutions into overall solution in linear time.

Consequence.

Brute force: n2.

Divide-and-conquer: n log n. Divide et impera.
Veni, vidi, vici.
- Julius Caesar

26
5.1 Mergesort
 Sorting

Sorting. Given n elements, rearrange in ascending order.

Obvious sorting Non-obvious sorting applications.

applications. Data compression.
List files in a directory. Computer graphics.
Interval scheduling.
Organize an MP3
Computational biology.
library. Minimum spanning tree.
List names in phone Supply chain management.
book. Simulate a system of particles.
Display Google Book recommendations on
PageRank results. Amazon.
Load balancing on a parallel
Easier once sorted. computer.
Find the median. ...
Find the closest pair.
Binary search in a
database.
Identify statistical
outliers. 28
 Mergesort

Mergesort.

Divide array into two halves.

Recursively sort each half.

Merge two halves to make sorted whole.

Jon von Neumann

(1945)

A L G O R I T H M S

A L G O R I T H M S divide O(1)

A G L O R H I M S T sort 2T(n/2)

A G H I L M O R S T merge O(n)

29
 Merging

Merging. Combine two pre-sorted lists into a sorted whole.

How to merge efficiently?


Linear number of comparisons.

Use temporary array.

A G L O R H I M S T

A G H I

Challenge for the bored. In-place merge. [Kronrud, 1969]

using only a constant amount of extra storage

30