Example of SELECT (k, S) algorithm S = < 1, 10, 8, 5, 6, 3, 5, 4, 2, 4, 7, 5, 8, 8, 9, 24, 6, 16, 20, 11, 4, 3, 14, 19, 2 > Divide into subsequences of 5 and sort each: 1 2 5 6 2 5 3 7 11 3 6 4 8 16 4 M, the sequence of medians 8 4 8 10 10 5 9 220 14 24 19 Find the median m of M, and rearrange the columns: 2 2 1 5 6 3 3 5 7 11 4 4 6 8 16 m, the median of M 4 14 8 8 5 19 10 9 220 20 24 S1 = < 1, 5, 3, 5, 4, 2, 4, 5, 4, 3, 2> S2 = < 6,6> S3 = <10, 8, 7, 8, 8, 9, 24, 16, 20, 11, 14, 19 > SELECT (5, S) SELECT (5, S1) SELECT (12, S) SELECT (13, S) SELECT (17, S) SELECT (20, S) answer is 6 answer is 6 SELECT (4, S3) SELECT (7, S3) etc. |S1|= 11 | S2 | = 2 |s3| = 12 2 2 IA IɅ N≤3 ≤ + 4 IA 3 N≤M≤ < 4 IɅ VI ΙΛ 15516) IɅ 5 7 8 00 6 11 16 elements known to be less than or equal to m 4 14 8 8 20 VI 5 19 10 9 24 16 elements known to be greater than or equal to m 20 2 2 1 5 6 3 3 5 7 11 4 4 6 VI 8 VI IA ΙΛ 4 14 8 8 ΙΛ IɅ 5 19 10 9 6≤2≤2 24 Those elements in the green box are known to be less than or equal to m, the number of such elements is at least (3/5) x (1/2) x n = (3/10)n. Contrapositively, the number of elements greater than m is at most n - (3/10) n = (7/10) n. Therefore, the recursive call at Line 12, SELECT (k - |S1| - |S2, S3) takes time at most T(7n/10). Similarly, the elements in the blue box are guaranteed to be greater than or equal to m, and the number of such elements is at least (3/10)n. So the number of elements less than m is at most (7/10)n, and the recursive call at Line 10, SELECT (k, S1) also takes time at most T(7n/10). Note that depend on the choice for the length of the subsequences (in the algorithm discussed in class and the example above, the subsequences are of length 5) and n (number of elements in S), the two boxes may not be of equal size, in which case the recursive calls at Line 12 and Line 10 (observe that only one of the two may be executed) will have different complexities, and the larger one will dominate the expression for T(n).
Example of SELECT (k, S) algorithm S = < 1, 10, 8, 5, 6, 3, 5, 4, 2, 4, 7, 5, 8, 8, 9, 24, 6, 16, 20, 11, 4, 3, 14, 19, 2 > Divide into subsequences of 5 and sort each: 1 2 5 6 2 5 3 7 11 3 6 4 8 16 4 M, the sequence of medians 8 4 8 10 10 5 9 220 14 24 19 Find the median m of M, and rearrange the columns: 2 2 1 5 6 3 3 5 7 11 4 4 6 8 16 m, the median of M 4 14 8 8 5 19 10 9 220 20 24 S1 = < 1, 5, 3, 5, 4, 2, 4, 5, 4, 3, 2> S2 = < 6,6> S3 = <10, 8, 7, 8, 8, 9, 24, 16, 20, 11, 14, 19 > SELECT (5, S) SELECT (5, S1) SELECT (12, S) SELECT (13, S) SELECT (17, S) SELECT (20, S) answer is 6 answer is 6 SELECT (4, S3) SELECT (7, S3) etc. |S1|= 11 | S2 | = 2 |s3| = 12 2 2 IA IɅ N≤3 ≤ + 4 IA 3 N≤M≤ < 4 IɅ VI ΙΛ 15516) IɅ 5 7 8 00 6 11 16 elements known to be less than or equal to m 4 14 8 8 20 VI 5 19 10 9 24 16 elements known to be greater than or equal to m 20 2 2 1 5 6 3 3 5 7 11 4 4 6 VI 8 VI IA ΙΛ 4 14 8 8 ΙΛ IɅ 5 19 10 9 6≤2≤2 24 Those elements in the green box are known to be less than or equal to m, the number of such elements is at least (3/5) x (1/2) x n = (3/10)n. Contrapositively, the number of elements greater than m is at most n - (3/10) n = (7/10) n. Therefore, the recursive call at Line 12, SELECT (k - |S1| - |S2, S3) takes time at most T(7n/10). Similarly, the elements in the blue box are guaranteed to be greater than or equal to m, and the number of such elements is at least (3/10)n. So the number of elements less than m is at most (7/10)n, and the recursive call at Line 10, SELECT (k, S1) also takes time at most T(7n/10). Note that depend on the choice for the length of the subsequences (in the algorithm discussed in class and the example above, the subsequences are of length 5) and n (number of elements in S), the two boxes may not be of equal size, in which case the recursive calls at Line 12 and Line 10 (observe that only one of the two may be executed) will have different complexities, and the larger one will dominate the expression for T(n).
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
We are learning the Select
Transcribed Image Text:Example of SELECT (k, S) algorithm
S = < 1, 10, 8, 5, 6, 3, 5, 4, 2, 4, 7, 5, 8, 8, 9, 24, 6, 16, 20, 11, 4, 3, 14, 19, 2 >
Divide into subsequences of 5 and sort each:
1
2
5
6
2
5
3
7
11
3
6
4
8
16
4
M, the sequence of medians
8
4
8
10
10
5
9
220
14
24
19
Find the median m of M, and rearrange the columns:
2
2
1
5
6
3
3
5
7
11
4
4
6
8
16
m, the median of M
4
14
8
8
5
19
10
9
220
20
24
S1 = < 1, 5, 3, 5, 4, 2, 4, 5, 4, 3, 2>
S2 = < 6,6>
S3 = <10, 8, 7, 8, 8, 9, 24, 16, 20, 11, 14, 19 >
SELECT (5, S)
SELECT (5, S1)
SELECT (12, S)
SELECT (13, S)
SELECT (17, S)
SELECT (20, S)
answer is 6
answer is 6
SELECT (4, S3)
SELECT (7, S3)
etc.
|S1|= 11
| S2 |
= 2
|s3| = 12
Transcribed Image Text:2
2
IA
IɅ
N≤3 ≤ +
4
IA
3
N≤M≤ <
4
IɅ
VI
ΙΛ
15516)
IɅ
5
7
8
00
6
11
16
elements known to be less than
or equal to m
4
14
8
8
20
VI
5
19
10
9
24
16
elements known to be greater than
or equal to m
20
2
2
1
5
6
3
3
5
7
11
4
4
6
VI
8
VI
IA
ΙΛ
4
14
8
8
ΙΛ
IɅ
5
19
10
9
6≤2≤2
24
Those elements in the green box are known to be less than or equal to m, the number of such
elements is at least (3/5) x (1/2) x n = (3/10)n. Contrapositively, the number of elements greater
than m is at most n - (3/10) n = (7/10) n.
Therefore, the recursive call at Line 12, SELECT (k - |S1| - |S2, S3) takes time at most T(7n/10).
Similarly, the elements in the blue box are guaranteed to be greater than or equal to m, and the
number of such elements is at least (3/10)n. So the number of elements less than m is at most
(7/10)n, and the recursive call at Line 10, SELECT (k, S1) also takes time at most T(7n/10).
Note that depend on the choice for the length of the subsequences (in the algorithm discussed in
class and the example above, the subsequences are of length 5) and n (number of elements in S),
the two boxes may not be of equal size, in which case the recursive calls at Line 12 and Line 10
(observe that only one of the two may be executed) will have different complexities, and the
larger one will dominate the expression for T(n).
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 1 images
Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education