Final Review

Topics since Exam 2

• recursion
  • defining the base case
  • making progress toward the base case with each recursive call
  • tracing recursive methods
  • helper methods
• algorithm analysis
  • big-oh
  • analysis of code/pseudocode
• linked lists
  • implementation
  • insertion/deletion
  • running time of common operations (add, remove)
  • advanced methods - examples:
    • recursive reversal of list using constant extra space
    • find common elements of two sorted lists

Other topics

• Java syntax
• Components of a Java class
• Elements of a method
  • Method implementation
  • Calling methods
• Statements and mathematical expressions
• Conditionals (if statements)
• Iteration (for, while, do-while)
• Arrays
• Strings
• Collections Framework
• -ArrayList
• -HashMap
• Inheritance/Interfaces
• -vocabulary: protected, super, extends, abstract, final
• -casting
• -polymorphism
• -overriding and partial overriding
• -dynamic binding
• -Comparable
• Exceptions
  • checked/unchecked
  • propagating versus using try/catch

Practice questions

1. Write a while loop that verifies that a user enters a positive integer value.

2. Write a method called evenlyDivisible that accepts two integer parameters and returns true if the first parameter is evenly divisible by the second, or vice versa, and false otherwise. Return false if either parameter is zero.

3. Write a method that takes as input an array of integers and will print the array in reverse order. You do not need to use recursion for this question.

4. Write a method getIth for the LinkedList class. The method will take as input an integer i and will return the Comparable object from the ith node in the list. For a list containing A, B, C, D, E (in that order), given the input 2 the method would return B.

5. What does the following method of a LinkedList class do?

public boolean mystery() {

if(this.head == null) {

return true;

}

return mystery(this.head, this.head.getNext());

}

private boolean mystery(Node n1, Node n2) {

if(n2 == null)

return true;

if(n1.getData().compareTo(n2.getData()) < 0)

return mystery(n2, n2.getNext());

return false;

}

6. Implement a recursive method that takes as input a char and a String and returns the number of times the char appears in the String. Given input 'c' and 'computer' the method would return 1. For full credit, implement this method without using any loops.

7. Implement a LinkedList method removeLastN. The method takes as input an integer n and removes the last n nodes from the list. If the list contained 6 nodes, a call to removeLastN(3) would result in the list containing the first three nodes of the original list (e.g., original list: head->A->B->C->D->E->F new list: head->A->B->C)

(a) How would do this without a size variable or method?

(b) How would you do this if you could only traverse the list one time?

8.Implement a method that takes as input two int[] arr1 and arr2 and returns a new int[] where the ith position of the new array is the sum of the ith position of arr1 and the ith position of arr2. Examples: arr1={1, 2, 3} arr2={4, 5, 6} returnedarr={5, 7, 9} arr1={1, 2, 3} arr2={4, 5} returnedarr={5, 7, 3}