CS2223-B23 Term (02) Homework 1

Homework Instructions

• This homework is to be completed individually. If you have any questions as to what constitutes improper behavior, please review the Course Policies.
• Submit your assignments electronically using the canvas site for this class. You must submit a single ZIP file that contains all of your code as well as the written answers to the assignment.
• All of your Java classes must be defined in a package edu.wpi.cs2223.algorithms.week1.USERID where USERID is your WPI user name (the letters before the @wpi.edu in your email address). 
• You should not use any Java collection utilities - since we are building low level collection functionality from scratch we need to stick to building the operations from the ground up.
• Please see the Late Work Policy section at Home  for any questions about late submissions.

Setting Up

Follow the steps here  to set up IntelliJ, git, and the IntelliJ project for Week 1 of this class.  

Once you have the class project set up and are able to execute tests and watch them pass you are ready to start coding!.

Start by creating the following package: edu.wpi.cs2223.algorithms.week1.USERID

All of the code that you write for this assignment will go in this package.

Problem One - FixedCapacityArrayQueue

In class, Friday 10/27 Lecture Slides , we looked at an implementation of a Queue that was backed by linked Nodes. We also looked at an implementation of a FixedCapacityArrayStack that was backed by a fixed size array.  

For this problem, create a class edu.wpi.cs2223.algorithms.week1.USERID.FixedCapacityArrayQueue that implements the Queue interface using a fixed capacity array as the backing storage.   

Modify this line of QueueTest to instantiate your new FixedCapacityArrayQueue implementation and execute the test.  Do both test methods pass?  If not, go ahead and fix your implementation so that all tests pass.

In the Javadoc of your implementation, answer the following questions:

1. comparing your implementation to the Node backed one we looked at in class, in what way is your implementation better?  In what ways is the Node backed implementation better?
2. what happens to your implementation if we enqueue more elements than the fixed size that the backing array was instantiated with?

Problem Two - ResizingArrayQueue

For this problem, create a class edu.wpi.cs2223.algorithms.week1.USERID.ResizingArrayQueue that implements the Queue interface using arrays whose sizes are adjusted as needed.  That is, start with an array of size 1, but replace it with a larger array as soon as you need to store more than one element.  A reasonable strategy here is to double the backing array size every time you need more storage.

Modify this line of QueueTest to instantiate your new ResizingArrayQueue implementation and execute the test.  Do both test methods pass?  If not, go ahead and fix your implementation so that all tests pass.  The fact that the backing array size is changing should be completely opaque to the client of your Queue implementation - this test included.

In the Javadoc of your implementation, answer the following questions:

1. In terms of N, the number of elements in the queue, what is the worst case number of operations that your implementation needs to perform when enqueue is called? (the operations we are most interested here are array reads and writes, consider each indexed access a single operation)
2. In terms of N, the number of elements in the queue, what is the worst case number of operations that your implementation needs to perform when dequeue is called? (the operations we are most interested here are array reads and writes, consider each indexed access a single operation)
3. In terms of N, the number of elements in the queue, what is the worst case number of operations that your implementation needs to perform when isEmpty is called? (the operations we are most interested here are array reads and writes, consider each indexed access a single operation)
4. To make the tests pass, you had to implement resizing of the backing array in the growing direction - to make room for storing more elements, describe the scenario under which you might want to shrink the size of the backing array.  What would you do to make sure you were not stuck in a growing/shrinking/growing cycle as single elements are added and removed.

Problem Three - TwoQueueStackPushOptimized, constant time push

For this problem, create a class edu.wpi.cs2223.algorithms.week1.USERID.TwoQueueStackPushOptimized that implements the Stack interface. Your implementation should have two member variables that are Queue implementations that we went over in class - LinkedListQueue.  These two queues should be instantiated in your constructor like this (feel free to rename those two member variables to be more descriptive) :

Your task is to implement the Stack interface by only using these two queues (queueOne and queueTwo) to support all of the stack operations.  No other state should be used.  Further, since this is a Push Optimized stack implementation, the push operation should take constant, O(1), time regardless of the size of the stack.  The pop operation is permitted to take more time and depend on N.

Modify this line of SlackTest to instantiate your new TwoQueueStackPushOptimized implementation and execute the test.  All tests should pass.

In the Javadoc of your implementation, answer the following questions:

1. In terms of N, the number of elements in the stack, what is the worst case number of operations that your implementation needs to perform when pop is called? (the operations we are most interested here are queue enqueues and dequeues, consider each one operation)
2. What did you find challenging in making pop work correctly?  Please explain how it works.

Problem Four - TwoQueueStackPopOptimized, constant time pop

For this problem, create a class edu.wpi.cs2223.algorithms.week1.USERID.TwoQueueStackPopOptimized that implements the Stack interface. Your implementation should have two member variables that are Queue implementations that we went over in class.  These two queues should be instantiated in your constructor like this (feel free to rename those two member variables to be more descriptive) :

Your task is to implement the Stack interface by only using these two queues (queueOne and queueTwo) to support all of the stack operations.  No other state should be used.  Further, since this is a Pop Optimized stack implementation, the pop operation should take constant, O(1), time regardless of the size of the stack.  The push operation is permitted to take more time and depend on N.

Modify this line of SlackTest to instantiate your new TwoQueueStackPopOptimized implementation and execute the test.  All tests should pass.

In the Javadoc of your implementation, answer the following questions:

1. In terms of N, the number of elements in the stack, what is the worst case number of operations that your implementation needs to perform when push is called? (the operations we are most interested here are queue enqueues and dequeues, consider each one operation)
2. What did you find challenging in making push work correctly?  Please explain how it works.

Problem Five - CircularLinkedListSurvivor

For this problem, you will implement a game where contestants start by standing in a circle.  Then starting with the head contestant, they count off up to the countPerRound value.  The person who says the positive integer, countPerRound value is eliminated and has to leave the circle.
 
The next round starts with the person right after the one who just got eliminated and once again contestants count up to the countPerRound value and whoever says that value leaves the circle.
 
This goes on for N rounds, where N is the initial number of contestants, until the last person is eliminated.
 
Guarantees:

• countPerRound is a positive integer
• head is the start of a circular linked list
• countPerRound can be smaller, equal to or larger than N (the initial number of contestants)

For example, given the following input linked list

which represents the following circle of contestants :

if countPerRound is 3. The following takes place:

• In round one the counting starts with Bob, the head, and goes Bob: 1, James: 2, Rose: 3.  So Rose is eliminated, and the circle now looks like this:

• Since Sally was the next person after Rose, she starts counting in round two and goes Sally: 1, Bob: 2, James: 3.  So James is eliminated, and the circle now looks like this:

• Since Sally was once again the next person in line, she starts counting in round three and goes Sally: 1, Bob: 2, Sally: 3.  So Sally is eliminated, and the only contestant left is Bob.
• In round 4, Bob is the only one left, he trivially counts to 3 and is the final contestant to be eliminated.  

Based on these results, your implementation should return the following linked list:

For this problem, create a class edu.wpi.cs2223.algorithms.week1.USERID.CircularLinkedListSurvivor. You can start by copying over this boilerplate implementation with a TODO for its core logic.  You can test your progress and final implementation by running CircularLinkedListSurvivorTest.

In the Javadoc of your implementation, answer the following questions:

1. In terms of N, the number of initial contestants, and countPerRound, what is the running time of your implementation?  Consider each linked list next traversal an operation.
2. Using the "think about time complexity - mathematically" strategy we saw in Tuesday 10/24 Lecture Slides starting on slide 25, derive the time complexity of your implementation in a similar way - that is express T(N) in terms of T(N-1) and repeatedly substitute terms until you arrive at a resulting equation.