Lab 3: Connect the Dots Generator Revisited

Learning Outcomes

• Perform algorithmic time complexity analysis on the algorithms
• Conduct benchmarking and analyze the results

Overview

This assignment focuses on algorithmic analysis and benchmarking. While you will still need to write and deliver code, the main deliverable is a report analyzing algorithmic time complexity and results of benchmarking experiments. You will update your solution to the previous assignment based on feedback from your instructor and enhance its functionality. The key enhancements will allow you to compare the efficiency of using iterators versus indices when accessing elements in LinkedLists.

Assignment

You will use the functionality developed in lab 2 to complete the following:

• Incorporate feedback from your instructor from lab 2
• Develop a method for removing dots from a Collection<Dot>
• Benchmark the time required to remove dots from a LinkedList using both index and iterator methods
• Perform algorithmic time complexity analysis on the algorithms to remove dots and compare those with your benchmarking data
• Write the results of removing dots to a correctly formatted .dot file

If your program is not able to produce a result similar to the balloon100.dot file when applying 100 as the number of desired dots to the balloon.dot picture, it is not ready to be submitted. You may wish to ask your instructor for help if you get stuck.

Details

Refactoring Constructors for the Picture Class

You must remove all constructors from the Picture class (submitted for lab 2) and implement the following constructors:

• Picture(List<Dot> emptyList) — Constructor that uses the list emptyList passed to it to store the dots for this picture.
• Picture(Picture original, List<Dot> emptyList) — Constructor that copies the dots from original into emptyList and uses it to store the dots for this picture.

These constructors provide flexibility in your Picture class because we can now specify the specific implementation of the List used (e.g., ArrayList, LinkedList, or even our own List implementation) by passing the appropriate list to the constructor. In fact, the Picture class is no longer dependent on any concrete list implementation.

Refactoring removeDots() Method

You must refactor removeDots() in the Picture class so that it now accepts the arguments (int numberDesired, String strategy) and uses the second to determine which of the following two private static methods to call:

• removeDotsIndex(List<Dot> dots, int numberDesired) which should have the functionality that was in the lab 2 implementation of removeDots() but now returns a long that represents the number of nanoseconds required for the algorithm to run.
• removeDotsIterator(Collection<Dot> dots, int numberDesired) that produces the same result as removeDotsIndex() but uses one or more iterators to traverse the collection of dots.

You may find System.nanoTime() and reviewing the code provided in lab 1 useful for this.

Results and Discussion

Our goal is to model the growth rates of your program's run time in two scenarios:

1. removeDotsIndex() when using a LinkedList.
2. removeDotsIterator() when using a LinkedList.

We will approach this both theoretically (big-O analysis) and empirically (benchmarking).

Create a Word document that includes the components described below. Unless otherwise directed by your instructor, place it in your project folder and add it to your repo. Be sure to commit and push it with the rest of your solution to this assignment.

Big-O Analysis

In your report, you must outline your asymptotic time analysis for the above scenarios. Your analysis must include a discussion clearly justifying the \( O( ? ) \) answer for each scenario. Use \( n \) to indicate the number of dots in the list before any are removed.

It may be helpful to review the run times of accessing a single element of LinkedList by calling next() on an iterator and theLinkedList.get(int) method.

Benchmarking

Your must also benchmark your code for each of the above scenarios. In your benchmarks, you will vary the number of dots in the drawings but always remove the same number of dots. This is because we want to assess the impact of a single change at one time.

You have been provided the following files (see the data folder in the project) to use in your benchmarks:

• noisy_circle_125.dot
• noisy_circle_250.dot
• noisy_circle_500.dot
• noisy_circle_1000.dot
• noisy_circle_2500.dot
• noisy_circle_5000.dot
• noisy_circle_7500.dot
• noisy_circle_10000.dot

You should have your program remove 100 dots from each drawing and record the time (in seconds). Note that your program takes input in the form of the number of dots that should remain after the removal. You must calculate the number of remaining dots for each drawing (e.g., 125 - 100 = 25 desired dots) to ensure that only 100 dots are removed.

Graph these data in Excel and compare your plot with your aysmptotic time analysis. You should put the independent variable (number of dots in the drawing) on the horizontal axis and the dependent variable (run time) on vertical axis. Your graph should have appropriate axis labels, a title, and a legend. We graphed idealized linear and quadratic functions below as an example for you to follow:

Interpreting Your Results

In your report, you should answer the following questions:

1. From your benchmarks, the run time of which scenario grows more slowly as \( n \) is increased? The run time of which scenario grows more quickly as \( n \) is increased?
2. From your big-O analysis, the run time of which scenario grows more slowly as \( n \) is increased? The run time of which scenario grows more quickly as \( n \) is increased?
3. Are the results from your benchmarks and big-O analysis consistent?

Just For Fun

Ambitious students may wish to:

• Just for Fun suggestions from lab 2
• Benchmark the two iteration strategies with ArrayLists
• Benchmark lecture/homework implementations of the ArrayList and LinkedList
• Create an interactive game where the user can draw lines between the dots, but only if they select the dots in the right order.
• Graph benchmark result in your UI
• Save dots images as .png images

Acknowledgment

This laboratory assignment was developed by Dr. Chris Taylor.