Section 2
Exercise 23.2.1
P0 = (0.25, 0.25, 0.25, 0.25,)
P1 = (0.125, 0.25, 0.25, 0.375)
Exercise 23.2.2
a)
P0 = (0.25, 0.25, 0.25, 0.25,)
P1 = (0.1375, 0.25, 0.25, 0.3625)
b)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.15, 0.25, 0.25, 0.35,
P2 = (0.15, 0.25, 0.29, 0.31)
P3 = (0.166, 0.234, 0.274, 0.3260)
Exercise 23.2.3
i a)
P0 = (0.25, 0.25, 0.25, 0.25)
i b)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.05, 0.05, 0.15, 0.15)
ii a)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.1375, 0.25, 0.025, 0.3625)
P2 = (0.0363, 0.3513, 0.0250, 0.2613)
P3 = (0.0363, 0.2601, 0.0250, 0.3524)
ii b)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.15, 0.25, 0.05, 0.35)
P2 = (0.07, 0.33, 0.05, 0.27)
Exercise 23.2.4
Map function:
The map function takes in, as parameters, the page rank estimate of a certain page along with its
corresponding column in the transition matrix; the column maybe partitioned to accommodate
Section 3
Exercise 23.3.1
Compute page rank for fig 23.5
a)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.3, 0.2, 0.2, 0.3)
b)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.2, 0.3, 0.2, 0.3)
P2 = (0.18, 0.30, 0.24, 0.28)
Exercise 23.3.2
a)
P0 = (0.25, 0.25, 0.25, 0.25)
b)
P0 = (0.25, 0.25, 0.25, 0.25)
Exercise 23.3.3
a)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.3, 0.2, 0, 0.3)
b)
P0 = (0.25, 0.25, 0.25, 0.25)
P1 = (0.2, 0.3, 0, 0.3)
Exercise 23.3.4
Proof by construction
(A) – when a is the only node in the teleport set
Exercise 23.3.5
Section 4
Exercise 23.4.1
a)
SELECT *
b)
SELECT s.sensID
c)
SELECT a.sensID
FROM
(SELECT sensID, count(sensID) as cnt FROM sensors [Range 1 minute] GROUP BY
Exercise 23.4.2
Readings
(80, 0)
(70, 50)
(60, 70)
(65, 100)
Istream(R)
0
50
70
100
Dstream(R)
60
110
100
160
Exercise 23.4.3
a)
SELECT item FROM
b)
SELECT P1.item1, P1.item2
FROM
(SELECT a.item AS item1, b.item AS item2, COUNT(*) AS cnt FROM Basket[Range
c)
SELECT item1, item2
FROM
(SELECT a.item AS item1, b.item AS item2, COUNT(*) AS cnt FROM Basket[Range 1
Section 5
Exercise 23.5.1
16, 8, 8, 4, 4, 2, 1, 1
1: 16, 8, 8, 4, 4, 2, 1, 1, 1 => 16, 8, 8, 4, 4, 2, 2, 1
2: 16, 8, 8, 4, 4, 2, 2, 1, 1
Exercise 23.5.2
k
10
15
20
Exercise 23.5.3
Create 10 streams, one for each bits of the 10-bit integer. When a new integer arrives, send all
the bits that are 1’s to their corresponding streams. Each stream employs the bit-counting
where Si(k) is the estimated number of bits from ith stream, which corresponds to the ith bit of
the integer.
1000100101 (new integer)
Streams9: 1 1
Streams8: 2, 1
buckets
2, 1, 1
4, 2, 1, 1
4, 4, 2, 1, 1
4
6
10
Exercise 23.5.4
a)
Whenever there are p+2 buckets of any size, combine the two least recent buckets of that size to
b)
The error of the algorithm presented in section 23.5.2 is at most B/2 where B is the size of the
last bucket. If there are n buckets, then the true count is at least
Since bucket size increases by powers of 2, the sum last p bucket of the same size as Bn cannot
be larger than the sum of the remaining buckets plus p (at least one 1 from each bucket
contributes to the total). Thus the maximum error is reduced to a factor of 1/p since the
approximation error is only from the last bucket. The new approximation error is
Exercise 23.5.5
a)
v
h1(v)
r
R
24
24(11000)
3
3
45
45(101101)
0
3
102
102(1100110)
1
3
26 = 64
b)
v
h2(v)
r
R
24
183(10110111)
0
0
45
204(11001100)
2
2
102
261(100000101)
0
2
24
183(10110111)
0
2
78
237(11101101)
0
2
222
381(101111101)
0
2
45
204(11001100)
2
2
24
183(10110111)
0
2
670
317(100111101)
0
2
78
134(10000110)
1
2
999
237(11101101)
0
2
576
223(11011111)
0
2
222
381(101111101)
0
2
24
183(10110111)
0
2
24
24(11000)
3
3
78
78(1001110)
1
3
222
222(11011110)
1
3
45
45(101101)
0
3
24
24(11000)
3
3
670
158(10011110)
1
3
78
78(1001110)
1
3
999
487(111100111)
0
3
576
64(1000000)
6
6
222
222(11011110)
1
6
24
24(11000)
3
6
c)
v
h3(v)
r
R
24
365(101101101)
0
0
45
386(110000010):1
1
1
Exercise 23.5.6
a)
No, this rule does not always compress the data in the window; it will not achieve any
b)
Since the temperature readings are real numbers chosen uniformly and at random, the chance of
102
443(110111011):0
0
1
24
365(101101101):0
0
1
78
419(110100011):0
0
1
222
51(110011):0
0
1
45
386(110000010):1
1
1
24
365(101101101):0
0
1
670
499(111110011):0
0
1
78
419(110100011):0
0
1
999
316(100111100):2
2
2
576
405(110010101):0
0
2
222
51(110011):0
0
2
24
365(101101101):0
0
2