University of Utah School of Computing
EAE 2420:
Introduction to Computer Science II
Homework 1
Assigned: Monday, August 25, 2014
Due: Monday, September 8, at 9am

Homework 1

Part I: Write a DoublyLinkedList

Your list should contain inner classes private class Node and public class Iterator
Your list should include the following routines:
  • public void insert( AnyType data )
  • public void remove( AnyType data)
  • public int size()
  • public Iterator first()
  • public Iterator last()
  • public Iterator find(AnyType data)
Your Iterator should include the following routines:
  • public bool valid()
  • public void next()
  • public void prev()
  • public AnyType getData()
  • public void remove() // removes "current" from the list
  • public void insert(AnyType data) // inserts after "current"
The list should be generic, so that it can hold any specific type of data.

Part II: In the fireworks simulator, replace the ArrayList of particles with a DoublyLinkedList

This zipfile contains both an action script and java implementation of a fireworks simulator (very kindly provided by Dr. Germain). Modify the fireworks simulator to use your double linked list. You should add a data member for the list and add appropriate calls to use it instead of the ArrayList (be careful to make sure that insertion and removal are O(1) operations). Given Part III, it would probably be a good idea to add a boolean to determine whether you are using the linked list or the array list.

Part III: Compare running times

In this step, you want to compare the running times of the ArrayList and DoublyLinkedList. Which do you think will be faster? Drawing the particles dominates the computation, so to understand how fast the add and delete routines are turn display off by Simulator.DO_NOT_DISPLAY to true. To automatically create fireworks set TEST_FIREWORKS.auto_fire_count to a positive integer. Compare the frames per second and time displayed for various numbers of particles. How many particles are necessary to start seeing a difference (notice that the total number of particles are displayed in the console)? Turn in a table or graph of your results and the answers to these questions as part of your written homework.

Part IV: Artistic Expression

Modify the simulator to do something new. For example, create a new type of firework (e.g. one with a circular explosion), or create a scripted fireworks display (maybe even set to music), or do something else.

Part V: Written Homework

What to hand in

Create a web page for the assignment. Add a description of your program and some screen captures. Use the CADE online handin system to handin your source code. Please zip and handin your entire project directory. Include in this directory/zipfile an "info.txt" file with your name, your CADE username, and the web address of your web page. If you work in a team only one of you need to submit the source code, but both need to make web pages and the info.txt file should include both your information.

Grading

Each homework assignment will receive a grade out of 100 points. This week, the available points will be broken down like so:
  • 40 points: Linked List Implementation
  • 5 points: Integration into the fireworks simulator
  • 10 points: Comments describing the class, each method as well as the interesting pieces of the code itself
  • 10 points: Elegence of programming
  • 10 points: Running time comparison
  • 10 points: Picture and web page
  • 5 points: Written Homework