Homework 6, Part A: Doubly Linked Lists (in pairs)

Here, you will create your own implementation of a doubly linked list. A doubly linked list is a linked list in which every node maintains a reference to the item next in the list, as well as the item previous in the list:

Task 0: Getting Settled

Copy over the List<T> interface below. Your linked list should implement this interface.

The List Interface.

public interface List<T> {
    /**
     * Checks if the list is empty
     * 
     * @return true if the list is empty, false otherwise
     */
    public boolean isEmpty();
    
    /**
     * Returns the size of the list
     * 
     * @return the size (or length) of the list
     */
    public int size();

    /**
     * Returns the element at the specified position from the list
     *
     * @param index of the element in the list
     * @return the element to be returned
     */
    public T get(int position);

    /**
     * Inserts an element at the given position in the list.
     * 
     * @param the index of the element to be added
     * @param the element to be added
     */
    public void insert(int position, T element);
    
    /**
     * Removes the element at the specified position from the list
     * 
     * @return the element to be returned
     */
    public T remove(int position);

    /**
     * Generates a String representation of list; 
     * first element in the representation is the front
     * 
     * @return a String representation of the list
     */
    public String toString();
}

Task 1: Doubly Linear Node

Create a class, DoublyLinearNode<T>, to represent a node in your linked list. You can follow the LinearNode from the class for inspiration.

Task 2: Implementing the Doubly Linked list

Create a class, DoublyLinkedList<T> that uses your DoublyLinearNode<T> to implement the List<T> interface. Before implementing each method, draw a memory diagram to make sure you know what pointer manipulations you plan to use. You may find it helpful to draw multiple versions of these memory diagrams corresponding to lists of various sizes.

Additionally, in your implementation, please:

• Store both a reference to the front of the list and the rear.
• Update these references appropriately when inserting/removing.
• Use the reference to rear for fast get/insertion/removal from the very end of the list (i.e. if someone wants to operate on the last element of the list, they shouldn’t have to iterate over the whole list to find it).

Hint: For both insert and remove, you may want to break your code into several cases:

• When the list is empty
• When removing from a list of size 1
• When inserting/removing at the front
• When inserting/removing at the rear

Hint: Feel free to throw RuntimeExceptions when anything goes wrong, and no need to work in javafoundations for this particular exercise.

Task 3: Testing

Please test your DoublyLinkedList<T> in a main method belonging to the same class. You can save your tests in DoublyLinkedListTests.txt. There’s no need to test your DoublyLinearNode<T>.

Homework 6, Part B: Community learning (in pairs)

In class, on Friday, we worked on answering a set of questions. In this task, we will work on a process of iterative feedback, to get to deeper understanding on these topics as a community.

1. In these slides, find your group number for this homework - note, there are two slides per group.
2. Come up with a final answer for the questions assigned to your group by Friday 10/24 at 5pm. Make sure to have clear and complete sentences, and appropriate terminology.
3. Individually, find the questions you asked, and provide feedback to the answers you received by Monday 10/27 at 10pm. Include these as comments in the slides themselves.
4. As a group, come up with a final answer to the questions you’ve been assigned in a new google document, that contains your name and your partner’s name in the title. Share this google doc with me and submit it to Gradescope by the deadline included in our schedule.

Homework 6, Part C: While my guitar weeps (individual)

Learning Goals

• Extend a known Data Structure (Queue), to create a new, special-purpose Data Structure (BoundedQueue)
• Use this special-purpose Data Structure in an simulation of a guitar playing music

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:

• A constructor that takes an integer argument, which is the capacity of the bounded queue
• A predicate isFull() that indicates whether the bounded queue is at capacity or not
• An enqueue() method that overrides the javafoundations.CircularArrayQueue’s enqueue() method so that it only enqueues an element if the queue is not at capacity.

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:

• public GuitarString(double frequency); The constructor creates a guitar string of the given frequency, using a sampling rate of 44,100. It initializes a bounded queue of the desired capacity N (sampling rate divided by the frequency, rounded up to the nearest integer), and fills the bounded queue with N zeros to model a guitar string at rest.
  

• public void pluck(); The pluck() method replaces the N samples in the bounded queue with N random values between -0.5 and +0.5:
  

• public double sample(); The sample() method returns the value of the item at the front of the bounded queue:
  

• public void tic(); The tic() method applies the Karplus-Strong algorithm, i.e., it deletes the sample at the front of the bounded queue and adds to the end of the bounded queue the average of the deleted sample and the sample at the front of the bounded queue, multiplied by the energy decay factor of 0.994:

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