CSC Final (Searching/Sorting - Generics)

bubble sort

public void sort(int[] array) {
        boolean done = false;
        int passes = 0;
        while(!done)  {
            passes++;
            done = true;
            for(int i=1;i<array.length;i++) {
                if(array[i-1] > array[i]) {
                    swap(array,i-1,i);
                    done = false;
                }
            }
        }
        //System.out.println("passes="+passes);
    }

Which sorting algorithm is this?

selection sort

which sorting algorithm is this?

public void sort(int[] array) {
        for(int i=0;i+1<array.length;i++) {
            int imin = i;
            for(int b=i+1;b<array.length;b++) {
                if(array[b] < array[imin]) {
                    imin = b;
                }
            }
            swap(array,imin,i);
        }

merge sort

which sorting algorithm is this?

 public void sort(int[] array) {
        sort(array,0,array.length);
    }

 public void sort(int[] array,int start,int end) {
        if(end-start < 2)
            return;

        int mid = start+(end-start)/2;
        sort(array,start,mid);
        sort(array,mid,end);


        int[] first = new int[mid-start];
        int[] second = new int[end-mid];
        for(int i=0;i<first.length;i++) {
            first[i] = array[i+start];
        }
        for(int i=0;i<second.length;i++) {
            second[i] = array[i+mid];
        }
        int i1 = 0, i2 = 0, i = start;
        while(i1 < first.length && i2 < second.length) {
            if(first[i1] <= second[i2]) {
                array[i] = first[i1];
                i1++;
                i++;
            } else {
                array[i] = second[i2];
                i2++;
                i++;
            }
        }
        while(i1 < first.length) {
            array[i] = first[i1];
            i1++;
            i++;
        }
        while(i2 < second.length) {
            array[i] = second[i2];
            i2++;
            i++;
        }
}

quick sort

which sorting algorithm is this?

     int n = end - start;
        if(n < 2)
            return;
        int pivot = RAND.nextInt(n)+start;
        int p = array[pivot];
        
        int i1=start, i2=end;
        // put values less than the pivot in the front
        for(int i=start;i<end;i++) {
          if(array[i] < p) {
            swap(array,i,i1);
            i1++;
          }
        }
        // put values more than the pivot at the end
        for(int i=end-1;i>=i1;i--) {
          if(array[i] > p) {
            i2--;
            swap(array,i,i2);
          }
        }
        // sort everything not equal to the pivot
        sort(array,start,i1);
        sort(array,i2,end);
    }

linear search

which searching algorithm is this?

 public int search(int[] array,int val) {
        for(int i=0;i<array.length;i++)
            if(array[i] == val)
                return i;
        return -1;
    }

binary search

which searching algorithm is this?

 public int search(int[] array,int val) {
        int step = 0;
        int lo = 0, hi = array.length-1;
        while(lo <= hi) {
            step++;
            int mid = lo+(hi-lo)/2; // just like (lo+hi)/2, but avoids overflow
            int diff = array[mid]-val;
            if(verbose) {
                System.out.println("step "+step+": lo = "+lo+", hi = "+hi);
                System.out.println("    mid="+mid);
                System.out.println("    diff="+array[mid]+" - "+val+"="+diff);
            }
            if(diff == 0) {
                if(verbose) System.out.println("    done!");
                return mid;
            } else if(diff < 0) {
                lo = mid+1;
                if(verbose) System.out.println("    lo = "+lo);
            } else {
                hi = mid-1;
                if(verbose) System.out.println("    hi = "+hi);
            }
        }
        return -1;
    }

head

x.next

tail

link.next

x.next

x.next

link

link.next

fill in the blanks for the linked list code:

public class MyLinkedList {
    static class Link{
        Object data;
        Link next;
        Link(Object data){
            this.data = data;
        }
    }
    Link head, tail;
    
    public void insert(int pos, Object o){
        Link link = new Link (o);
        Link x = /* a */;
        
        for(int counter = 0; counter < pos - 1; counter++){
            x = /* b */;
        }
        
        if (head ==  null){
            head = /* c */ = link;
        } else{
            /* d */ = /* e */;
            /* f */ = /* g */;
        }
        if(/* h */ == null){
            tail = link;
        }
    }
}

options:
1. head.next
2. link
3. tail
4. tail.next
5. x.data
6. x
7. head
8. link.next
9. x.next
10. x.prev

1. .

2. ^

3. $

4. *

5. +

6. ?

7. []

8. ()

regex basic symbols:
1.___ (any single line character)

2.____ (start of line/string)

3.____(end of line/string)

4.____(0 or more preceding characters)

5.____(1 or more preceding characters)

6.____(0 or 1 of the preceding characters)

7.____(a set or range of characters)

8.____(grouping)

1. \d

2. \D

3. \w

4. \W

5. \s

6. \S

7. \b

8. \B

regex character symbols:
1._____ (digit)

2._____ (nondigit)

3._____ (word character)

4._____(non word character)

5._____(whitespace)

6._____(non whitespace)

7._____(word boundary)

8._____(non word boundary)

1. ‘ ‘

2. ‘ brown ‘

3. ‘ fox ‘

4. ‘ ‘

5. nothing

6. ‘ The ‘

what does the code print for each regex?

public class Reg {
    public static void test(String pattern){
        Scanner s = new Scanner("The_quick_brown_fox_jumps_over_the_lazy_dog. ");
        while(s.hasNextLine()){
            if(s.findInLine(pattern) != null){
                MatchResult m = s.match();
                System.out.println("'" +m.group(0)+ "'");
            }else{
                System.out.println("Nothing");
            }
            break;
        }
    }
    public static void main(String[] args) {
        test("(brown|fox)*"); //1
        test("(brown|fox)+"); //2
        test("(brown\\s+|fox)+"); //3
        test("((brown|fox)\\s+)*"); //4
        test("((brown|fox)\\s+)+"); //5
        test("(The|quick)*"); //6
    }
}

5. hashcodes can speed up access to an element of a map

6. sets contain items with unique values

7. if two objects have different hashcodes, they are not equal

select all that are true:
0. a hashcode of 1 always works
1. sets contain items with unique hashcodes
2. if you have proper hashcode, you don’t need to implement equals
3. a hashcode needs to be based on a random pivot
4. if two objects have the same hashcode, they are equal
5. hashcodes can speed up access to an element of a map
6.sets contain items with unique values
7. if two objects have different hashcodes, they are not equal
8. a hashcode is best implemented as a recursive function

lemon
orange
grape
lime

list all the fruit names printed

public class Boo {
    public static void main(String[] args) {
        Runnable test0 = ()->{
        System.out.println("apple");
        int[] d = new int[2];
        d[1] = 1;
    };
        Runnable test1 = ()->{
            System.out.println("peach");
            int[] e = new int[2];
            e[2] = 1;
        };
        
        Runnable test2 = ()->{
            System.out.println("lemon");
            int[] f = null;
            f[2] = 1;
        };
        
        try{
            int a = 3, b = 4;
            if(a < b){
                test0 = test2;
            }else if(a == b){
                test0 = test1;
            }
            test0.run();
            System.out.println("apricot");
        }catch(NullPointerException ex){
            System.out.println("orange");
        }catch(ArrayIndexOutOfBoundsException ex){
            System.out.println("banana");
        }finally{
            System.out.println("grape");
        }
        System.out.println("lime");
     }
}

line 0
line 2
line 5

which lines have errors?

package practice;
include java.util.*; //line 0
/**
 *
 * @author Kimber&Trinity
 */
public class Hanoi {//line 1
 List<List<Integer>> towers = new ArrayList<<>>(); //line 2
 final int size; //line 3
 public Hanoi(int size){ //line4
     size = this.size; //line 5
     for(int i = 0; i < 3; i++){
         towers.add(new ArrayList<>()); //line 6
     }
     for(int i = size - 1; i >= 0; i--){
         towers.get(1).add(i); //line 7
     }
 }
 public void move_one(int from, int to){
     int n = towers.get(from).size(); // line 8
     int val = towers.get(from).remove(n);
     towers.get(to).add(val); //line 9
 }
 public void move_n(int from, int to, int n){
     if(n==1){ // line 10
         move_one(from, to);
     }else{
         int other = 3 - from - to;
         move_n(from, other, n - 1);
         move_one(from, to);
         move_n(other, to, n -1);
     }
 }
}

[2,3,1]

what is the output?

public class MyKey implements Comparator<List<Integer>>{
    public int compare(List<Integer> a, List<Integer> b){
        int diff = 0;
        if(diff == 0) diff = a.get(2) - b.get(2);
        if(diff == 0) diff = a.get(0) - b.get(0);
        if (diff == 0) diff = b.get(1) -a.get(1);
        return diff;
    }
    public static void main(String[] args) {
        List<List<Integer>> mk = Arrays.asList(Arrays.asList(1,2,3),
                Arrays.asList(3,2,1), Arrays.asList(2,3,1), Arrays.asList(2,1,3),
                Arrays.asList(1,3,2), Arrays.asList(3,1,2));
        Collections.sort(mk, new MyKey());
        System.out.println(mk.get(0));
    }
}

1. O(1)

2. O(N³)

3. O(log N)

4. O(N)

5. O(N log N)

6. O(N²)

7. O(1)

8. O(N)

9. O(N log N)

10. O(log N)

11. O(N)

12. O(1)

what is the time complexity of each of the following?
1. remove from the front of a linked list
2. a function f that runs in f(N) = N² + N³/100 + 100 * N seconds
3. add into priority queue
4. remove from front of array list
5. a function f that runs in f(N) =.233 N + 2 f(N/2) seconds
6. selection sort
7. random access of array list
8. random access of linked list
9. quick sort
10. binary search
11. add to front of array list
12. add to front of linked list

6. spin + zorp

what is the best hashcode?

0. spin + warp

1. (int)java.lang.Math.PI

2. spin + cache

3. zorp;

4. super.hashCode()

5. random.nextInt(1000)

6. spin + zorp

7. spin + wheel

8. System.identityHashcode(wheel)

import java.util.Random;
public class DTable{
int warp;
final int spin;
public DTable(int s) { spin = s;}
int dabbo(){ return(wheel.nextInt(3) + cache++ + --warp) % spin;}
public boolean equals(Object o){
DTable that = (DTable) o;
return this.spin == that.spin;}
public int hashCode(){
return /*???*/
}
final static int zorp = 7;
static int cache = 0;
final static Random wheel = new Random();
}

map.containsKey(word)

map.put(word, map.get(word)+1)

map.put(word,1)

identify the missing items:

0. map.put(word) = 1
1. map.get(word) > 0
2. map.put(word, 1)
3. map.get(word) = 1
4. map.put(word, map.get(word) + 1)
5. map.containsKey(word)
6. map.put(word, count + 1)
7. map.put(word) = map.get(word) + 1
8. map.containsValue(word)
9. map.get(word)++

public class WordCount3{
final static Map<String, Integer> map = new HashMap<>();
public void addWord(String word){
if(/* item 0*/)
	/* item 1*/;
else
	/* item 2*/;
}}

Exception is a checked exception

Exception extends Throwable

IOException is a checked exception

choose all the options below that are true:
0. RuntimeException is a checked exception
1. Throwable extends Error
2. Exception is checked exception
3. Exception extends Throwable
4. Error is a checked exception
5. Error extends Exception
6. NullPointerException is a checked exception
7. IOException is a checked exception
8. Throwable extends RuntimeException
9. Throwable extends Exception

line 4

line 7

line 8

identify each line with a syntax error:

public class Fib{ //line 0
Integer n; //line 1
Fib(int n){this.n = n;} //line 2
int eval(){ //line 3
if(n<2) return n //line 4
Fib f1 = new Fib(n - 1), f2 = new Fib(n - 2); //line 5
return f1.eval() + f2.eval(); // line 6
}

public static void main(String[] args) raises Exception{ //line 7
Fib f = Fib(27); //line 8
System.out.println(f.eval()); //line 9
}}

1, 2, 4,8

choose all that are true:
0. a queue is a LIFO
1. balanced binary trees require keys that are comparable
2. balanced binary trees look up their keys in O(Log (N)) time
3. balanced binary trees look up their keys in O(N log N) time
4. binary trees keep keys in a sorted order
5. balanced binary trees look up their keys in O(N) time
6. balanced binary trees require keys with a valid hashCode
7. balanced binary trees require keys that are comparators
8. a stack is LIFO
9. balanced binary trees require keys with valid equals method

0. right == null

1. c == this.c

2. right = new Node (c )

3. right.add( c )

fill in the missing code:
0. right == null
1. compare(this,c) == 0
2. right == left
3. c < this.c
4. compare(this, c) < 0
5. right = new Node( c )
6. this.compareTo( c) < 0
7. right.add( c)
8. this.compareTo( c) == 0
9. c == this.c

class Node{
char c;
Node left, right;
Node(char c){this.c = c;}
}

public class BinaryTree{
void add(char c){
if(/* line 0 */){
if(/* line 1 */){
/* line 2 */;
} else{
/* line 3 */
}
}else if(/* code hidden*/){
/* code hidden */
}
}
...

3) 2 4

choose the best option from the list:
0) 4 2
1) 4 1
2) 1 4
3) 2 4
4) 4 3

import java.util.*; public class InAndOut{
public static void main(String[] args) throws Exception{
Stack<Integer> s = new Stack<>();
Queue<Integer> q = new LinkedList<>();
s.push(1); s.push(2); s.push(3); s.push(4);
q.add(1); q.add(2); q.add(3); q.add(4);
q.remove();
System.out.printf("%d_%d%n", q.remove(), s.pop());}}

RuntimeException

unchecked, subclass of exception, may be caught

Error

unchecked, subclass of throwable, should not be caught

finally

what keyword always runs?

stack

has push() to add to the end, pop() to remove from the end, and is LIFO

queue

has add() to add at end, remove() removes from the front, FIFO

Linked List

has addFirst(), addLast(), removeFirst(), removeLast(), can use either LIFO or FIFO

priority queue

add and remove or O(Log(N)), constructor can take a Comparator (class)

deque

has push() and pop() and can be used for a stack (interface)

Comparable

has compareTo() method, when a class wants to know how to compare objects to itself (interface)

Comparator

has compare() method, when a class wants to compare any two objects (interface)

set

a collection of unique objects

TreeSet

with a default constructor, a collection of unique Comparable objects

map

an associative map or unique keys to non unique values

TreeMap

with default constructor, a map with unique Comparable keys

hash key

needs equals() and hashCode(), equal objects have equal hashCodes, not vice versa!!

1. O(1)

2. O(N)

3. O(N)

4. O(1)

time complexities for Array List:
1. append:
2. prepend
3. insert:
4. get():

1. O(1)

2. O(1)

3. O(N)

4. O(N)

time complexities for Linked List:
1. append:
2. prepend:
3. insert:
4. get():

O(Log N)

balanced binary trees are what time complexity?

Binary Trees

keeps nodes in sorted order
balanced if the height of left and right nodes differ by at most one
operations are easily expressed in recursive form

1. use instanceof

2. instantiate arrays

3. access the class

what can you NOT do in Generics:
1.
2.
3.