Midterm Exam

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Spring 2023

Start of Midterm Exam	End of Midterm Exam
2:00 PM on Wednesday March 29, 2023	11:59 PM on Sunday April 16, 2023
There will be no extensions and No late submissions will be accepted

Overview

Your midterm exam will is in two parts:

Part I (50 Points)

This part of the midterm exam will consist of 50 multiple choice questions. You will find this part of the midterm exam on Blackboard in the Exams folder. You will be allowed to take this part of the exam, up to, 3 times; the highest grade will be the only one that counts. Each time you take this part of the exam, you will have 60 minutes the complete it, unless you communicated your need for extra time, in which case you will have 90 minutes to complete it.

Part II (60 Points)

This part of the midterm exam will be programming based and you will be submitting your code for testing to your zyBooks textbook . You will implement and test the DoubleEndedQueue. Users of a DoubleEndedQueue are allowed to add and remove elements from both the front and back of the double ended queue. Your DoubleEndedQueue will be implemented as a doubly linked structure (i.e. All nodes have next and previous node references). In addition, you will also be writing a driver to use your DoubleEndedQueue.

Part II Details

1. DoubleEndedQueue Class

   You will write the DoubleEndedQueue.java class which will implement the DoubleEndedQueueInterface , from your zyBooks textbook DoubleEndedQueue.java will be implemented as a doubly linked structure.

   Your DoubleEndedQueue class must have the following private instance variables:

   front

   A reference to the front Node in the DoubleEndedQueue, initially set to null.

   back

   A reference to the back Node in the DoubleEndedQueue, initially set to null.

   size

   An int coresponding to the number of elements in the DoubleEndedQueue, initially set to 0.

2. ElementIterator Class

   Your ElementIterator will extend Iterator. Please see the documentation for the Iterator<T> . Your ElementIterator class will implement both the hasNext() and next() methods of this interface.

   Your DoubleEndedQueue class must implement the Iterable<T> interface. Implementing this interface requires that your provide a method in your DoubleEndedQueue with the following signature: public Iterator iterator(). Please see the documentation for the Iterable<T> . The Iterator you will build and return will actually be an ElementIterator.

3. Node Class

   You will use the provided Node.java which can be downloaded from from your zyBooks textbook .

   Please note that each Node has references to both the previous and the next nodes as well as a reference to the contained element.

4. Driver Class

   You will write the Driver.java class to test your implementation of DoubleEndedQueue.java.

   Your Driver.java class will implement the Driver Interface . The interface may be downloaded from from your zyBooks textbook .

Please submit the completed exam in your zyBooks textbook .