# LAD Block 4: Implementing and applying algorithms

 Is it possible to have a best case constant time function for finding a value in an array? No, because it would have to terminate before is has looked at the other values.Exception would be to find minimal value in a sorted array. Describe a algorithm in pseudo code that stores the 3 greatest values of an array. array A Int max1=0, Max2=0, Max 3=0 ; for (int i =0 ; i Max1) {Max3 =Max2 ;Max2 =max1 ;Max1= A[i]} if (A[i]>Max2) {Max3 =Max2 ;Max2= A[i]} if (A[i]>Max3) Max3= A[i]} } Write the body of a method: public static boolean hasDuplicates(int[] a, int k)  That takes an array of numbers and a constant k, where all numbers in the array are between 0 up to and including k. It returns true if and only if the array contains any duplicate values. For full points the worst case time (and memory) complexity of your function should be O(k). if(a.length > k) return true;Boolean[] bs = new Boolean [k+1] ; for(int i=0 ; i= low) { int middle = (low + high) / 2 ; if( arr[middle] == x ) return true ;  if( arr[middle] < x ) {low = middle +1 ;} if ( arr[middle] > x ){high = middle -1}}return false;} Use class Heap with a constructor Heap() together with methods void add(int element) int removeMin()  to write the body of a method:  public static void heapSort(int[] arr)  That takes an array and sorts it using the Heap sort algorithm. public static void heapSort(int[] arr){Heap h = new Heap();  for(int i=0 ; i < arr.length ; i++) { h.add(arr[i])}  for(i=0 ; i arr.length; i++) {arr[i] = h.removeMin();} } Write the body of a method:  public static int countCommon(int[] a, int [] b) That takes two sorted arrays and returns the number of values that are in both arrays (you may assume there are no duplicates in either array). For instance for inputs {1,2,4,5,7} and{2,4,6,7,8} the result would be 3 because 2, 4 and 7 are in both arrays. Complexity should be linear in the input size. (Hint: Use a simplified version for the merge algorithm for sorted arrays) public static int countCommon(int[] a, int [] b) {int i = 0 , j=0 , res=0; While (i[b[j] )  j++;  else { res++ ; i++ ; j++; }} return res ;} Hur byter man plats på två element i en array? Först sparar man ett av elementen Sen byter genom att skriva över de sparadeSen sätt tillbaks de sparade på sin nya plats Code an insertion sort algo Code a depth first Search/Traversal for tree using a stack Code a breadth first search/Traversal on a tree Code a linear search Code Selection sort Code merge sort Authorccc ID329489 Card SetLAD Block 4: Implementing and applying algorithms DescriptionLAD Block 4: Implementing and applying algorithms Updated2017-03-15T18:05:30Z Show Answers