IV s
Dijkstra’s
shortest
path
algorithm
s
_a
u s
S fsf
52 9 1 S3 fs y z S4 s Y 3 tf
SSI s y j t a
is
is
as
O
6
die
OLM Focus neighbours
0cal Decrease keycalls
tighter boundis Ocad
takesOCD
1
M
n ExtractMin’s Ocnlgn Oln Ign Ocnlgn
m Decreantay’s 0cmGa 0 mega 0 m
T.tn gnOnlgnmLM0 n
Spzaphs.OCn4n OCnlgu O nlgn
Demmiapaph.IE E oCn
0 Mtn 0cm assuming aconnectedgraph
Fib Aeapbinomial
heap
Kruskalis
Prints
ReverseDetete
N S
s b e d
Ttya X it i He
x X i X
h g fKruskal Reverse Delete X
Prim’s starting a
O
Kruskally u s
us
ReverseDetity
1
i
x
Xx
OH
0414
am’T
m
overallcomplexity OCHO mgm 10 mtg
0cm Lgm
Kruskal’s 0cm Gm
p
Ocmlgm myna
C zorba
a 0 mtg
n E
o
E
t
overallpref fufu m2
m2
Discussion 4
1. Hardy decides to start running to work in San Francisco city to get in shape. He prefers a
route that goes entirely uphill and then entirely downhill so that he could work up a sweat uphill
and get a nice, cool breeze at the end of his run as he runs faster downhill. He starts running
from his home and ends at his workplace. To guide his run, he prints out a detailed map of the
roads between home and work with k intersections and m road segments (any existing road
between two intersections). The length of each road segment and the elevations at every
intersection are given. Assuming that every road segment is either fully uphill or fully downhill,
give an efficient algorithm to find the shortest path (route) that meets Hardy’s specifications. If
no such path meets Hardy’s specifications, your algorithm should determine this. Justify your
answer.
2. You are given a graph representing the several career paths available in industry. Each node
represents a position and there is an edge from node v to node u if and only if v is a prerequisite
for u. Top positions are the ones which are not prerequisites for any positions. The cost of an
edge (v, u) is the effort required to go from one position v to position u. Ivan wants to start a
career and achieve a top position with minimum effort. Using the given graph can you provide
a alg i hm i h he ame ime c m le i a Dijk a ? Y ma a me he g a h i a
DAG.
3. You have a stack data type, and you need to implement a FIFO queue. The stack has the
usual POP and PUSH operations, and the cost of each operation is 1. The FIFO has two
operations: ENQUEUE and DEQUEUE. We can implement a FIFO queue using two stacks.
What is the amortized cost of ENQUEUE and DEQUEUE operations.
4. Given a sequence of numbers: 3, 5, 2, 8, 1, 5, 2, 7
a. Draw a binomial heap by inserting the above numbers reading them from left to right
b. Show a heap that would be the result after the call to deleteMin() on this heap
5. (a): Suppose we are given an instance of the Minimum Spanning Tree problem on a graph G.
Assume that all edges costs are distinct. Let T be a minimum spanning tree for this instance.
Now suppose that we replace each edge cost ce by its square, ce2 thereby creating a new
instance of the problem with the same graph but different costs. Prove or disprove: T is still a
MST for this new instance.
(b): Consider an undirected graph G = (V, E) with distinct nonnegative edge weights we 0.
Suppose that you have computed a minimum spanning tree of G. Now suppose each edge weight
is increased by 1: the new weights are c e = ce + 1. Does the minimum spanning tree change?
Give an example where it changes or prove it cannot change.
ie
H of
H o
o W
s
Aggregate Analysis
E t.am
A engraves t deque
ve
n pushes n pops n pushes 9
IF 34 Odd
a MST couldchange if we have
negative cost edges
b MST will stay the same since
orderofedges sortedbycost
will stay the same Kruskals’s
will pickexactly the same edges
for the MST
Before Lecture Notes – 4 & 5
Discussion 4