CSCI 161 Exam 1 Study Guide Flashcards

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the recursive Java method for computing the nth Harmonic number?

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

What is the generic Java interface for a classic queue?

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

How do you remove and return the ith item from an array in the ArrayBag class?

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; count--; return returnValue; }

What is the name for a class defined inside of another class?

nested Signup and view all the answers

A non-static class defined inside another class is known as an ____________ class.

inner Signup and view all the answers

How can you avoid throwing ClassCastException errors?

Use instanceof to determine if the cast can be made before attempting the cast. Signup and view all the answers

What is the recursive method for removing all elements from a generic stack?

public void clearStack(Stack s) { if (s.isEmpty()) { System.out.println("stack is empty"); } else { s.pop(); clearStack(s); } } Signup and view all the answers

Write a method that returns a pointer to the second-to-last node in a singly linked list.

public Node nextToLast(ListBag list) { if (list.size < 2) return null; else { Node temp = list.head; while (temp.next.next != null) temp = temp.next; return temp; } } Signup and view all the answers

Write a method to create a deep copy of an ArrayList of Integers.

public static ArrayList deepCopy(ArrayList source) { ArrayList copy = new ArrayList(source.size()); for (int i = 0; i < source.size(); i++) { int x = source.get(i); copy.add(x); } return copy; } Signup and view all the answers

What are the advantages and disadvantages of using sentinels in a doubly linked list?

Advantages: Head and tail pointers never change. Insertion and deletion always occur between nodes. Disadvantages: Extra memory used by sentinel nodes. Signup and view all the answers

Under what circumstances might the algorithm with O(n^2) be a better choice than O(n)?

If the coefficients on O(n) are large enough, they may overshadow the effect of O(n^2) for small values of n. Signup and view all the answers

What is the Big-Oh notation for the running time of the algorithm xyz?

O(n) Signup and view all the answers

Study Notes

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.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Prepare for your CSCI 161 exam with this comprehensive study guide featuring flashcards that cover key concepts such as recursive methods and data structures. Test your understanding of harmonic numbers and queue operations through examples and definitions. Perfect for reinforcing your knowledge prior to the exam.