3. (8 marks) A computer's memory holds programs 1 through n, where each program occupies consecutive memory locations and no two programs overlap. Program i begins at address ai for each 1 i n, and a1 < a2 < < an. After a certain amount to time, some of the programs change their memory requirements, with the new length of the ith program being li. It might be necessary to shift some of the programs to satisfy the new memory requirements with no programs overlapping. Suppose that the programs must remain in the same order. Further, suppose that the starting addresses of programs 1 and n cannot be changed, and that programs 1 through n - 1 with their new memory requirements can fit into the space between a and an, that is, l + l2 + ... + ln-1 an - a1. Let R be a relation on {1, 2,..., n} where: j-1 (i,j) Ri j and laajai q=i That is, (i, j) E R means that if programs i and j remain at their original starting addresses, it is possible to shift programs i + 1 through j - 1 to satisfy the new memory requirements of programs i through j - 1. (a) Prove that R is a partial order relation. (b) Explain why the following statement is true by giving a few sentences of explanation. Do not give a formal proof. If C is a chain of the partially ordered set {1, 2,..., n} with respect to R such that 1, n C, then the new memory requirements can be satisfied with no programs overlapping by shifting n - |C| programs.