Lab 3: Connect the Dots Generator Revisited
- Perform algorithmic time complexity analysis on the algorithms
- Conduct benchmarking and analyze the results
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
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
- Benchmark the time required to remove dots from a
LinkedListusing 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
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.
Refactoring Constructors for the
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.,
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.
You must refactor
removeDots() in the
Picture class so that it now accepts
(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
longthat 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.
Results and Discussion
Our goal is to model the growth rates of your program's run time in two scenarios:
removeDotsIndex()when using a
removeDotsIterator()when using a
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.
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
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:
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
- Benchmark lecture/homework implementations of the
- 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
This laboratory assignment was developed by Dr. Chris Taylor.