Suppose that [e, e..... e] is a list of k integers. The following table defines some...

  

Transcribed Image Text:

Suppose that [e, e..... e] is a list of k integers. The following table defines some operations on such lists. Each operation works in 0(1) time. 07 08 Operation [] [e] 01 MERGE(left, right) 02 both = [] 03 04 05 06 HEAD() TAIL() LENGTH() ler Suppose that I and rare lists of integers. The elements of each list are sorted into nondecreasing order, but you do not know what those elements are. The procedure MERGE(!) returns a new list that has all the elements of I and also sorted into nondecreasing order. else both both left = TAIL(left) while LENGTH(left) > 0 and LENGTH(right) > 0 if HEAD(left) 2. Questions 2a through 2d are about the procedure FACTORIAL, which returns the factorial of the integer n. Assume that n 0. Use a loop invariant to prove that FACTORIAL is correct. FACTORIAL(n) f=1 k=1 while k n f = kx f k = k+1 return f 2a. (5 points.) What is a loop invariant for FACTORIAL? 2b. (5 points.) Use the invariant from 2a to prove that FACTORIAL is correct at initialization. 2c. (5 points.) Use the invariant from 2a to prove that FACTORIAL is correct during maintenance. 2d. (5 points.) Use the invariant from 2a to to prove that FACTORIAL is correct at termination. 3. Questions 3a and 3b are about the backtracking procedure MAKE-SETS and its helper MAKING-SETS. The symbol 'o' is the empty set, and the symbol 'U' is the set union operator. The procedure PRINT(s) prints the set s. The parameters n, k, and e are nonnegative integers. The parameter s is a set of nonnegative integers. MAKE-SETS(n, k) MAKING-SETS(n, k, 1, ) MAKING-SETS(n, k, e, s) if k == 0 PRINT(S) else for e = e to n MAKING-SETS(n, k-1, e + 1, su{e }) 3a. (5 points.) What will MAKE-SETS(4, 2) print? Hint: enumerate the calls to MAKING-SETS breadth-first. 3b. (5 points.) Suppose that / and mare nonnegative integers. What does MAKE-SETS(/, m) compute? Your answer must be one short sentence, stated in terms of /and m. Suppose that [e, e..... e] is a list of k integers. The following table defines some operations on such lists. Each operation works in 0(1) time. 07 08 Operation [] [e] 01 MERGE(left, right) 02 both = [] 03 04 05 06 HEAD() TAIL() LENGTH() ler Suppose that I and rare lists of integers. The elements of each list are sorted into nondecreasing order, but you do not know what those elements are. The procedure MERGE(!) returns a new list that has all the elements of I and also sorted into nondecreasing order. else both both left = TAIL(left) while LENGTH(left) > 0 and LENGTH(right) > 0 if HEAD(left) 2. Questions 2a through 2d are about the procedure FACTORIAL, which returns the factorial of the integer n. Assume that n 0. Use a loop invariant to prove that FACTORIAL is correct. FACTORIAL(n) f=1 k=1 while k n f = kx f k = k+1 return f 2a. (5 points.) What is a loop invariant for FACTORIAL? 2b. (5 points.) Use the invariant from 2a to prove that FACTORIAL is correct at initialization. 2c. (5 points.) Use the invariant from 2a to prove that FACTORIAL is correct during maintenance. 2d. (5 points.) Use the invariant from 2a to to prove that FACTORIAL is correct at termination. 3. Questions 3a and 3b are about the backtracking procedure MAKE-SETS and its helper MAKING-SETS. The symbol 'o' is the empty set, and the symbol 'U' is the set union operator. The procedure PRINT(s) prints the set s. The parameters n, k, and e are nonnegative integers. The parameter s is a set of nonnegative integers. MAKE-SETS(n, k) MAKING-SETS(n, k, 1, ) MAKING-SETS(n, k, e, s) if k == 0 PRINT(S) else for e = e to n MAKING-SETS(n, k-1, e + 1, su{e }) 3a. (5 points.) What will MAKE-SETS(4, 2) print? Hint: enumerate the calls to MAKING-SETS breadth-first. 3b. (5 points.) Suppose that / and mare nonnegative integers. What does MAKE-SETS(/, m) compute? Your answer must be one short sentence, stated in terms of /and m.

Answer rating: 100% (QA)

1 The runtime of MERGEleft right is given by M L R where L is the length of the left list and R is t... View the full answer