Question

1. When do we say an algorithm is optimal for a problem? Explain with a specific problem and two concrete examples of algorithms, one of which is optimal and one which is not optimal for your chosen problem.

Answer 1

An optimal algorithm for a problem is the algorithm for which the objective function is maximized(or minimized) for a large random input. The objective function can be time complexity for searching and sorting or hit rate for page replacement algorithms.

We take the example of Page Replacement Algorithms here. In operating system, whenever a page is referred and is not present in the cache memory, page fault(or miss) occurs. There are a number of algorithms for page replacement. Any new referred page that is not present in the memory is considered a miss. Otherwise, it is a hit. Our aim is to maximize the hit to miss ratio.

First, we see the First-in-first-out(FIFO) algorithm in which when a page fault occurs, the page in the memory which arrived the first is replaced with the new page.

Maximum no. of pages that can be stored in the cache = 3.

Input string : 1,2,3,4,1,4,5,2,3

When 4 arrives, the page that is oldest in the memory is 1. So, 1 is replaced with 4. Similarly, when 1 arrives for the 2nd time, the oldest page is 2. So, 2 is replaced by 1 and so on.

No. of miss = 8          No. of hit = 1        hit-to-miss ratio = 1/8

Now, we consider the optimal page replacement algorithm. In it, we replace the page which will not be used for the longest in the future. If there are two such pages in the memory that are never used in the future, we replace the page that arrived first in the memory.

Input string : 1,2,3,4,1,4,5,2,3

When 4 arrives, the page that will not be used in the future for the longest time is 3. So, 3 is replaced with 4. Similarly, when 5 arrives, the pages that will not be referred in the future is 1 and 4. Now, 1 is older than 4 i.e, 1 has been in the memory for a longer time than 4. So, 1 is replaced by 5 and so on.

No. of miss = 6        No. of hits = 3        hit-to-miss ratio = 3/6 = 1/2

So, you can see that the ratio is much higher in case of optimal page replacement algorithm as compared to FIFO algorithm. So, the 2nd algorithm is considered the optimized algorithm for the page replacement problem.