1. A d-dimensional box with dimensions (x1, x2,..., xd) nests within another box with di- mensions (y1, 2,...,ya) if there exists a permutation 7 on {1,2,...,d} such that xÃ(1) < Y1, (2) Y2,...,x(d) < Yd. (a) Argue that the nesting relation is transitive. (b) Describe an efficient method to determine whether one d-dimensional box nests inside another. (c) You are given a set of n d-dimensional boxes {B1, B2, ..., Bn}. Give an efficient algo- rithm to find the longest sequence (B₁₁, Bi₂,..., Bik) of boxes such that Bi, nests within Bij+1 for j = 1, 2,..., k 1. Express the running time of your algorithm in terms of n and d. 3. Consider a single machine that can process jobs. We receive a set of job requests {1,2, ..., n}, and the ith request takes a positive time duration a¿ to process. We are able to use the machine for the period between time 0 and specified time T. Our goal is to process the jobs so as to keep the machine busy for the entire time it is available. Give an efficient algorithm to determine whether the machine can be kept busy for the entire time T, and which jobs should be processed. You may assume the processing times a; and total available time T are positive integers. Also state and justify the running time of your algorithm.

1. A d-dimensional box with dimensions (x1, x2,..., xd) nests within another box with di- mensions (y1, 2,...,ya) if there exists a permutation 7 on {1,2,...,d} such that xÃ(1) < Y1, (2) Y2,...,x(d) < Yd. (a) Argue that the nesting relation is transitive. (b) Describe an efficient method to determine whether one d-dimensional box nests inside another. (c) You are given a set of n d-dimensional boxes {B1, B2, ..., Bn}. Give an efficient algo- rithm to find the longest sequence (B₁₁, Bi₂,..., Bik) of boxes such that Bi, nests within Bij+1 for j = 1, 2,..., k 1. Express the running time of your algorithm in terms of n and d. 3. Consider a single machine that can process jobs. We receive a set of job requests {1,2, ..., n}, and the ith request takes a positive time duration a¿ to process. We are able to use the machine for the period between time 0 and specified time T. Our goal is to process the jobs so as to keep the machine busy for the entire time it is available. Give an efficient algorithm to determine whether the machine can be kept busy for the entire time T, and which jobs should be processed. You may assume the processing times a; and total available time T are positive integers. Also state and justify the running time of your algorithm.