Data Structures & Algorithms Lecture Notes

26 September 2010 • Reproducing Code

Outline

Background
Question
Experiment
Results
Comments

Background

CS 305 and 503 students are encouraged to form study groups.
- In particular, students are encouraged to exchange and test each other’s programs, revising their programs as suggested by their partner’s tests.
A Student’s work is assumed to be a entirely product of their own efforts.
- Cheating occurs when that assumption fails.

Quandry

Is it possible to analyze somebody else’s program and then revise your own without cheating?
Yes: Bring to your work only the things you can remember about somebody else’s work.
Learning: stuffing things in your head so you can pull them out later and use them.

Question

Is it possible to remember enough of a program to be able to reproduce it with high fidelity?
Hyphothesis: in general, no.
Justification:
- There’s too much detail for (most) human memory to take in.
- Understanding and exploiting detail is important; high-fidelity recall is not.

Experiment Protocol

Set up (each step given 5 minutes):
1. Two people each write a binary-search program.
2. Each person analyzes the other’s program for correctness.
3. Each person explains their analysis to the other (5 min × 2).
4. Each person rewrites their program.
How similar is each person’s rewritten program to the other person’s original program?

Experiment Illustrated

analysis schematic

How similar is each person’s second (post analysis, rewritten) program to the other person’s first (pre analysis, original) program?

Sample 1

public static bsearch(int a[], int x)
{
  for (int i, i ≤ a.length, i++)
  {
    if (a[i] = x)
      return i;
  }
    return -1
}

int bsearch(int a[], int x) {
  for (int i = 0; i ≤ a.length; i++) {
    if (a[i] = x)
      return i;
  }
  i = -1;
  return i;
  }

public static bsearch(int a[], int x)
{
  for (int i, i ≤ a.length; i++)
  {
    if (a[i] = x)
      return i
  }
  return -1
}

int bsearch(int a[], int x) {
  for (int i = 0; i ≤ a.length; i++) {
    if (a[i] = x)
      return i;
  }
  i = -1;
  return i;

unchanged

Sample 2

int bsearch(int a[], int x)
{
  for (int i = 0, i < a.length; i++)
  {
    if (a[i] == x)
      return i;
  }
  return -1;
}

int bsearch(int a[], int x)
  for i = 0, i ≤ a.length - 1, i++
    if a[i] = x
      return i
    else a[i] != x
      return -1

int bsearch(int a[], int x)
{
  for (int i = 0; i < a.length; i++)
  {
    if (a[i] == x)
      return i;
  }
  return -1;
}

int bsearch(int a[], int x)
{
  for (i = 0; i ≤ a.length - 1; i++)
  {
    if (a[i] == x)
    {
      return i;
    }
    return -1;
  }
}

unchanged

different

Sample 3

int search(int array[], int x)
  if (array[i] = x)
    return i;
  else if (array[i] =! x)
    return -1;

int bsearch(int a[], int x);
  if (a[i] = x)
    return i;
  else
    return -1;

int search(int a[], int x)
  if (a[i] = x)
    return i;
  else if (a[i] =! x)
    return -1;
  else
    return -1;

int bsearch(int a[], int x)
  if (a[i] = x)
    return i;
  if (a[i] != x)
    return -1;

different

Sample 4

public int searchX(int a[], int x) [
int val = -1;
   for (int i = 0; i ≤ a.length; i++) [
    if (a[i] == x)
      val = i;
    ]
  return val; ]

for (int = i, i ≤ a.length, i++)
  if (int a[] int x) {
    return i;
  else
    return -1;
  }

public int searchX(int a[], int x) {
int val = -1;
  for (int i = 0; i ≤ a.length; i++) {
    if (a[i] == x)
      val = i;
    }
  return val;
}

for (int i = 0, i ≤ a.length, i++) {
  if (int i == x) {
    return value i;
    }
  return value -1;
  }

different

Sample 5

public int bSearch(int a[], int x) {
  for (int i = 0; i < a[].length; i++) {
    if (a[i] = x)
      return i;
    else
      i++;
    if (x =! a[])
      return -1
    }
}

int bsearch(int a[], int x);
  if (
  return i;
  else
    return -1;

int bSearch(int x[], int x) {
for (int i = 0; i < a[].length; i++) {
  if (a[i] = x)
    return i;
  else
    i++;
  }
    return -1;
}

int bsearch(int a[], int x);
  for (i = 0; i++; x)
    if (
      return i;

different

Sample 6

int bsearch(int [] a, int x) {
// assume sorted ascending
  for (i = 0; i < a.length -1; i++)
  {
    if (a[i] == x)
      return i
    else
      if (a[i] > x)
        return -1;
  }
    return -1;
}

binary search:
  int a[], int x, int i;
    if a[] = x
    return z;
      if x != 0
    return -1

int bsearch(int a[], int x)
{
  // assume a[] is sorted ascending
  for (i = 0; i < a.length -1 ; i++)
  {
    if (a[i] == x)
      return i
    else {
      if (a[i] > x)
        return -1; }
  }
  return -1;
}

int binary(int a[], int x);
{
  for (i = 0, i > 0, i++)
    { if a[] == x
        return x
      else
        a[] > x
        return -1
                 }
      return -1
    }

Sample 7

int search(array [], int x) {
  int length = array.length;
  for (int i = 0; i < length; ++i)
    if length[i] == x
      return i;
    else
      return -1;
  }

int bsearch(int a[], int i) {
  if (x == a[i])
    return i;
  else
    { i = -1;
      return i; }
                 }

int public search(array [], int x) {
  int length = array.length;
  for (int i = 0; i < length; ++i) {
    if (length ≥ 0) {
      if array[i] == x;
        return i;
      else
        return -1;
    }
    else
      return "empty array";
  }
}

int bsearch(int a[], int z) {
  int length = array.length;
  for (int i = 0; i < length, i++) {
    if (x == a[i])
      return i;
    if (a[i] == null)
      return -1;
    else
      return -1; }
                  }

different

Results

None of the revised programs were close to the partner’s original program.
There is little danger of being accused of cheating, at least for these results.
There are all sorts of threats to validity, particularly time pressure.

Other Observations

Of the 14 programs written,
- All were linear search; no programs implemented binary search.
- 13 programs were incorrect and one program worked.

	P1	P2	P3	P4	P5	P6	P7	P8	P9	P10	P11	P12	P13	P14
Q 1
Q 2
Q 3

Error Counts

Error Count

non-looping code* 5

indexing exception 4

uninitialized index 3

truncated iterations 3

wrong return value 1

early termination 1

skipping elements 1

Revised program counts, except *: 5 original, 1 revised.

Error		Count
non-looping code*		5
indexing exception		4
uninitialized index		3
truncated iterations		3
wrong return value		1
early termination		1
skipping elements		1

Fence-Post Errors

Looking at too many elements.

for (int i = 0; i ≤ a.length; i++)
  if (a[i] == x) ...

Looking at too few elements.

for (int i = 0; i < a.length - 1; i++)
  if (a[i] == x) ...

Summary

The experiment supports the claim that it’s unlikely that humans can remember enough detail to reproduce a program with high fidelity.
The objective is to understand, not to reproduce.
Pick the most tenacious study partner you can find, then don’t trust them.
- If you can’t find a tenacious one, find a smart one.