Spring 2024 Type Name: CSC175 Assignment 6 Directions: Download this file and save as lastnameAssignment6SP24. Type all solutions on this document. Upload Word document to Blackboard by! . Show work and explain concepts thoroughly! Note: Recall that A[1] refers to the first element of the list A, A[2] is the second, etc. [3] points for a professional looking document (organization, neatness, etc.) 1) [6] Use the Euclidean Algorithm to find: (show each step of the algorithm) a) GDC(693,600) b) GCD(1260,125) 2) Consider the sorted list: 11 17 18 21 23 27 28 29 33 40 41 52 57 a) [1] What is the most steps it could take to find a number if we traveled through the list one at a time? Why? b) [2] What is the most steps it could take to find a number if we traveled through the list using binary search? Why? c) [5] Use binary search to find 27. Explain how you used the algorithm at each step. 3) a) [2] Give the Big O runtime for the following algorithm. Explain your answer. Begin FunAlgorithm (List of numbers A) Enter N (length of A) print N " is the length of A." M=N*4 print M " is a multiple of 4." If N<7 then print "A has less than 7 elements." Else if N>9 print "A has more than 9 elements." Else print "A has between 7 and 9 elements, inclusive." W = A[N-1]*5 print W" is a multiple of 5." print "Algorithms are fun!" End FunAlgorithm b) [5] For the FunAlgorithm above, what would the output be if A = (3, 44, 23, 4, 69, 223, 14, 4, 21, 34, 52)? c) [2] Give the Big O runtime for the following algorithm. Explain your answer. Begin Find28Algorithm (List A of unsorted numbers which includes the number 28) Enter N (length of A) Conduct Insertion Sort on A Conduct Binary Search on A to find the number 28 End Find28Algorithm d) [2] How would the Big O runtime change for Find28Algorithm if A was sorted? e) [2] Give the Big O runtime for the following algorithm. Explain your answer. Begin TwoDigitsAlgorithm (List A of integers) Enter N (length of A) print N " is the length of the list A." For i = 1 to N-1 For j =i+1 to N If A[i]=A[j] print A[i] End If End For End For For k = 1 to N If A[k]<10 or A[k]>99 print A[k] " is not a two-digit integer." End If End For End TwoDigitsAlgorithm f) [2] What is TwoDigitsAlgorithm doing? Be as clear as possible. g) [3] For TwoDigitsAlgorithm above, what would the output be if A = (44, 23, 4, 69, 223, 44, 4, 21, 34, 52)? 4) Consider the list 16 8 12 23 6 10 25 19 20 a) [5] Use bubble sort to sort the list. Show each swap. How many swaps took place? b) [7] Explain how merge sort works in your own words. Use merge sort to sort the list. Show each step. c) [7] Explain how insertion sort works in your own words. Use insertion sort to sort the list. Show each step. 5) [6] Answer each question. a) What is the best case runtime for Quicksort? When does that occur? b) What is the worst case runtime for Quicksort? When does that occur? c) What is Big O notation for merge sort? Generally does it differ from best to worst case runtime? Why do you think that is the case?