V. Adamchik Lecture 4
Analysis of Algorithms
University of Southern California
Binomial Heaps Greedy Algorithms
Reading: chapter 3 and 4
CSCI 570
Intuition: a kind of heaps
We want to create a heap with a better amortized complexity of insertion. This example will demonstrate that binary heaps do not provide a better upper bound for the worst-case complexity.
Insert 7, 6, 5, 4, 3, 2, 1 into an empty binary min-heap.
Binomial Trees Bk
The binomial tree Bk is defined as 1. B0 is a single node
2. Bk is formed by joining two Bk-1 trees
Binomial Heaps
A binomial heap is a collection (a linked list ) of at most Celling(log n) binomial trees (of unique rank) in increasing order of size where each tree has a heap ordering property.
Discussion Problem 1
Given a sequence of numbers: 3, 5, 2, 8, 1, 5, 2, 7.
Draw a binomial heap by inserting the above numbers reading them from left to right
Discussion Problem 2
How many binomial trees does a binomial heap with
25 elements contain? What are the ranks of those trees?
Insertion
What is its worst-case runtime complexity?
What is its amortized runtime complexity?
Building: Binomial vs Binary Heaps
The cost of inserting n elements into a binary heap, one after the other, is Θ(n log n) in the worst-case.
If n is known in advance, we run heapify, so a binary heap can be constructed in time Θ(n).
The cost of inserting n elements into a binomial heap, one after the other, is Θ(n) (amortized cost), even if n is not known in advance.
93
12 6 14
8
deleteMin()
min
15 12 17
10
11
20 23
deleteMin()
Discussion Problem 3
Devise an algorithm for merging two binomial heaps and discuss its complexity. Merge B0B1B2B4 with B1B4.
.
Heaps
Binary
Binomial
Fibonacci
findMin
Θ(1)
Θ(1)
deleteMin
Θ(log n)
Θ(log n)
insert
Θ(log n)
Θ(1) (ac)
decreaseKey
Θ(log n)
Θ(log n)
merge
Θ(n)
Θ(log n)
ac – amortized cost.
FIBONACCI HEAPS
Idea: relaxed (lazy) binomial heaps Goal: decreaseKey in O(1) ac.
The algorithm is outside of the scope of this course.
.
Heaps
Binary
Binomial
Fibonacci
findMin
Θ(1)
Θ(1)
Θ(1)
deleteMin
Θ(log n)
Θ(log n)
O(log n) (ac)
insert
Θ(log n)
Θ(1) (ac)
Θ(1)
decreaseKey
Θ(log n)
Θ(log n)
Θ(1) (ac)
merge
Θ(n)
Θ(log n)
Θ(1) (ac)
decreaseKey: example
Suppose we want to change 11 to 5.
93
12 6 15 12 14 17
8
10
20
11
23
Greedy Algorithms
The Money Changing Problem
We are to make a change of $0.40 using use US currency and assuming that there is an unlimited supply of coins.
SubOptimal solution
Greedy Algorithm does not always yield the global optimal solution.
• • • •
What is Greedy Algorithm?
There is no formal definition…
It is used to solve optimization problems
It makes a local optimal choice at each step Earlier decisions are never undone
Do not always yield optimal solutions
Elements of the greedy strategy
There is no guarantee that such a greedy algorithm exists, however a problem to be solved must obey the following two common properties:
greedy-choice property
and
optimal substructure.
Scheduling Problem
There is a set of n requests. Each request i has a starting time s(i) and finish time f(i). Assume that all request are equally important and s(i) ≤ f(i). Our goal is to develop a greedy algorithm that finds the largest compatible (non-overlapping) subset of requests.
s(1) f(1) s(2)
f(2)
How do we choose requests?
Proof
Discussion Problem 4
Let’s consider a long, quiet country road with houses scattered very sparsely along it. We can picture the road as a long line segment, with an eastern endpoint and a western endpoint. You want to place cell phone base stations at certain points along the road so that every house is within four miles of one of the base stations.
Give an efficient algorithm that achieves this goal and uses as few base stations as possible.
>4 miles
<4 miles <4 miles <4 miles
The Minimum Spanning Tree
Find a spanning tree of the minimum total weight.
ORD
1
DEN
9
LAX
85
10
PIT
7
DCA
2
ATL
6
3
4
DFW
Kruskal's Algorithm
14223 822
1615 6 11 5 3 4
8417 958
76839
T/F Questions
1. Every graph has a spanning tree.
2. A Minimum Spanning Tree is unique.
3. Kruskal’s algorithm can fail in the presence of negative cost edges.
USC CSCI 570
Discussion Problem 5
You are given a graph G with all distinct edge costs. Let T be a minimum spanning tree for G. Now suppose that we replace each edge cost ce by its square, ce2, thereby creating a new graph G1 with the different distinct costs. Prove or disprove whether T is still an MST for this new graph G1.
Discussion Problem 6
You are given a minimum spanning tree T in a graph G = (V, E). Suppose we add a new edge (without introducing any new vertices) to G creating a new graph G1. Devise a linear time algorithm to find an MST in G1.
Prim's Algorithm
a
1
b2c2d
357 e3f
4
2
Complexity of Prim's Algorithm