Homework 3: Simple Algorithms!

This assignment introduces you to fundamental sorting and searching algorithms through hands-on implementation and analysis.

Important Dates

Motivation for Algorithm Optimization

Imagine you're developing a social media platform that needs to:

• Sort thousands of posts by timestamp for user feeds
• Search through friend lists efficiently when people frequently access the same contacts
• Handle real-time data where some operations are more expensive than others

Raw algorithmic implementations often work, but optimized versions can make the difference between a responsive application and one that users abandon. Sometimes a simple optimization like "early termination" or "move-to-front search" can transform performance from unusable to excellent.

In this homework, you will implement several classic sorting algorithms with optimizations, along with search heuristics that adapt to usage patterns.

Starter Code

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

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

Algorithm Implementation Tasks

1. Performance Testing

Start with this task first! Add comprehensive unit tests to PerformanceMonitorTest.java for:

• SortableArrayList
• SortableLinkedList
• ArrayBag
• LinkedListBag

A few example tests are already provided to guide your implementation.

2. Sortable Linked List Implementation

Implement the operations of SortableLinkedList class. This provides a linked list-based data structure that can be sorted using position-based sorting algorithms.

Key requirements:

• Do not change the provided fields or the nested LinkPosition class
• Highly advisable to carefully study SortableArrayList before starting this
• Implement all methods including the iterator

3. Optimized Bubble Sort

Implement OptimizedBubbleSort with the early termination optimization. This improvement allows the algorithm to detect when the list becomes sorted and terminate early.

Key requirements:

• Must implement early termination optimization
• Highly advisable to carefully study BubbleSort before starting this
• Best-case time complexity should improve from O(n²) to O(n)

4. Binary Insertion Sort

Implement BinaryInsertionSort that uses binary search to find the optimal insertion position for each element during insertion sort.

Key requirements:

• This is an optimization that uses binary search to find the insertion position for each element
• Make use of helper methods as needed so your code is clean and readable
• Highly advisable to carefully study InsertionSort before starting this

5. ArrayBag Search Optimization

The contains method of ArrayBag with the transpose sequential search optimization:

• Implement compare and transpose operations.
• Implement contains method
  • Make use of the compare and transpose operations.
  • It must implement transpose sequential search optimization.
• Do not change the provided fields and methods

6. LinkedListBag Search Optimization

The contains method of LinkedListBag with the move-to-front search optimization:

• Implement compare and mveToFront operations.
• Implement contains method
  • Make use of the compare and moveToFront operations.
  • It must implement move-to-front search optimization
• Do not change the provided fields and methods

Testing and Analysis

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

Running the Sorting Demo

After implementing the sorting algorithms, run SortingDemo.java to see how your algorithms perform on different types of input data.

Performance Analysis with SortingDriver

Run SortingDriver.java for comprehensive performance testing. This class runs sorting algorithms on various benchmark datasets and measures their efficiency.

Critical Analysis Task: Compare the measurements printed to the terminal with your expectations based on theoretical time complexities. You must document in README.md at least one case where the metrics do not align with expectations, and provide a hypothesis for why this discrepancy occurs.

Debugging Hint: Use the debugger to step through the code and observe what happens as the algorithm runs on the problematic dataset.

Search Optimization Analysis

After implementing the search optimizations, run SearchDemo.java to observe the search algorithms in action.

In your README.md, explain when one might see performance improvements using the optimized search methods in ArrayBag and LinkedListBag. Provide a concrete example of a scenario where these optimizations would be beneficial.

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:

Please note, 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: PerformanceMonitorTest contains comprehensive unit tests for SortableArrayList performance monitoring, including comparisons, swaps, and counter reset functionality. [1 point]

• Spec 2: PerformanceMonitorTest contains comprehensive unit tests for SortableLinkedList performance monitoring, including comparisons, swaps, and counter reset functionality. [1 point]

• Spec 3: PerformanceMonitorTest contains comprehensive unit tests for ArrayBag performance monitoring, including comparison tracking and transpose optimization verification. [1 point]

• Spec 4: PerformanceMonitorTest contains comprehensive unit tests for LinkedListBag performance monitoring, including comparison tracking and move-to-front optimization verification. [1 point]

• Spec 5: SortableLinkedList constructor correctly initializes the linked list structure with a sentinel node and proper linking. [1 point]

• Spec 6: SortableLinkedList.compare method correctly compares elements and accurately tracks comparison count in the performance monitor. [1 point]

• Spec 7: SortableLinkedList.swap method correctly swaps element data and accurately tracks modification count in the performance monitor. [1 point]

• Spec 8: SortableLinkedList.getPosition correctly traverses the linked list to return the position at the given index with proper bounds checking. [1 point]

• Spec 9: SortableLinkedList iterator correctly traverses all positions in order and implements proper hasNext and next functionality. [1 point]

• Spec 10: OptimizedBubbleSort.sort correctly implements bubble sort with early termination optimization that stops when no swaps occur during a pass. [2 points]

• Spec 11: BinaryInsertionSort.sort correctly implements insertion sort using binary search to find insertion positions, reducing comparisons from O(n) to O(log n) per insertion. [2.5 points]

• Spec 12: ArrayBag.contains correctly implements transpose sequential search optimization: when an element is found, it swaps with its immediate predecessor (unless already at position 0). [1.5 points]

• Spec 13: ArrayBag.contains correctly tracks comparison and modification counts in the performance monitor during search operations. [1 point]

• Spec 14: LinkedListBag.contains correctly implements move-to-front search optimization: when an element is found, it moves to the front of the list. [1.5 points]

• Spec 15: LinkedListBag.contains correctly tracks comparison and modification counts in the performance monitor during search operations. [1 point]

• Spec 16: Performance analysis in README.md identifies and explains at least one discrepancy between expected theoretical performance and actual measurements from SortingDriver, with a reasonable hypothesis for the cause. [2 points]

• Spec 17: Search optimization analysis in README.md explains when the optimized search methods in ArrayBag and LinkedListBag would provide performance improvements, with concrete examples of beneficial scenarios. [1.5 point]

• Spec 18: The code exhibits good programming style, including proper encapsulation, appropriate method organization, and adherence to provided constraints (e.g., not modifying provided fields/methods). [1 point]

The total score for this homework is 23 points.