# LAD Block 4: Implementing and applying algorithms

The flashcards below were created by user ccc on FreezingBlue Flashcards.

1. 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.
2. 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 <n.length() ; i++){

• if (A[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]
• }

}
3. 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<a.length ; i++) {

if(bs[a[i]] == true) return true;

• bs[a[i]] = true ;
• }

• return false ;
• }
4. Implement a binary search on an array of integers.
Describe the algorithm in java code.Make both the head of the function and the body.
• public Boolean binaryS ( int[] arr , int x) {
• int low = 0 ;
• int high = arr.length-1 ;

while(high>= 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;
• }
5. Use class Heap with a constructor Heap()
together with methods
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++) {

• for(i=0 ; i arr.length; i++) {
• arr[i] = h.removeMin();
• }

}
6. 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<a.length && j <b.length) {
•
• if( a[i]<b[j] )  i++ ;

else if( a[i]>[b[j] )  j++;

• else { res++ ; i++ ; j++; }
• return res ;
• }
7. Hur byter man plats på två element i en array?
• Först sparar man ett av elementen
• Sen byter genom att skriva över de sparade
• Sen sätt tillbaks de sparade på sin nya plats
8. Code an insertion sort algo
9. Code a depth first Search/Traversal for tree using a stack
10. Code a breadth first search/Traversal on a tree
11. Code a linear search
12. Code Selection sort
13. Code merge sort
 Author: ccc ID: 329489 Card Set: LAD Block 4: Implementing and applying algorithms Updated: 2017-03-15 18:05:30 Tags: LAD Block Implementing applying algorithms Folders: Description: LAD Block 4: Implementing and applying algorithms Show Answers: