q4

Q1. (10 pts) Designing an Algorithm - Smallest and Largest Numbers Write an algorithm that finds both the smallest and largest numbers in a list of n numbers. Try to find a method that does at most 1.5n comparisons of Array elements in total. Q2. (20 pts) Designing and implementing an Algorithm - Subsets of a set of n elements a. [8 pts) Write an algorithm that prints all the subsets of three elements of a set of n elements (integers). The input to the algorithm is an array of integers (the elements of the set). The output is a list of all the subsets of three element. (Note that the efficiency of your algorithm will be considered in grading) b. [5 pts] Identify a basic operation for your algorithm and study the performance of your algorithm by giving its time complexity function. If it has an every-case time complexity, determine it. Otherwise, determine the worst-case time complexity. c. 12 pts) Identify the complexity category to which the algorithm belongs. d. [5 pts) Implement your algorithm using Java. Write a main method that asks the user to enter the size and elements of a set of integers, stores them in an array and then prints all the subsets of three-elements. 03. [20 pts) Designing and implementing an Algorithm - Sum of three elements a. [8 pts) Write an algorithm that determines whether there are three elements in a given array of integers that sums to exactly a given integer value k. As input, you are given an array of n integers and an integer value k. (Note that the efficiency of your algorithm will be considered in grading) For example, given the array [1, 3, 7, 4) and k - 14, the answer is ""yes", given k=6 the answer is 'no." b. 15 pts) Identify a basic operation for your algorithm and study the performance of your algorithm by giving its time complexity function. If it has an every-case time complexity determine it . Otherwise, determine the worst-case time complexity. C. [2 pts) Identify the complexity category to which the algorithm belongs. d. [5 pts) Implement your algorithm using Java. Write a main method that asks the user to enter the integer value k and the sizen of an array of integers. The main method must generate the array elements randomly. As output, the program must first print all elements of the array. Then, it should print "No" if the array does not contain three elements that sums to k or print "Yes" if there are three elements that sums to k. If the output is "Yes", the program must print these three elements and their location index in the array Q4. [20 pts] Designing and Implementing an Algorithm - Longest increasing sequence a. [8 pts) Write an algorithm to find a subsequence of a given sequence of integers in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. The algorithm should print one of the existing longest subsequences. (Note that the efficiency of your algorithm will be considered in grading.) For example, in the following sequence of integer values: 0,8, 4, 12, 2, 10, 6, 14, 1,9.5, 13.3.11, 7. 15 A longest increasing subsequence is 0.2,6,9, 11, 15. This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not the only solution: for instance 0, 4, 6, 9, 11, 15; 0, 2, 6, 9, 13, 15; and 0, 4, 6, 9, 13, 15 are other increasing subsequences of equal length in the same input sequence. b. [5 pts] Identify a basic operation for your algorithm and study the performance of your algorithm by giving its time complexity function. If it has an every-case time complexity, determine it. Otherwise, determine the worst-case time complexity. c. [2 pts] Identify the complexity category to which the algorithm belongs. d. [5 pts) Implement your algorithm using Java. Write a main method that asks the user to enter the integer value k and the size n of an array of integers. The main method must generate the array elements randomly. As output, the program must first print all elements of the original input sequence, then, it should print the length of the longest subsequence, and finally the elements of one of the longest subsequence Q1. (10 pts) Designing an Algorithm-Smallest and Largest Numbers Write an algorithm that finds both the smallest and largest numbers in a list of n numbers. Try to find a method that does at most 1.5n comparisons of array elements in total. Q2. (20 pts) Designing and implementing an Algorithm - Subsets of a set of n elements a. [8 pts) Write an algorithm that prints all the subsets of three elements of a set of n clements (integers). The input to the algorithm is an array of integers (the elements of the set). The output is a list of all the subsets of three element. (Note that the efficiency of your algorithm will be considered in grading.) b. [5 pts] Identify a basic operation for your algorithm and study the performance of your algorithm by giving its time complexity function. If it has an every-case time complexity, determine it. Otherwise, determine the worst-case time complexity. c. 12 pts) Identify the complexity category to Chich the algorithm belongs. d. [5 pts) Implement your algorithm using Java. Write a main method that asks the user to enter the size and elements of a set of integers, stores them in an array and then prints all the subsets of three-elements. 03. (20 pts) Designing and implementing an Algorithm - Sum of three elements a. [8 pts) Write an algorithm that determines whether there are three elements in a given array of integers that sums to exactly a given integer value k. As input, you are given an array of n integers and an integer value k. (Note that the efficiency of your algorithm will be considered in grading) For example, given the array [1, 3, 7, 4) and k - 14, the answer is yes", given k = 6 the answer is no." b. 15 pts) Identify a basic operation for your algorithm and study the performance of your algorithm by giving its time complexity function. If it has an every-case time complexity, determine it . Otherwise, determine the worst-case time complexity. C. [2 pts) Identify the complexity category to which the algorithm belongs. d. [5 pts) Implement your algorithm using Java. Write a main method that asks the user to enter the integer value k and the size n of an array of integers. The main method must generate the array elements randomly. As output, the program must first print all elements of the array. Then, it should print "No" if the array does not contain three elements that sums to k or print "Yes" if there are three elements that sums to k. If the output is "Yes", the program must print these three elements and their location index in the array Q4. [20 pts] Designing and Implementing an Algorithm-Longest increasing sequence a. [8 pts) Write an algorithm to find a subsequence of a given sequence of integers in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. The algorithm should print one of the existing longest subsequences. (Note that the efficiency of your algorithm will be considered in grading.) For example, in the following sequence of integer values: 0,8, 4, 12, 2, 10, 6, 14, 1,9.5, 13.3.11, 7.15 A longest increasing subsequence is 0.2,6,9, 11, 15. This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not the only solution: for instance 0, 4, 6, 9, 11, 15; 0, 2, 6, 9, 13, 15 ; and 0, 4, 6, 9, 13, 15 are other increasing subsequences of equal length in the same input sequence. b. [5 pts] Identify a basic operation for your algorithm and study the performance of your algorithm by giving its time complexity function. If it has an every-case time complexity, determine it. Otherwise, determine the worst-case time complexity. c. [2 pts) Identify the complexity category to which the algorithm belongs. d. [5 pts] Implement your algorithm using Java. Write a main method that asks the user to enter the integer value k and the size n of an array of integers. The main method must generate the array elements randomly. As output, the program must first print all elements of the original input sequence, then, it should print the length of the longest subsequence, and finally the elements of one of the longest subsequence