# 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 `LinkedList`

s.

## 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:

— Constructor that uses the list emptyList passed to it to store the dots for this picture.`Picture(List<Dot> emptyList)`

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

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:

`removeDotsIndex()`

when using a`LinkedList`

.`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 the`LinkedList.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:

- 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?
- 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?
- 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
`ArrayList`

s - 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.