Consider the paging problem. Consider the following randomized online algorith Algorithm Description: Each page P has an associated bit denoting whether the page is FRESH or STALE. If requested page P in fast memory, then P's associated bit is set to FRESH. If the requested page P is not in fast memory, then a STALE page is selected uniformly at random from the STALE pages in fast memory and ejected, and P's associated bit is set to FRESH. If the request page P is not in fast memory, and all pages in fast memory are FRESH, then make all pages in fast memory STALE, select a STALE page uniformly at random from the STALE pages in fast memory to evict, and P associated bit is set to FRESH Show that this algorithm is O(log k) competitive/approximate using the following strat- egy (recall k is the size of the fast memory). Partition the input sequence into consed- utive subsequences/phases where there are exactly k distinct pages requested in each subsequence/phase. The phase breaks are when all pages in fast memory are made STALE. Let mi be the number of pages requested in phasei that were not requested in phase i 1 (a) Show that the optimal number of page faults is ??.m) (b) Show that the expected number of page faults for the randomized algorithm on the page requests in phase i is O(mi log k) Consider the paging problem. Consider the following randomized online algorith Algorithm Description: Each page P has an associated bit denoting whether the page is FRESH or STALE. If requested page P in fast memory, then P's associated bit is set to FRESH. If the requested page P is not in fast memory, then a STALE page is selected uniformly at random from the STALE pages in fast memory and ejected, and P's associated bit is set to FRESH. If the request page P is not in fast memory, and all pages in fast memory are FRESH, then make all pages in fast memory STALE, select a STALE page uniformly at random from the STALE pages in fast memory to evict, and P associated bit is set to FRESH Show that this algorithm is O(log k) competitive/approximate using the following strat- egy (recall k is the size of the fast memory). Partition the input sequence into consed- utive subsequences/phases where there are exactly k distinct pages requested in each subsequence/phase. The phase breaks are when all pages in fast memory are made STALE. Let mi be the number of pages requested in phasei that were not requested in phase i 1 (a) Show that the optimal number of page faults is ??.m) (b) Show that the expected number of page faults for the randomized algorithm on the page requests in phase i is O(mi log k)
