Notes on Page Replacement Algorithms (LRU-K, Competitive Analysis, Marking Alg, more)

 I took these notes in an airplane sit over a couple of transatlantic flights between Miami and Paris. I was reading about page replacement algorithms and went over some very classic papers in the topic.

 

Some notes from optimization lecture

Notes on Amortized Efficiency of List Update and and Paging Rules

For two lists of same items, an inversion is an unordered pair of items, i, j, s.t. i occurs before j in one list and after j in the other.




to be continued...

Lowest Common Ancestor Queries

Let T be a rooted tree. The lowest common ancestor of any pair of nodes u_i,u_j in T is their common ancestor that is farthest away from the root.


For example, in the graph shown in this figure, the lowest common ancestor of u6 and u10 is u3.


In the lowest common ancestor queries problem, given a tree you need to pre-process the information such as to provide O(1) per-query answers to the question "What is the lowest common ancestor" of nodes ui and uj for any i,j in [n].
Assume for simplicity that the tree is a binary tree.
Then construct the following structures:


-An array E[1..2n-1] that stores the nodes of T in the order in which they occur in the Euler leftmost-way tour of the "double-tree" obtained from doubling each edge of T, starting at the root.


-An array L[1..2n-1] such that L[i] stores the level of node E[i].


-An array R[1..n] such that R[i] is the smallest integer l for which E[l] = ui.


Then for a given pair i, j assuming R[i] < R[j]. Let k be the integer such that R[i] ≤ k ≤ R[j] and L[k] is minimum. Then the lowest common ancestor of nodes ui and uj is equal to E[k].


Finding L[k] that is minimum for the subarray L[i..j] can be done in O(1) time if you apply the O(n log n) preprocessing used in this post to find the range minimum queries problem.


MArio

Range minimum problem (general case)

The Range Minimum Problem is defined as: Given an array A[1..n] of real numbers, we want to preprocess A such that for any two given integers i and j with 1 ≤ i < j ≤ n we can efficiently compute an integer k, i ≤ k ≤ j for which A[k] is minimum.


Here I am going to go over three solutions which use preprocessing to provide a O(1) per query operational time.


Solution 1:
This is the most brute of the three solution. It takes O(n^2) time and space.
It consists in storing the answer for all possible n-choose-2 pairs of (i,j) possible.
For this we make a two dimensional array X defining X[i][j] as:


X[i][j] = k ∈ [i,j] s.t. A[k] is minimum.


We construct X as shown in the recurrence relation shown in this figure.


Solution 2:
This solution is slightly smarter and takes O(n log n) time and space.
Here an array Y is defined as follows:


Y[i][l] = k ∈ [i, i + 2^l - 1] s.t. A[k] is minimum, for i∈[1,n-1] and l∈[1, log(n-i+1)]


For ease of exposition, by log(x) we mean floor of log(x) in this post.


Observe that for integers i and j in the interval [1,n] such that i < j, for h = log(i-j) we have that {i,i+1,...,i + 2^h - 1} ∪ {j - 2^h + 1,...,j} = [i,j].


Then min(A[Y[i][h]], A[Y[j-2^h+1][h]]) is the minimal element in A[i..j].


We construct Y as shown the recurrence relation in this figure.


All for now folks.


MArio

Minimizing Piece-wise Linear Area for Solution to Convex Hull of Segments

In a previous post we saw a solution to the parallel line segment smallest convex hull problem. See the post and familiarize yourself with the solution. You will see that the last paragraph explains how to find the optimal point p that minimizes the area between the point, two polylines, and the tangent lines between p and the polylines.


There we want to determine the point p in segment sl such that the area A(p) is minimized. See this figure.


See that the straight lines defined by the extension of the sides of the polyline (top or bottom chain) that are reachable from p by drawing a line that does not cut the polyline intersect the segment sl.


Extend the sides of one of the polylines (top or bottom chain). If the side is reachable from any point in  sl by drawing the point to the side without cutting the chain, then the extension into infinite of the line defined by that side intersects the segment  sl . To find the optimal p to minimize A(p), we just need to consider all the above mentioned intersection points.


Let x1, x2, ..., xa be the points of intersection from the extension of the lines sides of the top chain and segment sl, ordered from top to bottom.


Let y1, y2, ..., yb be the points of intersection from the extension of the lines sides of the top chain and segment sl, ordered from top to bottom.


We just need to consider all the intersections between two intervals [xi,x i+1] and [yj,y j+1] for all i and j possible, which quantity that is is linear in the number of segments from the problem solved in the last post. See this figure for a visual.


Then see this figure and realize that for each of those intervals, realize that the optimal point p for that interval will lie in one of the extreme points of the interval, or else then any point in the interval will give you the same area A(p). The reason is that the chains form a monotone convex polyline, and whichever of the two points al(p) and bl(p), as shown in the figure, is closest from sl will determine the point p in sl that minimizes A(p).

Parallel Line Segments Smallest Convex Hull

Here I am gonna write on what I learned about finding the smallest convex hull (smallest CH) of a set of parallel line segments from reading Loffler and Kreveld's work.


Here is the problem:
Given a set of parallel (vertical) line segments, choose a point on each line segment such that the area of the convex hull of the resulting point set is the smallest possible among all possible selections of this point set.


See this figure for a visual.


To solve this problem we are first to see the following definition:


Greatest Common Region (GCR): The greatest common region of a set of line segments S is the largest region that is part of the convex hull of every possible choice of points on the segments.


Now let's see the definition, in this context, of top and bottom chain of a set S of parallel vertical line segments.


top chain (resp. bottom chain) of S: Polyline that contains no lower (resp. higher) endpoints of any segment over (resp. under) it.


After seeing these definitions, go ahead and realize that the region enclosed between the top and the bottom chain of S forms the greatest common region (GCR) of the set S of parallel vertical line segments.


Also realize that the area (A(GCR)) of the GCR of S is equals to zero if and only if the area (A(C*)) of the optimal (aka smallest) convex hull of S is zero.
It is easy to check if A(GCR) == 0 in linear time. // O(n)
If it is found that A(GCR) == 0  then obviously the optimal solution for smallest convex hull of S has area zero.


Hence just assume that A(GCR) > 0. :)


Let sl and sr be the leftmost and rightmost segments of the set S.


Let p be a point in  sl and a point q on  sr, then let al(p) th rightmost point in the top chain such that the line from p to al(p) does not intersect the top chain. Define bl(p) respectively with the bottom chain. Also define ar(q) and br(q) respectively for q.
See figure 2 inside this picture for a visual.


Now you can go ahead and realize that for a certain p and q in the right leftmost and right most respectively segments, then the area enclosed by the chain
p -> al(p) -> ar(p) -> q -> br(q) -> bl(q) -> p
is the optimal solution. The challenge is then to find the right p and q.


To find the right p just go ahead and do:
For each pair of edges e1 and e2 of the top and bottom chain respectively whose projection onto infinity intersect sl at points y1 and y2 respectively, go ahead and pick the optimal point x1 for the interval in sl between y1 and y2. Do the same for q and pick a point x2 respectively. Find the area enclosed in in O(log n) time. Pick the smallest of all the solutions and return.


The problem can therefore be solved in O(n log n) time.