Consider the page caching problem where the memory cache can hold m pages, and we are given a sequence P of n requests taken from a pool of m +1 possible pages. Describe the optimal strategy for the...

Consider the page caching problem where the memory cache can hold
m

pages, and we are given a sequence
P
of
n
requests taken from a pool

of
m
+1 possible pages. Describe the optimal strategy for the offline

algorithm and show that it causes at most
m+n/m
page misses in total,

starting from an empty cache.

Describe an efficient external-memory algorithm that determines whether

an array of
n
integers contains a value occurring more than
n/2 times.