Computer Science 501
Data Structures and Algorithm Analysis

Fall 2014, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

This lab approaches analysis of algorithms from both the theoretical and empirical perspectives. The theoretical questions in the lecture assignment and problem set portions of the lab, will give you a chance to practice with the analysis tools we have considered in class. In the empirical study, you will use the timing code you developed last week to generate tabular and graphical format data, and see if you can match your results to the theoretical expectations.

You may work individually or in a group of 2 or 3 on this lab, but it is essential that each individual understands how to do the lecture assignment and problem set questions, as exam questions will be very similar. As you know, exams are not group efforts.

Getting Set Up

Create a document where you will record your answers to the lecture assignment and lab questions. If you use plain text, call it "lab4.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab4.pdf" before you submit it.

Lecture Assignment Questions

We will usually discuss these questions at the start of class on the lab due date, so no credit can be earned for late submissions of lecture assignment questions.

Problem Set Problems

See the PDF version of this document for a more readable version of this part of the assignment, as the HTML rendering of these kinds of equations is poor and improving it is more trouble than it's worth.

1. 5n² + 2n + 5 and n²
2. nlogn and n²
3. 2^logn and n
4. 2ⁿ and 2²ⁿ

1. n in Omega(logn)
2. 5n + 6 in Theta(n)
3. n logn in Omega(n)
4. n in Theta(n - n^(1)/(2))

1. 762n² - 56n + 37
2. (n³ + 100)⁵
3. 2ⁿ + n²

for ( i = 1; i <= n; i++ )
    for ( j = 1; j <= n; j++ ) {
        for ( k = 1; k <= Math.pow(2,j); k++ ) {
             System.out.println("hello");
        }
        System.out.println("hello");
    } 

Note: you may test your formula by implementing this code and then running it for different values of n.

Empirical Analysis Study

Last week, you developed one or more Java classes capable of measuring the time taken for a variety of experiments. Please refer back to that lab description for the list of experiments.

Your first task is to run your program(s) repeatedly (likely thousands of times) to generate a set of timing data.

• For each experiment, you will need to run instances for a range of problem sizes. Powers of 2 are often a good choice. Be sure to include large problem sizes where running times do not make this prohibitively expensive.
• Choose the number of times to run the for loop within a given instance of an experiment so that the minimum time between starting and stopping the timer is at least, say, 10 milliseconds, but that the maximum time is not more than a few seconds.
• Run each problem size several times (at least 10) and use the minimum time you observe in each case for the results you present.
• To minimize the chance that compiler optimizations, especially Java's "just in time" run-time optimizer, do not taint your results, run the Java Virtual Machine with flags that disable this. For Java/Oracle JVMs, adding the -Xint to your Java command line will disable the JIT compiler.

Your second task is to gather your results into both tabular and graphical formats. You might use familiar tools such as a spreadsheet program for this, but I encourage you to look into gnuplot, which is a free data plotting program available for most platforms. It is installed on mogul, and an example of how to use it is available there in /home/shared/gnuplotexample.

Your final task is to present your results for each experiment. Before addressing the individual experiments, write an introductory paragraph describing the overall approach, including as many details about your test environment as you can (include Java version and any options used when running, operating system version, CPU configuration (number of cores, chips), architecture, and speed, and memory size at a minimum, but also things like cache sizes if you can find them).

Then for each experiment, include the following:

• A restatement the theoretical expectation for the efficiency (e.g., O(n²)) that you gave for last week.
• A presentation of your timing results in tabular and graph formats.
• A comparison of your timing results with the theoretical expectation, explaining any discrepencies to the best of your ability.

Submitting

Before 6:00 PM, Tuesday, September 23, 2014, submit your lab for grading. There are two things you need to do to complete the submission: (i) Copy your file with the answers to the lecture assignment and lab questions into your project directory. Be sure to use the correct file name. If you prepared your answers in Word, export to a PDF file and submit that. (ii) Upload a copy of your lab (a .7z or .zip file containing your project directory) using Submission Box under assignment "Lab4".

Grading

This assignment is worth 75 points, which are distributed as follows: