CSCI 161 Exam 1 Study Guide Flashcards

Harmonic Numbers

• The nth Harmonic number ( H_n ) is computed using the formula: ( H_n = \sum_{k=1}^{n} \frac{1}{k} ).
• Recursive Java method to compute ( H_n ):

  public static double harmonic(int k) {
      if (k == 1) return 1.0;
      else return 1.0 / k + harmonic(k - 1);
  }
  

Queue Data Structure

• A queue operates under first-in, first-out (FIFO) principles.
• Classic operations include:
  • enqueue: Adds an item to the queue.
  • dequeue: Removes and returns the item from the front.
  • isEmpty: Checks if the queue is empty.
  • isFull: Checks if the queue is full.
• Java generic interface for a queue:

  interface Queue<T> {
      void enqueue(T newItem);
      T dequeue();
      boolean isEmpty();
      boolean isFull();
  }
  

Generics and Array Manipulation

• Method to remove an item at index i from a generic ArrayBag:

  public T remove(int i) {
      T returnValue = bag[i];
      for (int j = i; j < bag.length - 1; j++)
          bag[j] = bag[j + 1];
      bag[bag.length - 1] = null; // optional
      count--; // optional
      return returnValue;
  }
  

Factorial Trace

• Factorial method creates a tree of calls when tracing recursion (not displayed here).

Deep Copy in Java

• Deep copy method for Player class:

  public Player copy() {
      return new Player(name, jersey);
  }
  

Deep Copy of Player Array

• Creating a deep copy of an array of Player objects:

  Player[] teamCopy = new Player[team.length];
  for (int i = 0; i < team.length; i++)
      teamCopy[i] = team[i].copy();
  

Equality Check in Player Class

• equals method for comparing Player objects:

  public boolean equals(Object o) {
      if (!(o instanceof Player)) return false;
      Player obj = (Player) o;
      return this.name.equals(obj.name) && this.jersey == obj.jersey;
  }
  

Singly Linked List Operations

• Method to get the second-to-last node in a singly linked list:

  public Node nextToLast(ListBag list) {
      if (list.size < 2) return null;
      Node temp = list.head;
      while (temp.next.next != null) temp = temp.next;
      return temp;
  }
  

Nested and Inner Classes

• A class defined within another class is termed a nested class.
• A non-static nested class is known as an inner class.

Handling ClassCastException

• Prevent ClassCastException by using instanceof to check types before casting.

Clearing a Stack Recursively

• Recursive method to clear all elements from a generic stack:

  public void clearStack(Stack s) {
      if (s.isEmpty()) {
          System.out.println("stack is empty"); // optional
      } else {
          s.pop();
          clearStack(s);
      }
  }
  

Copying an ArrayList

• Method for creating a deep copy of an ArrayList of Integers:

  public static ArrayList<Integer> deepCopy(ArrayList<Integer> source) {
      ArrayList<Integer> copy = new ArrayList<>(source.size());
      for (int i = 0; i < source.size(); i++)
          copy.add(source.get(i));
      return copy;
  }
  

Algorithmic Complexity

• O(n²) can be preferable over O(n) if the constants involved in O(n) are significantly large for small values of n.

Algorithm Running Time Analysis

• The running time of the algorithm is analyzed using Big-Oh notation, with detailed counting of operations:
  • Total operations: ( 6n - 1 ) where n is the input size.