algorithms:

Suppose we want to replicate a file over a collection ofn servers, labeled S, S., ..., S.. To place a copy of the file at server >i results in a placement cost of Ci, for an integer Ci > 0. Now, if a user requests the file from server , and no copy of the file is present at Si, then the servers Si., Si., Si.... are searched in order until a copy of the file is finally found, say at server S wherej > i. This results in an access cost of j -i. (Note that the lower-indexed servers iS-2,.. are not consulted in this search.) The access cost is 0 if Si holds a copy of the file. We wl require that a copy of the file be placed at server S,, so that all such searches will terminate, at the latest, at S We'd like to place copies of the files at the servers so as to minimize the sum of placement and access costs. Formally, we say that a configuration is a choice, for each server with i = 1,2, ,n-1, of whether to place a copy of the file at Si or not. (Recall that a copy is always placed at S.) The total cost of a configuration is the sum of all placement costs for servers with a copy of the file, plus the sum of all access costs associated with all n servers 92 11 142, 0143. Give a polynomial -time algorithm to find a configuration of the minimum total cost. What is the running time of your algorithm