Design an algorithm which gets as input a list of k integer values

Design an algorithm which gets as input a list of k integer values N1, N2, ……, Nk as well as a special value SUM. Your algorithm must locate a pair of values in the list N that sum to the value SUM. (10 points) For example, if your list of values is 3, 8, 13, 2, 17, 18, 10, and the value of SUM is 20, then your algorithm would output either the two values (2, 18) or (3, 17). If your algorithm cannot find any pair of values that sum to the value SUM, then it should print out the message ‘Sorry, there is no such pair of values. Work out your algorithm to verify that it will work correctly for the given list and SUM in example. (10 points) Q2. For a shuffle-left algorithm, the best case occurs when the list has no 0 values and worst case occurs when the list has all 0 values. Prove this by taking a two lists of your choice where one is for best case and one for worst case. Show all the comparisons and copies in each step to prove the given statement of best and worst case. Do not write only the points given by the book. Show the workout to show the reasons. (15) Q3. Below is the algorithm for Bubble Sort. 1. Get values for n and the n list items 2. Set the marker U for the unsorted section at the end of the list 3. While the unsorted section has more than one element do steps 4 through 8 4. Set the current element marker C at the second element of the list 5. While C is has not passed U, do steps 6 and 7 6. If the item at position C is less than the item to its left then exchange these two items 7. Move C to the right one position 8. Move U left one position 9. Stop a) Using the bubble-sort algorithm, for each of the following lists, perform sorting, and show the list after each exchange. (5+5 points) i) 4, 8, 2, 6 ii) D, B, G, F, A, C, E b) Explain and prove why the bubble sort algorithm above does T(n2) comparisons on an n-element list. (20 points) Q4) Design a circuit that has three inputs and one output.