COMP114 - Experimental Methods in Computing

There are three lectures each week, taking place at the following times

The first lecture will take place on Monday 7th February (Note: 2nd week of semester)

A provisional allocation to each of the two groups may be found via the links below:

Please check which group you have been assigned to and, if you have compelling reasons as to why the time is unsuitable, contact me (by e-mail) describing what these are.

Aims

1. To introduce the role and significance of empirical approaches within Computer Science.
2. To make clear the distinction between applying such techniques in order to test software solutions for correctness and their use in evaluating a solution s performance.
3. To instil an awareness of those parameters affecting the design and quality of experimental data in evaluating algorithmic solutions.
4. To provide a knowledge of typical methods for generating data used in experimental studies in Computer Science.
5. To equip students with the ability critically to analyse and assess results derived from experimental studies in Computing contexts.
6. To provide practical experience in the use of empirical methods in evaluating software solutions.

Learning outcomes

1. Be aware of the different areas within Computer Science for which experimental methods have relevance.
2. Be able to distinguish the use of experimental methods for testing and evaluation.
3. Have an understanding of the factors involved in constructing experiment settings.
4. Be capable of selecting and applying appropriate experimental methods in a variety of contexts from Computer Science.
5. Be able objectively to assess, analyse, and present empirically derived results.

Syllabus

Introduction: Underlying motivations for use of experimental approaches in C.S., e.g. difficulty of obtaining formal analytic demonstrations of system properties; traditional application: software testing, system performance tuning, simulation studies in the physical sciences. Recent developments: algorithm engineering, evaluation of heuristic techniques in AI domains; simulation studies of emerging paradigms, e.g. ANN, Belief Network,; large-scale MAS applications, e.g. eauctions, resource and task allocations. (4 lectures)

Methodologies Focus and aims: distinguishing differing needs of testing correctness and evaluating qualitative or performance aspects. The (Hypothesis Sample Data selection Experiment Analysis of results) cycle. (3 lectures).

Experiment Design: What is an experiment? Population and sampling, Exploratory Data Analysis, statistical analysis (statistical variables, confidence levels, hypotheses testing), t test, Chi-square test. Limits of statistical approaches. (7 lectures)

Selection of Sample Data: Advantages and problems in using randomly generated data; Impact of random distribution properties in terms of experimental results; importance of motivating choice of distribution in reporting such. Review of standard approaches to random generation of widely used structures in algorithmic solutions: permutations and combinations, graphs, propositional formulae. Producing genuinely random data: bits and numbers. Selecting input size range and number of trials. (6 lectures)

Assessment, Analysis, and Presentation (4 lectures)

Example Application Studies:

1. Introduction
2. Methodologies
3. Experiment Design
4. Selection of Random Data
5. Analysis and Presentation

1. Monte Carlo Methods (due: 04/03/2011) (10%)
2. Using t-tests (due: 25/03/2011) (20%)
3. Binary Tree Properties (due 06/05/2011) (30%)
4. Phase Transitions (due: 20/05/2011) (40%)

1. 1st Assignment Feedback and Mark Breakdown(html)
2. 2nd Assignment Feedback and Mark Breakdown(html)
3. 3rd Assignment Feedback and Mark Breakdown(html)
4. 4th Assignment Feedback and Mark Breakdown(html)

• Real Function source for Assessment 1
• 2-CNF Class (java source) Assessment 4
• gnuplot script for Assessment 4
• AntiVirusPerformanceData.class used in Assessment 2.
• BasicStats.class Basic Statistics methods
• BasicStats.java Basic Statistics methods
• BinaryTree.class The Binary Tree class realisation (for Assessment 3).
• BinaryTree.java The Binary Tree class realisation (source code) (for Assessment 3).
• RandomTrees.class Three Random Binary Tree methods (Assessment 3) (compiled code).
• RandomTrees.java Three Random Binary Tree methods (Assessment 3) (source code).
• Java applet for computing t-test values (Assessment 2)