Lab 1: Introduction to Empirical Analysis of Algorithms

Purpose

• To have a deep understanding of iteration and recursion.
• To learn the empirical evaluation of the algorithms

Description

In the class, we have discussed both recursive and iterative algorithms to calculate Fibonacci numbers, and the analyze of their time efficiency. In this lab, you will evaluate the efficiency of both algorithms empirically. You are required to implement both algorithms using C, design an experiment to measure the time overhead of the algorithms, and analyze the experiment results. Here are general steps that you need to perform empirical evaluation of the algorithms.

• Understand both algorithms and the experiment's purpose.
• Decide on the efficiency metrics to be measured. In this lab, you are required to measure the time efficiency in terms of both the number of the basic operations and the real time unit. For example, you can assume the basic operation is addition. To measure the time overhead upto microsecond granularity, you can use gettimeofday(). Use ``man gettimeofday'' to check the mannual of the function.
• Decide on characteristics of the input sample (its range, size and so on), and generate a sample of inputs.
• Write one/two program(s) to implement both algorithms.
• Run the program(s) on the sample's input and record the output. You need to decide on the number of repeated runs of the same program on the same inputs, in order to get more accurate result. You should generate an output file that records the execution results. The output file can be a simple text file in a table format, including the algorithm type, input, output, execution time and number of operations. A sample output will be:

  algtype input output numofops exectime
  1        2      1      1        4

• Visualize the output data and analyze the results. In this lab, you will use ``R'' to generate figures from the measured data. A sample R file can be found here. You can use any editor to write R program. To run R programs, type ``R'' at the terminal, and then type ``source(``R filename'')'' to execute the R program and generate the plots. Type ``q()'' to quit from R program.

Submission

• A hard copy of the source code and output of all your programs. You should use command ``a2ps'' or ``enscript -2rG'' to print them in two columns.
• A hard copy of your lab report written in Latex. It should include the following contents:
  • Section 1 Introduction: a brief description of the problem and the purpose of the lab.
  • Section 2 Implementation: a brief description of how to implement the algorithms to calculate Fibonacci numbers, and how to measure the time overhead.
  • Section 3 Experiment: a detailed description of your experiment setup, performance metrics, sample input, and analysis of experiment result.
  • Section 4 Conclusion

Here is a sample Latex file of the lab report.

Link to this Page

• Lab Handouts & Assignments last edited on 11 April 2008 at 8:44 am by aldenv29.allegheny.edu