This project consists of three problems. For algorithm design questions, you can write pseudo-code, or explain...

Transcribed Image Text:

This project consists of three problems. For algorithm design questions, you can write pseudo-code, or explain your answer in English. You need to submit your answer document through Canvas. Suppose we have a sorted array A in increasing order. Assume the array has starting index as 1 (rather than 0). It contains n positive integers. Given a positive integer number k, an interval [i, j] (1 ≤i≤j≤n) is defined as a good interval if it satisfies A[j] - A[i] ≤k.< A max good interval is a good interval with the cardinality maximized. Here is an example. ( Suppose that A is [1, 2, 4, 7, 8, 9, 10, 19], and k is 6, Intervals [1,4], [3,7], and [2, 5] are good intervals. Intervals [1, 5] and [6, 8] are not good intervals. Interval [3, 7] is a max good interval. < [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] I Good interval Good interval(max good interval) Good interval Not Good interval Not Good interval Problem 1: 1) Suppose that A is [2, 3, 7, 9, 11, 13, 15, 16, 17, 22, 24], and k is 9. Please write out a max good interval in A. (10%)< For Example: If A is [20, 21, 25, 26, 30, 31, 32, 34,37,39] and k is 7, Then, your answer can be [3, 7] or [5, 9], as indicated below, both contains five elements, and both are correct. ( [20, 21, 25, 26, 30, 31, 32, 34,37,39] or [20, 21, 25, 26, 30, 31, 32, 34,37,39] 2) Now, given any sorted array A in increasing order and a positive integer k, pleas design an algorithm to find a max good interval. What is the running time in terms of big-Oh. (20%)< This project consists of three problems. For algorithm design questions, you can write pseudo-code, or explain your answer in English. You need to submit your answer document through Canvas. Suppose we have a sorted array A in increasing order. Assume the array has starting index as 1 (rather than 0). It contains n positive integers. Given a positive integer number k, an interval [i, j] (1 ≤i≤j≤n) is defined as a good interval if it satisfies A[j] - A[i] ≤k.< A max good interval is a good interval with the cardinality maximized. Here is an example. ( Suppose that A is [1, 2, 4, 7, 8, 9, 10, 19], and k is 6, Intervals [1,4], [3,7], and [2, 5] are good intervals. Intervals [1, 5] and [6, 8] are not good intervals. Interval [3, 7] is a max good interval. < [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] [1, 2, 4, 7, 8, 9, 10, 19] I Good interval Good interval(max good interval) Good interval Not Good interval Not Good interval Problem 1: 1) Suppose that A is [2, 3, 7, 9, 11, 13, 15, 16, 17, 22, 24], and k is 9. Please write out a max good interval in A. (10%)< For Example: If A is [20, 21, 25, 26, 30, 31, 32, 34,37,39] and k is 7, Then, your answer can be [3, 7] or [5, 9], as indicated below, both contains five elements, and both are correct. ( [20, 21, 25, 26, 30, 31, 32, 34,37,39] or [20, 21, 25, 26, 30, 31, 32, 34,37,39] 2) Now, given any sorted array A in increasing order and a positive integer k, pleas design an algorithm to find a max good interval. What is the running time in terms of big-Oh. (20%)<

Answer rating: 100% (QA)

Problem 1 Given the sorted array A 2 3 7 9 11 13 15 16 17 22 24 and the positive integer k 9 lets fi... View the full answer