CS计算机代考程序代写 AI algorithm Announcements

Announcements

Announcements

• HW 3 Due Today

• Exam Next Friday

– Basically the same rules as the last exam.

– Complete exam instructions assignment on
gradescope.

– If you cannot make the usual time (and could last
time), please email me by Wednesday.

– Review video on course webpage.

Exam Topics

• Chapters 4 and 2

– BFS

– Dijkstra

• Priority Queues

– Bellman-Ford

– Shortest Paths in DAGs

– Karatsuba

– Master Theorem

– Merge Sort

– Order Statistics

– Binary Search

– Closest Pair of Points

Greedy Algorithms (Ch 5)

• Basics

• Change making

• Interval scheduling

• Exchange arguments

• Optimal caching

• Huffman codes

• Minimal spanning trees

Greedy Algorithms

Often when trying to find the optimal solution
to some problem you need to consider all
your possible choices and how they might
interact with other choices down the line.

But sometimes you don’t. Sometimes you can
just take what looks like the best option for
now and repeat.

Greedy Algorithms

General Algorithmic Technique:

1. Find decision criterion

2. Make best choice according to criterion

3. Repeat until done

Surprisingly, this sometimes works.

Example: Making Change

Problem: How do you make exact change for
$12.83 using the fewest number of bills/coins?

Idea: Want to use biggest denominations
possible.

Amount Left: Bills used:

$12.83 $2.83 $10 $1.83 $1 $0.83 $1 $0.58 ¢25 $0.33 ¢25 $0.08

¢25

$0.03

¢5

$0.02

¢1

$0.01

¢1

$0.00

¢1

10 bills/coins

This is the best
possible!

Change Making

Note: This technique always works for making
change when using American currency.

Note: It does not always work when using other
currencies.

Example: Weirdtopia has $1, $5, $7 bills.

Problem: Make change for $10 in Weirdtopia.

Greedy: Optimal:

$7+$1+$1+$1 = $10 $5+$5 = $10

Things to Keep in Mind about Greedy
Algorithms

• Algorithms are very natural and easy to write
down.

• However, not all greedy algorithms work.

• Proving correctness is important.

Interval Scheduling

Imagine that you are trying to schedule as many
classes as possible without any conflicting
lectures.

Problem: Given a collection C of intervals, find a
subset S ⊆ C so that:

1. No two intervals in S overlap.

2. Subject to (1), |S| is as large as possible.

Question: Interval Scheduling

What is the greatest number of non-overlapping
intervals that can be picked from the below?

A) 0

B) 1

C) 2

D) 3

E) 4

First Interval
• Note: S must consist of intervals

J1 = [x1,y1], J2 = [x2,y2], …
where yi < xi+1. • What is the best J1? – Only way J1 matters is that y1 < x2. – Want y1 as small as possible. • Once, we’ve picked J1, have another interval cover problem among the intervals that don’t overlap J1. • Algorithm: repeatedly pick non-overlapping interval with smallest max. Algorithm IntervalScheduling(C) S ← {} While(some interval in C doesn’t overlap any in S) Let J be the non-overlapping interval with smallest max Add J to S Return S O(n) iterations O(n) time Runtime: O(n2) Proof of Correctness • Algorithm produces J1, J2,…,Js with Ji = [xi,yi]. • Consider some other solution K1, K2,…,Kt with Ki = [wi,zi]. Claim: For each m ≤ t, ym ≤ zm. In particular, s ≥ t. Proof of Claim Use Induction on m. Base Case: m = 1. J1 is the interval with smallest max, so y1 ≤ z1. Inductive Step: Assume ym ≤ zm. • Jm+1 has smallest y for any [x,y] with x > ym.

• Km+1 = [wm+1, zm+1] has
wm+1 > zm ≥ ym

• Therefore, ym+1 ≤ zm+1.

Optimization

• Original algorithm checks all intervals every
time.

• Only need to consider intervals in increasing
order of y.

• Sort once.

Optimized Algorithm

IntervalScheduling(C)

Sort C by y-value

S ← {}

y
max

← -∞

For J = [x,y] in C

If x > y
max

Add J to S

y
max

← y

Return S

O(n log(n))

O(n)

Runtime:
O(n log(n))

Question: Other Greedy Candidates

What are other possible candidate greedy
decision procedures for interval scheduling?

• Smallest max

• Shortest

• Fewest overlaps

• Largest min

• Smallest min

• Largest max

Only these work!

Smallest Min

Greedy Optimal

Shortest

Greedy Optimal

Fewest Overlaps

Greedy Optimal

Proofs

As it is very easy to write down plausible greedy
algorithms for problems, but more difficult to
find correct ones, it is very important to be
able to prove that your algorithm is correct.

Fortunately, there is a standard proof technique
for greedy algorithms.

Exchange Argument

• Greedy algorithm makes a sequence of decisions D1,
D2, D3,…,Dn eventually reaching solution G.

• Need to show that for arbitrary solutions A that G ≥
A.

• Find sequence of solutions
A=A0, A1, A2,…,An = G
so that:

– Ai ≤ Ai+1
– Ai agrees with D1,D2,…,Di

Exchange Argument

In particular, we need to show that given any Ai
consistent with D1,…,Di we can find an Ai+1 so
that:

• Ai+1 is consistent with D1,…,Di+1
• Ai+1 ≥ Ai
Then we inductively construct sequence

A=A0 ≤ A1 ≤ A2 ≤ … ≤ An = G

Thus, G ≥ A for any A. So G is optimal.

Exchange Argument for Interval
Packing

• What decisions does greedy algorithm make?

– Di, i
th interval equals Ji.

• Need to show that IF we have a solution that
agrees with first i decisions, can make it agree
with i+1 without making it worse.

• Have solution: J1,J2,…,Ji,Ki+1,…,Km
– Need to modify to use interval Ji+1.

Inductive Step

Greedy solution: J1,J2,…,Jn Ji = [xi,yi]

Current solution: J1,J2,…,Ji,Ki+1,…,Km Ki = [wi,zi]

Claim: J1,J2,…,Ji,Ji+1,Ki+2,…,Km is a valid solution.

Proof: Need to verify:

• xi+1 > yi: This is because Ji, Ji+1 don’t overlap.

• wi+2 > yi+1: This is because wi+2 > zi+1 ≥ yi+1.

Example

Greedy Solution Arbitrary Solution