Homework 3: Maze Runner!

This assignment introduces you to linked data structures and abstract data type implementations through building a maze exploration system. You will implement a linked-grid Maze ADT and a circular dynamic Deque, then observe how different data structures affect algorithm behavior.

Important Dates

Motivation for Data Structure Design

Imagine you're developing a pathfinding system for:

• Video game AI that needs to navigate mazes efficiently with limited memory
• Robotics applications where different navigation strategies are needed based on terrain
• GPS systems that must adapt search algorithms based on traffic patterns and route preferences

The choice of underlying data structure dramatically affects performance and behavior. Different auxiliary data structures can lead to entirely different exploration patterns and performance characteristics, even when using identical high-level algorithms.

In this homework, you will implement both array-based and linked-based data structures, then use them to power maze exploration algorithms. You'll discover how subtle changes in data structure choice can produce surprisingly different behaviors despite using the same core logic.

Starter Code

Download the starter code from the following link: hw5.zip.

The starter code is a zip file named hw5-starter.zip. You must unzip this file. After unzipping, you will get a folder called hw5-starter. Open this folder as an IntelliJ project.

Implementation Tasks

1. Maze Testing

Start with this task first! Add comprehensive unit tests to MazeTest.java based on the specifications of the Maze ADT (see src/main/java/hw5/structures/Maze.java).

Key requirements:

• Test all Maze interface methods thoroughly
• Verify boundary conditions and edge cases
• Test neighbor relationships and wall behavior
• Use the provided abstract test structure

2. LinkedMaze Implementation

Complete src/main/java/hw5/structures/LinkedMaze.java, which implements the Maze ADT using a linked list structure where each maze cell contains four pointers to adjacent cells (north, south, east, west).

Key requirements:

• Do not rename any of the provided fields or methods
• Implement efficient O(1) neighbor access through direct pointer navigation
• Ensure bidirectional linking between adjacent cells
• Constructor should run in O(width × height) time with O(1) auxiliary space

3. Deque Testing

Add comprehensive unit tests to DequeTest.java based on the specifications of the Deque ADT (see src/main/java/hw5/structures/Deque.java).

Key requirements:

• Test both front and back operations
• Verify behavior on empty and full deques
• Ensure all operations work correctly in various states

4. ArrayDeque Implementation

Complete src/main/java/hw5/structures/ArrayDeque.java, which implements the Deque ADT using a circular array where all operations must run in constant time (or amortized constant time).

Key requirements:

• Implement circular array with automatic resizing
• All insert related operations must be O(1) amortized time
• Handle wraparound correctly in the circular array
• Resize array when at capacity

5. Queue Adapter Implementation

Complete the implementation of src/main/java/hw5/adapters/DequeQueue.java to implement a Queue ADT using a Deque as the underlying data structure.

Key requirements:

• Use composition to wrap Deque functionality
• Implement FIFO (first-in-first-out) behavior
• Map queue operations to appropriate deque operations

6. Stack Adapter Implementation

Complete the implementation of src/main/java/hw5/adapters/DequeStack.java to implement a Stack ADT using a Deque as the underlying data structure.

Key requirements:

• Use composition to wrap Deque functionality
• Implement LIFO (last-in-first-out) behavior
• Map stack operations to appropriate deque operations

Testing and Analysis

As you implement each data structure, run the provided unit tests to ensure correctness. There are more tests on Gradescope that will run after submission.

Running Integration Tests

After implementing the adapters, run the tests in:

• src/test/java/hw5/adapters/ArrayDequeAdapterTest.java
• src/test/java/hw5/explorers/QueueBasedMazeSearchTest.java
• src/test/java/hw5/explorers/StackBasedMazeSearchTest.java

These tests should pass if you have correctly completed the deque and adapter implementations.

Do not make any changes to the source code in src/main/java/hw5/explorers.

Performance Analysis

In src/main/java/README.md, compare and contrast the time and space complexity of your LinkedMaze implementation against an array-based implementation.

Critical Analysis Task: Consider memory usage and access patterns. Explain when one implementation might be preferred over the other.

Search Algorithm Analysis

Create various mazes, and execute both Stack-based and Queue-based searches. Observe the differences between these search algorithms and report your findings in src/main/java/README.md. Consider these questions in your analysis:

• Which explorer finds shorter paths?
• Which explorer visits fewer cells?
• Which explorer requires less memory space?
• How does maze structure affect each explorer's performance?
• When might you prefer one explorer (stack-based vs queue-based) over another?

Submission

In preparation, you must (1) run checkstyle to ensure your code is checkstyle compliant (if not, fix the styling issues). (2) Create a zip file containing the src folder (and all therein). (3) Submit the zip file to Gradescope.

You can submit as many times as you like until deadline. We will only grade the last submission.

Rubric

Teaching assistants will evaluate your submission using the following criteria:

We reserve the right to change this rubric without advance notice, even after the submission deadline. However, the chances of doing so are slim, and at any rate, should not be a significant change.

• Spec 1: MazeTest contains comprehensive unit tests for the Maze ADT interface, including boundary conditions, neighbor relationships, and wall behavior verification. [2 point]

• Spec 2: LinkedMaze constructor correctly initializes the linked grid structure with proper bidirectional linking between adjacent cells. [1.5 points]

• Spec 3: LinkedMaze.getCell correctly traverses the linked structure to return the cell at the specified coordinates with proper bounds checking. [0.5 point]

• Spec 4: LinkedMaze.getNeighbors correctly returns adjacent non-wall neighbors in the documented order (north, south, east, west) using direct pointer navigation. [1.5 points]

• Spec 5: LinkedMaze.resetVisited correctly traverses the entire linked structure and resets the visited flag for all cells. [0.5 point]

• Spec 6: DequeTest contains comprehensive unit tests for the Deque ADT interface, including front/back operations, capacity management, and edge cases. [3 point]

• Spec 7: ArrayDeque constructor correctly initializes the circular array structure with appropriate default capacity and proper index management. [1 point]

• Spec 8: ArrayDeque.addFirst correctly insert elements at appropriate positions in the circular array and handle wraparound properly. [1.5 points]

• Spec 9: ArrayDeque.addLast correctly insert elements at appropriate positions in the circular array and handle wraparound properly. [1.5 points]

• Spec 10: ArrayDeque.removeFirst correctly remove elements from appropriate positions in the circular array with proper bounds checking. [1.5 points]

• Spec 11: ArrayDeque.removeLast correctly remove elements from appropriate positions in the circular array with proper bounds checking. [1.5 points]

• Spec 12: ArrayDeque correctly implements automatic resizing when deque is full, maintaining element order and circular array properties. [1 points]

• Spec 13: DequeQueue correctly implements Queue interface using Deque composition, providing proper FIFO behavior through appropriate method mapping. [1 point]

• Spec 14: DequeStack correctly implements Stack interface using Deque composition, providing proper LIFO behavior through appropriate method mapping. [1 point]

• Spec 15: Performance analysis in README.md provides a thorough comparison of LinkedMaze vs ArrayMaze implementations, discussing time complexity, space complexity, and practical performance considerations. [1.5 points]

• Spec 16: Search algorithm analysis in README.md compares stack-based vs queue-based maze exploration, explaining behavioral differences and providing insights about when each approach is preferable. [2.5 points]

• Spec 17: The code exhibits good programming style, including proper encapsulation, appropriate method organization, and adherence to provided constraints (e.g., not modifying provided fields/methods). Code is modularized and no operation is longer than 20 lines. [1 point]

The total score for this homework is 24 points.