CS代考程序代写 algorithm Lecture 3:

Lecture 3:
Greedy algorithms (Adv.)
The University of Sydney
Page 1

Shortest path trees vs minimum spanning trees
Shortest path trees and minimum spanning trees can be very different
In tutorial, we saw the following example.
Can it be worse?
The University of Sydney
Page 2

Light approximate shortest path tree (LAST)
Given a graph G = (V,E) with edge costs c, and a source vertex s, an (!,”)-LAST is a spanning tree T with
– c(T) ≤ ! c(MST)
– For every v, dT(s,v) ≤ ” dG(s,v)
Previous example
The University of Sydney
Page 3

Light approximate shortest path tree (LAST)
Theorem There exists an efficient algorithm that finds a (2,2)- LAST.
Proof
– ALG:
– Compute MST T of G – H=T
– For each v in DFS(T)
– If dH(s,v) > 2 dG(s,v): – Add(s,v)toH
– Output shortest path tree of H The University of Sydney
Page 4

Light approximate shortest path tree (LAST)
Proof
– ALG:
– Compute MST T of G
– H=T
– For each v in DFS(T)
– If dH(s,v) > 2 dG(s,v):
– Add(s,v)toH
– Output shortest path tree of H
– Cost analysis:
– Let A be set of vertices for which (s,v) was added
– pred(v) = predecessor of v in A according to tour order
The University of Sydney
Page 5

Lecture 4:
Divide and Conquer (Adv.)
The University of Sydney
Page 7
Fast Fourier Transform

The median problem
– The median is the “half-way” point of a set
– Given a sequence of n numbers, the median can be found as
follows:
– sort the numbers W(n log n)
– the median is the middle element (element at position “n/2”) – Can we find the median in linear time?
The University of Sydney
Page 8

The selection problem
– Given an unsorted array A with n numbers and a number k, find k-th smallest number in A
– Trivial solution: Sort the elements and return kth element.
– Can we do better than O(n log n) ?
– How could we solve this problem with divide and conquer?
The University of Sydney
Page 9

First attempt
– Suppose we could compute the median element of A in O(n) time
– If k < n/2 then find k-th among elements smaller than the median – If k > n/2 then find (k-n/2)-th among elements larger than the median
– This leads to the recurrence T(n) = T(n/2) + O(n), which solves to T(n) = O(n)
– But how can we compute the median in O(n) time?
The University of Sydney Page 10

Approximating the median
– We don’t need the exact median. Suppose we could find in O(n) time an element x in A such that
|A|/3 < rank(A, x) < 2|A|/3 – Then we get the recurrence T(n) = T(2n/3) + O(n) – Which again solves to T(n) = O(n) – To approximate the median we can use a recursive call! The University of Sydney Page 11 Median of 3-medians – Consider the following procedure – Partition A into |A|/3 groups of 3 – Sort each group – For each group find the median – Let x be the median of the medians x median of medians smallest median largest The University of Sydney Page 12 Median of 3-medians – Consider the following procedure – Partition A into |A|/3 groups of 3 – For each group find the median – Let x be the median of the medians – We claim that x has the desired property |A|/3 < rank(A, x) < 2|A|/3 smallest median largest – Half of the groups have a median that is smaller than x, and each group has two elements smaller than x, thus # elements smaller than x > 2 (|A|/6) = |A|/3 # elements greater than x > 2 (|A|/6) = |A|/3
The University of Sydney
Page 13

Median of 3-medians
– Consider the following procedure – Partition A into |A|/3 groups of 3 – Sort each group
– For each group find the median
– Let x be the median of the medians
– Claim: |A|/3 < rank(A, x) < 2|A|/3 – Partition the initial array of elements quicksort-style around x. – if k=n/2 we are done, return x smallest median largest smaller x larger – otherwise, if n/2 0.
– Caveat. Theoretical improvements to Strassen are progressively less practical.
The University of Sydney
Page 27

Summary: Divide-and-Conquer
– Divide-and-conquer.
– Break up problem into several parts.
– Solve each part recursively.
– Combine solutions to sub-problems into overall solution.
The University of Sydney
Page 28

Related Posts