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 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 ofremoveDots()
but now returns along
that represents the number of nanoseconds required for the algorithm to run.removeDotsIterator(Collection<Dot> dots, int numberDesired)
that produces the same result asremoveDotsIndex()
but uses one or more iterators to traverse the collection of dots.
You may find System.nanoTime() 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 aLinkedList
.removeDotsIterator()
when using aLinkedList
.
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:
- 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
andLinkedList
- 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.