CPE 103 Lab

Simple Algorithm Timing Study

Learn how to do timing studies to evaluate run time performance of algorithms.
Develop an intuitive sense for how long an algorithm will execute.

Finding Java system time

To compute "wall clock" execution time of a code segment, we need to get the current system time at the start of the segment (let's call it startTime), then get the current system time at the end of the segment (let's call it endTime). The running time of the segment will be the value of endTime - startTime. To obtain the current system time, we use
long startTime = System.currentTimeMillis();method of the System class located in java.lang library (no need to import). This method returns the current system time in milliseconds from midnight, 01/01/1970.

Part 1

Your objective is to write a program that takes five seconds to execute.

1. Study the algorithm below to learn what it does and how it works.

Pseudocode for timing a list building algorithm.

DECLARE a generic ArrayList of Strings 
     
Prompt the user for the number of words to put in the list
Obtain number of words from user

WHILE number of words >  zero

    SET starttime to System.currentTimeMillis()
    Construct the list

    LOOP for number of words to put in list

         Reset current word to empty
         LOOP to create a word of 20 random letters
               get a random letter using (char)( 'A' + ((int) (26 * Math.random() ))) ;
               add the letter to the current word
         END LOOP

         add the word to the list

    END LOOP

    SET endtime to System.currentTimeMillis()

    Compute and display elapsed time in milliseconds
    Display the last word in the list

    Prompt the user for the number of words to put in the list
    Obtain number of words from user

END WHILE

2. Implement the algorithm above in Java.
3. When the program is running correctly, experiment with your program to determine how many words are needed in the list in order to cause the program to require five seconds to execute. Fill in the table below with your results.
(You may copy it to a word processor).

Be sure to run the program at least 5 times with each data value to be sure you have consistent results.
Note: it's difficult to get EXACT results, and accuracy isn't important for this lab. Just get somewhere roughly between 4.5 - 5.5 seconds.

Part 2

Create an experiment to answer the two questions below.

a. Approximately how many words you can put in the list (above) before you get an OutOfMemoryError?

b. Given the largest list you can build with available memory, how long does it take to do a linear (sequential) search for an item not present in the list?
(If you skipped part (a) use 10 million items).

Fill in your answers in the worksheet below. (You may copy it to a word processor).

Submit printouts of your worksheet and your source code at the next class meeting.

Algorithm Timing
Lab Worksheet
Student 1 ____________________
Student 2 ____________________

Part 1

Trial #	list size	milliseconds
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Part 2

a) ____________ words in the list when it runs out of memory.

b) ____________ seconds for a linear search of a list of size _________.