Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
Algorithms: Sequential, Parallel and Distributed 1-1
Chapter 17
Internet Algorithms
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed 1-2
Lecture Notes
Overview
In Chapter 17 we introduce the student to some algorithms that are the basis of information
storage and retrieval on the Internet. We first show how the World Wide Web is naturally
modeled as a digraph with nodes being web pages and directed edges corresponding to
hyperlink references. We then show how search engines use ranking functions to determine the
order in which web pages are presented in answer to a query by the user. Two ranking
functions, PageRank and HITS, are discussed. The idea of hashing is then introduced, and the
main methods of collision resolution are discussed. Web caching is then described, and the
notion of consistent hashing and its implementation are discussed as an efficient way to
maintain web caches. We finish the chapter by a discussion of the mathematical ideas
underlying the RSA Public-Key Cryptography system, and describe this system in some detail.
Chapter Objectives
After completing the chapter the student will know:
• How the World Wide Web can be modeled by a digraph
• How search engines use forward and reverse indexing to build a database of web pages
when responding to a query
• How search engines give web pages a ranking when presenting answers to a query
• The ideas behind the two main ranking functions for web pages, PageRank and HITS
Instructor Notes
The algorithms discussed in this chapter should impress the student with the importance of
Algorithms: Sequential, Parallel and Distributed 1-3
may not be as familiar with random walks, and we give a brief discussion of Markov chains
and random in digraphs, as well as eigenvalues and eigenvectors in Appendix D.
Solutions to Selected Exercises
Section 17.2 Ranking of Web pages
pNqWVq in
==
17.2 a. Take the digraph to be a cycle Cn of length n ≥ 2 or greater.
b. Ri = (1, 1, …., 1), so that it converges to (1, 1, …., 1). Equivalently if we normalize R0
17.3 Ri[p] equals the summation over all walks K from q to p of the product of the
probabilities on the edges of K. If there is no path from q to p, then this sum is empty
17.5 Since B is the matrix associated with a random walk on the web digraph, i.e., B[p,q]
equals the probability Pp,q that a random walker at node p will move to node q in the next step
(transition), it follows that Bi[p,q] is that the probability Pp,q(i) that a random walker starting at
node p will be at node q after i steps. We can prove this by induction on i as follows.
Algorithms: Sequential, Parallel and Distributed 1-4
17.6 Letting J be the matrix of all 1’s we have Ri = d/nJ + (1 – d)BTRi - 1 ,
Section 17.3 Hashing
17.8 Inserting 2, 11, 55, 23, 53, 9, 61, 46, 1, 3, 25, 19, 17, 34, 10, 38
slot
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
key
23
46
2
1
3
25
53
55
9
11
34
10
61
38
17
19
17.9 Inserting 2, 11, 55, 23, 53, 9, 61, 46, 1, 3, 25, 19, 17, 34, 10, 38
slot
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
key
23
1
2
3
46
53
55
10
11
25
61
19
17
38
9
34
17.10 The leading digit is a number between 1 and 9. The resulting chained hash function is
shown below (where a new element is added at the beginning of the linked list):
H[1] → 123
H[2] → 200 → 211 → 23
xXt ][9/1
17.11 We assume that X is equally likely to begin with any of the nine digits. Using the
chained hash function given in the solution to the previous question the number of
17.12 First assume that h2(k) and m are relative prime. Then, h2(k) is invertible modulo m, i.e.,
there exists an integer s such that sh2(k) ≡ 1 (mod m). To see this apply the extended Euclid’s
algorithm (see Exercise 1.10 of Chapter 1) to obtain integers s and t such that
17.13 This question should have been starred. Also, in the statement of the Theorem 17.3.1
the two occurrences of ≤ should have been ≈. Consider an unsuccessful search. The search will
terminate when an empty slot is reached. Let pi denote the probability that the search
terminates after i probes. Then,
=
=
n
iin ipU
1
Algorithms: Sequential, Parallel and Distributed 1-6
= ==
+−−−+−+=−+−+==
n
i
n
i
i
n
i
in nmCinimCimmpimmipU
1 11
),(/)1,()1(1)1(1
Section 17.4 Caching, Content Delivery, and Consistent Hashing
17.14 Let B be the first bucket in V2 that is encountered when traversing the circle in a
17.15 a. Consider any two views V1 and V2 and any item I. Consider the list L of buckets given
17.16 Since 23 is a prime number the multiplication table for Z23* is the same as the
multiplication table for Z23*. The question should have been to compute the
multiplication table for Z21* given below:
*
1
2
4
5
8
10
11
13
16
17
19
20
1
1
2
4
5
8
10
11
13
16
17
19
20
Algorithms: Sequential, Parallel and Distributed 1-7
2
2
4
8
10
16
20
1
5
11
13
17
19
4
4
8
16
20
11
19
2
10
1
5
13
17
5
5
10
20
4
19
8
13
2
17
1
11
16
8
8
16
11
19
10
10
20
19
8
11
11
1
2
13
13
13
5
10
2
16
16
11
1
17
17
17
13
5
1
19
19
17
13
11
20
20
19
17
16
17.17 a. 1097 = 365×3 + 2, 3 = 2 × 1 + 1
b. 1097 = 46×23 + 39, 46 = 1×39 + 7, 39 = 5×7 + 4, 7 = 1×4 + 3, 4 = 1×3 + 1
17.18 We will assume the number is represented in binary (a similar argument holds if the
number is represented in another base, such as decimal). Denote the number of digits (bits) of
a, b and q by m, n and p, respectively. Let a[i:j] denote the number determined by the digits of
1. The final value of r is the remainder. Since each stage involves at most O(n) bit
computations and since there are at most O(p) stages, the complexity of the algorithm is O(pn).
17.19 RSA decryption involves computing md mod n. The number of digits of both m and d is
no larger than the number of digits of n, i.e., is O(β) Using the binary method for powers md
can be computed in O(log d) = O(β) steps, where each step involves computing a product and
17.20 Consider any index i, 1 ≤ i ≤ n. For any index j different from i, since ajbjM/mj is
divisible by mi,
ajbjM/mj (mod mi ) ≡ 0.
Also, since by hypothesis biM/mi (mod mi) ≡ 1, we have that aibiM/mi (mod mi) ≡ ai. It follows
that
ii mmM mod)/( 1−
Suppose x and y both satisfy all the congruence relations. Then y – x ≡ 0 (mod ≡ mi), i = 1,
…, k, so that y – x = jM for some j, i.e., y = x + jM, i.e., different solution differ by multiples
of M. Since x + jM is clearly a solution if x is, it follows that all solutions are of the form x0+
jM, where x0 is any solution. In particular, choosing
)mod)/((/1
1
0iii
k
immMmMx −
=
=
Algorithms: Sequential, Parallel and Distributed 1-9
17.21 a. M = q(q-1 mod p) Mp + p(p-1 mod q)Mq ≡ q(q-1 mod p) Mq ≡ Mq (mod p).
17.22 a. Use the formula M = qr((qr)-1 mod p) Mp + pr((pr)-1 mod q)Mq + pq((pq)-1 mod r)Mq
We now show that this formula is correct. By Chinese Remainder Theorem the x that satisfy
the congruences are catergorized by x = qr b1Mp + prb2Mq + pq b3Mq where b1qr ≡ 1 (mod p) ,
b2pr ≡ 1 (mod q) and b3pq ≡ 1 (mod r) . The smallest choice for x is when b1 = (qr)-1 mod p,
1iii
ipppppM −
=
