Wellesley College
CS230: Data Structures in Java
Fall 2025

Homework 9, Part A: Guitar

Learning Goals

Exercise: While My Guitar Gently Weeps

In this exercise, you will learn how to simulate the plucking of a guitar string with the Karplus-Strong algorithm. Play the video below to see a visualization of the algorithm. If your browser won’t play the video below, you can right-click on it and save it to your Desktop to play it from there.

When a guitar string is plucked, the string vibrates and creates sound. The length of the string determines its fundamental frequency of vibration. We model a guitar string by sampling its displacement (a real number between -1/2 and +1/2) at N equally spaced points (in time), where N equals the sampling rate (44,100) divided by the fundamental frequency (rounding the quotient up to the nearest integer).

Plucking the string. The excitation of the string contains energy at any frequency. We simulate the excitation with white noise: set each of the N displacements to a random real number between -1/2 and +1/2.

The resulting vibrations. After the string is plucked, the string vibrates. The pluck causes a displacement which spreads wave-like over time. The Karplus-Strong algorithm simulates this vibration by maintaining a bounded-queue of the N samples: the algorithm repeatedly dequeues the first sample from the bounded queue and enqueues the average of the dequeued sample and the front sample in the queue, scaled by an energy decay factor of 0.994.

Task 0

Download this starting code that will allow you to complete the tasks below.

Task 1

Write a BoundedQueue.java class that implements a bounded queue ADT. A bounded queue is a queue with a maximum capacity: no elements can be enqueued when the queue is full to its capacity. The BoundedQueue class should inherit from the javafoundations.CircularArrayQueue class, given in the starting code.

Your BoundedQueue.java file should contain implementations for the following methods:

You should not add any more instance methods to this class implementation. But, of course, you should be providing evidence of testing your implementation in the main().

Make sure you test this class before continuing to the next task.

Task 2

Write a GuitarString class that models a vibrating guitar string according to the following contract:

Task 3

Now you should be ready to test your code from the previous tasks. Compile and run the provided GuitarHeroine application. If you have successfully completed the previous tasks, then when you run the application, a window should appear as follows:

Now, you can make sweet music. By pressing any of the keys on your computer keyboard corresponding to the notes as illustrated in the piano keyboard image, you can simulate plucking a guitar string for that note (make sure that your computer’s sound is not muted).

What to submit

In Gradescope submit the following files:

  1. The BoundedQueue.java file
  2. Your testing transcript (BoundedQueue.txt) for BoundedQueue class
  3. The GuitarString.java file


Homework 9, Part B: Tree Recursion

Learning Goals

Tasks

First, create a BlueJ project with the following starter code.

BTNode.java:

import java.util.LinkedList;

public class BTNode<T> {
    protected T element;
    protected BTNode<T> left, right;

    public BTNode(T elmt) {
        element = elmt;
        left = right = null;
    }

    public T getElement() { 
        return element; 
    }

    public void setElement(T element)
    { this.element = element; }

    public BTNode<T> getLeft() { 
        return left; 
    }

    public void setLeft(BTNode<T> left) { 
        this.left = left; 
    }

    public BTNode<T> getRight() { 
        return right; 
    }

    public void setRight(BTNode<T> right) {
        this.right = right; 
    }

    public BTNode<T> find(T target) {
        BTNode<T> result = null;

        if (element.equals(target)) {
            result = this;
        } else {
            if (left != null)
                result = left.find(target);
            if (result == null && right != null)
                result = right.find(target);
        }

        return result;
    }

    public int count() {
        int result = 1;

        if (left != null)
            result = result + left.count();

        if (right != null)
            result = result + right.count();

        return result;
    }

BSTNode.java:

public class BSTNode<T extends Comparable<T>> extends BTNode<T> {

    public BSTNode(T element) {
        super(element);
    }

    public void add(T item) {
        if (item.compareTo(element) < 0) {
            if (left == null)
                left = new BSTNode(item);
            else //  Add recursively 
                ((BSTNode) left).add(item);
        } else { //  item >= element, go right
            if (right == null)
                right = new BSTNode (item);
            else //  Add recursively 
                ((BSTNode) right).add (item);
        }
    }

    public BSTNode<T> find(T target) {
        if (target.compareTo(element) == 0)
            return this;
            
        // Since left and right are defined as BTNodes in the parent class,
        // we cast them to BSTNodes here so we can call compareTo
        BSTNode<T> l = (BSTNode<T>) left;
        BSTNode<T> r = (BSTNode<T>) right;
        
        if (target.compareTo(element) < 0 && l != null) {
            return l.find(target);
        }
            
        if (r != null) {
            return r.find(target);
        }
        
        return null;
    }
}

Next, implement the following instance methods:

  1. Implement public int countLeaves() in the BTNode class. This method should return an integer counting the number of leaves in tree.
  2. Implement public int countNodesAtLevel(int level) in the BTNode class. This method should return the number of nodes at a given level in the tree. In this method, we’ll say that level 0 represents the root.
  3. Implement public LinkedList<T> collectOnlyChildren() in the BTNode class. This method should return a list of all elements T that belong to nodes that have no siblings.
  4. Implement public boolean isValid() in the BSTNode class. This method should return true if the tree is a valid binary search tree.

Please test your code as you go, putting your test in a driver class called Driver.java.


Submission Checklist