LAD Block 4: Implementing and applying algorithms

Home > Preview

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
    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();
    • }

    }
  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
    Image Upload
  9. Code a depth first Search/Traversal for tree using a stack
    Image Upload
  10. Code a breadth first search/Traversal on a tree
    Image Upload
  11. Code a linear search
    Image Upload
  12. Image Upload
    Image Upload
  13. Image Upload
    Image Upload
  14. Image Upload
    Image Upload
  15. Image Upload
    Image Upload
  16. Image Upload
    Image Upload
  17. Code Selection sort
    Image Upload
  18. Image Upload
    Image Upload
  19. Image Upload
    Image Upload
  20. Image Upload
    Image Upload
  21. Image Upload
    Image Upload
  22. Code merge sort
    Image Upload

Card Set Information

Author:
ccc
ID:
329489
Filename:
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:

Home > Flashcards > Print Preview