Algorithms and Data Structures 2020

Data Structures

Projects and Exercises

3.2 Projects and Exercises

  3.2.1 Compulsory Assignment
  3.2.2 Exercises

3.2.1 Compulsory Assignment

Problem 3.1 (Experimental Running Time) Compare the running time of LinkedList and ArrayList in Java.

Use the file ArrayListDemo.java as a basis. Compile and run the program, and look at the output as well as the source code. What does this test tell us about the performance of ArrayList?

Modify the program to use LinkedList instead of ArrayList. Compile and run the new version. What does it tell us about the performance of LinkedList? What are the advantages and disadvantages of LinkedList compared to ArrayList?

Modify the programs to initialise a smaller array, maybe about 100 elements, and test both ArrayList and LinkedList. How do the two implementations compare when the list is small?

Review the theoretical properties of LinkedList and ArrayList, and compare your empirical output to the theory. Are the test results reasonable?

When would you prefer to use ArrayList and when would you prefer LinkedList? Try to find example applications where you would recommend one or the other.

Problem 3.2 (Optional) In the above tests, we measured in milliseconds, and mostly only a single operation at a time. This does not always allow us an exact comparison.

There are two things you can do:

1.
Use the java.lang.System.nanoTime() function instead.
2.
Make several, similar operations in sequence, e.g. for instance 100 get() calls on adjacent indices.

Try to modify the test programs, and see if you can learn a bit more about the cases where the first test showed zero milliseconds.

(Remember that we rarely care much about the time of a single operations, but when the same operation is made thousands or millions of times, even a difference of less than a millisecond may matter.)

Problem 3.3 (Hall of Fame) Consider a Computer Game where you are going to implement a Hall of Fame, i.e. a list of, say, the 100 best scores ever achieved. What data structure would you choose? What benefits and disadvantages do you consider to make that choice?

Describe the data structure (do not implement it) with all the operations required in the application. For each operation, consider the following:

1.
How fast/slow is the operation?
2.
When and how often do you expect the operation to be used?

Would your choices change if the number of scores to be stored changes?

3.2.2 Exercises