Algorithms and Data Structures 2020

Week 2. 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?

It is possible that the program runs out of memory. In that case you may have to increase the heap size with an option to JVM.

1.
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?
2.
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?
3.
Try with some different list sizes to see how the run time developes. Which operations run in constant time? Linear time? Slower than linear?
4.
Review the theoretical properties of LinkedList and ArrayList, and compare your empirical output to the theory. Are the test results reasonable?
5.
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 (Based on Goorich et al C-3.20) Suppose you are making a multiplayer game with n 1000 players, numbered from 1 to n, interacting in an enchanted forest. The winner is the player who first meets every other player. The game is constructed so that a function, meet(i,j) is called every time player i meets player j,

Design the algorithm to be implemented in meet, so that it records who has met whom, and reliably detects when someone has won (i.e. has met every other player).

You should also make an init() algorithm to initialise the data structure used by meet(i,j).

1.
Can you demonstrate that the algorithm is correct?
2.
What is the time complexity?
3.
Is it possible to make it faster?

Hint. You may have to record both whether or not i and J have met, and how many players i has met.

3.2.2 Exercises

Problem 3.4 (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?

Problem 3.5 (Based on Goorich et al C-3.19)

Design an algorithm, shuffle, which takes a list A with n elements and reorders it such that every permutation is equally likely. Assume that you have a function random(n) to return a random integer in the range 0, 1,,n 1.

1.
What is the running time (complexity) of your algorithm?
2.
Is it possible to solve the problem in linear time?
3.
Is it best to use ArrayList or LinkedList as input and output? Why?

Problem 3.6 Goodrich et al C-3.22–23. Comment on the run time complexity for your solutions.

Problem 3.7 Goodrich et al C-3.24. Comment on the run time complexity for your solutions.

Problem 3.8 Goodrich et al C-3.25.

Comment on the run time complexity for your solution.