Transcript bYTEBoss

Introduction To Algorithms
CS 445
Discussion Session 2
Instructor: Dr Alon Efrat
TA : Pooja Vaswani
02/14/2005
Topics
• Radix Sort
• Skip Lists
• Random Variables
2
Radix Sort
Limit input to fixed-length numbers or words.
Represent symbols in some base b.
Each input has exactly d “digits”.
Sort numbers d times, using 1 digit as key.
Must sort from least-significant to most-significant digit.
Must use any “stable” sort, keeping equal-keyed items
in same order.
3
Radix Sort Example
Input data:
a b a
b a c
c a a
a c b
b a b
c c a
a a c
b b a
4
Radix Sort Example
Pass 1: Looking at rightmost position.
a b a
b a c
c a a
a c b
b a b
c c a
a a c
b b a
Place into appropriate pile.
a
b
c
5
Radix Sort Example
Pass 1: Looking at rightmost position.
b b a
Join piles.
c c a
c a a
b a b
a a c
a b a
a c b
b a c
a
b
c
6
Radix Sort Example
Pass 2: Looking at next position.
a b a
c a a
c c a
b b a
a c b
b a b
b a c
a a c
Place into appropriate pile.
a
b
c
7
Radix Sort Example
Pass 2: Looking at next position.
a a c
Join piles.
b a c
b a b
b b a
a c b
c a a
a b a
a
b
c c a
c
8
Radix Sort Example
Pass 3: Looking at last position.
c a a
b a b
b a c
a a c
a b a
b b a
c c a
a c b
Place into appropriate pile.
a
b
c
9
Radix Sort Example
Pass 3: Looking at last position.
Join piles.
a c b
b b a
a b a
b a c
c c a
a a c
b a b
c a a
a
b
c
10
Radix Sort Example
Result is sorted.
a a c
a b a
a c b
b a b
b a c
b b a
c a a
c c a
11
Radix Sort Algorithm
rsort(A,n):
For d = 0 to n-1
/* Stable sort A, using digit position d as the key. */
For i = 1 to |A|
Add A[i] to end of list ((A[i]>>d) mod b)
A = Join lists 0…b-1
(dn) time, where d is taken to be a constant.
12
Skip List
Below is an implementation of Skip List in which the topmost level is left
empty.
There is also an implementation in which the topmost level is never left
empty. ( As in the lecture notes )
S3
-
S2
-
15
S1
-
15
23
S0
-
15
23
+
10
+
+
36
+
13
Skip List
•
•
•
•
•
•
The definition of a dictionary
Definition of skip lists
Searching in skip lists
Insertion in skip lists
Deletion in skip lists
Probability and time analysis
14
Definition of Dictionary
• Primary use: to store elements so that they
can be located quickly using keys
• Motivation: each element in a dictionary
typically stores additional useful information
beside its search key. (eg: bank accounts)
• Red/black tree, hash table, AVL tree, Skip
lists
15
Dictionary ADT
• Size(): Returns the number of items in D
• IsEmpty(): Tests whether D is empty
• FindElement(k): If D contains an item with a key equal to k,
then it return the element of such an item
• FindAllElements(k): Returns an enumeration of all the
elements in D with key equal k
• InsertItem(k, e): Inserts an item with element e and key k
into D.
• remove(k): Removes from D the items with keys equal to k,
and returns an numeration of their elements
16
Definition of Skip List
•
A skip list for a set S of distinct (key,
element) items is a series of lists S0, S1 , …
, Sh such that
–
–
–
–
Each list Si contains the special keys + and -
List S0 contains the keys of S in nondecreasing
order
Each list is a subsequence of the previous one,
i.e.,
S0  S1  …  Sh
List Sh contains only the two special keys
17
Example of a Skip List
• We show how to use a skip list to implement the
dictionary ADT
S3
S2
-
S1
-
S0
-
+
-
+
31
23
12
23
26
31
34
31
34
+
64
44
56
64
78
+
18
Initialization
• A new list is initialized as follows:
• 1) A node NIL (+ ) is created and its key is set
to a value greater than the greatest key that
could possibly used in the list
• 2) Another node NIL (-) is created, value set to
lowest key that could be used
• 3) The level (high) of a new list is 1
• 4) All forward pointers of the header point to NIL
19
Searching in Skip List
- general description
• 1)
If S.below(p).the position below p in the
same tower is null. We are at the bottom and
have located the largest item in S with keys less
than or equal to the search key k. Otherwise, we
drop down to the next lower level in the present
tower to setting p  S.below(p).
• 2)
Starting at position p, we move p forward
until it is at the right-most position on the present
level such that key(p) <= k. We call this scan
forward step.
20
Searching in Skip List
• We search for a key x in a skip list as follows:
– We start at the first position of the top list
– At the current position p, we compare x with y 
key(after(p))
x = y: we return element(after(p))
x > y: we “scan forward”
x < y: we “drop down”
– If we try to drop down past the bottom list, we return
NO_SUCH_KEY
• Example: search for 78
21
Searching in Skip List Example
S3
-
S2
-
S1
-
S0
-
+
+
31
23
12
23
26
31
34
31
34
+
64
44
56
64
78
+
1) P is 64, at S1,+ is bigger than 78, we drop down
• At S0, 78 = 78, we reach our solution
22
Insertion
• The insertion algorithm for skip lists uses
randomization to decide how many
references to the new item (k,e) should be
added to the skip list
• We then insert (k,e) in this bottom-level list
immediately after position p. After inserting
the new item at this level we “flip a coin”.
• If the flip comes up tails, then we stop right
there. If the flip comes up heads, we move to
next higher level and insert (k,e) in this level
at the appropriate position.
23
Randomized Algorithms
• A randomized algorithm
performs coin tosses (i.e., uses
random bits) to control its
execution
• It contains statements of the
type
b  random()
if b = 0
do A …
else { b = 1}
do B …
• Its running time depends on
the outcomes of the coin
tosses
We analyze the expected
running time of a randomized
algorithm under the following
assumptions

the coins are unbiased, and
the coin tosses are
independent

The worst-case running time
of a randomized algorithm is
large but has very low
probability (e.g., it occurs when
all the coin tosses give “heads”)
24
Insertion in Skip List Example
1) Suppose we want to insert 15
2) Do a search, and find the spot between 10 and 23
3) Suppose the coin come up “head” three times
p2
S2 -
p1
S1 -
S0 -
S3 -
23
p0
10
23
36
+
+
S2 -
15
+
S1 -
15
23
+
S0 -
15
23
10
+
+
36
+
25
Deletion
• We begin by performing a search for the given
key k. If a position p with key k is not found, then
we return the NO SUCH KEY element.
• Otherwise, if a position p with key k is found (it
would be found on the bottom level), then we
remove all the position above p
• If more than one upper level is empty, remove it.
26
Deletion in Skip List Example
• 1) Suppose we want to delete 34
• 2) Do a search, find the spot between 23 and 45
• 3) Remove all the position above p
+
S3 -
p2
S2 -
34
p1
S1 -
S0 -
23
34
p0
12
23
34
45
+
S2 -
+
S1 -
+
S0 -
+
+
23
12
23
45
+
27
Probability Analysis
• Insertion, whether or not to increase h
• Worst case for find, insert, delete: O (n + h)
• Due to low probability events when every item
belongs to every level in S
• Very low probability that it will happen
• Not a fair assessment
28
Performance of a Dictionary by a Skip
List
•
•
•
•
•
•
•
Operation
Size, isEmpty
findElement
insertItem
Remove
FindAllElements
removeAll
Time
O(1)
O(log n) (expected)
O(log n) (expected)
O(log n) (expected)
O(log n + s) (expected)
O(log n + s) (expected)
- S being the extra matching keys we have to go through
29