Lab 3: Connect the Dots Generator Revisited

Learning Outcomes

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:

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:

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:

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:

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:

Example Plot
Figure 1: Example Plot of Two Functions

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:

Acknowledgment

This laboratory assignment was developed by Dr. Chris Taylor.

See your professor's instructions for details on submission guidelines and due dates.