Statement testing with MS Copilot

Task 1 (student 1)

Using MS Copilot  identify statements for the insertSort function. Assign a tag to for each identified statement.  Present the list of statements with tags. Write the prompt and the chatbot answer. Discuss the result.

Does it properly recognized that the FOR instruction consists of 3 statements? 

The following prompt was used to generate the statement list using MS Copilot:

given a following function in C:

void insertSort(int a[], int length) {
    int i, j, value;
    for (i = 1; i < length; ++i) {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; --j) {
            a[j + 1] = a[j];
        }
        a[j + 1] = value;
     }
}

identify every statement in this function. assign a tag for every statement, then present the list of statements and their respective tags.

It produced the following output:

Below is a breakdown of every executable statement (or control structure) within the function, along with a unique tag for each:

S1 – Variable Declaration

int i, j, value;

This statement declares the loop variables (i and j) and a temporary variable (value) to hold the element currently being inserted.

S2 – Outer For Loop

• for (i = 1; i < length; ++i) {
      ...
  }
  

  This for loop iterates over the indices from 1 to length - 1. The loop treats the subarray a[0..i-1] as already sorted and inserts a[i] into its proper place.

S3 – Current Element Assignment

• value = a[i];
  

Inside the outer loop, this assignment copies the current element (a[i]) into the temporary variable value before shifting sorted elements to make room.

S4 – Inner For Loop

• for (j = i - 1; j >= 0 && a[j] > value; --j) {
      ...
  }
  

This inner loop handles the shifting process. It starts at index i - 1 and checks two conditions—whether j is still within bounds (i.e., j >= 0) and whether a[j] is greater than value. If both conditions hold, it shifts elements one position to the right.

S5 – Element Shifting Assignment

• a[j + 1] = a[j];
  

Within the inner loop, this statement moves the element a[j] one position to the right to open up a slot for value.

S6 – Insertion Assignment

a[j + 1] = value;

After finishing the inner loop (when the correct position is found), this assignment places value into its sorted position.

---

This detailed breakdown connects each code “step” with a corresponding tag, which you can refer to for further discussion or analysis of the algorithm.

If you're curious about further nuances of the insertion sort algorithm or wish to explore alternative sorting techniques with similar step-by-step breakdowns, let me know!

This response correctly identified simple assignment statements. However, it failed to consider that the statements in for loops, while they seem like one, are actually separate statements, executed at different times. This example shows that relying on large language models can, and often will, lead to wrong outcomes, and thus it is required from users that they know at least something in the domain, so that they can spot and correct any errors.

Task 2 (student 2)

Using MS Copilot generate the Control Flow Graph in the DOT language for the insertSort function. Do not force Copilot to create the instruction list. Write the prompt and the chatbot answer. Discuss the result. 

Does the CFG has the same structure as the CFG created by a human in the previous section of the book?

When the Task 1 is finished, use the generated instruction list with tags as the hint for Copilot. Did it help them co correct the CFG (now the CFG should be correct)? Discuss the result.

Prompt: Generate for me Control Flow Graph in the DOT language for the insertSort function from wikipedia.

Answer: Certainly! Below is the Control Flow Graph (CFG) of the insertSort function in the DOT language:

digraph InsertSortCFG {
    entry [label="Entry"];
    exit [label="Exit"];

    entry -> init_i;
    init_i -> cond_i [label="i = 1"];
    cond_i -> exit [label="i >= length"];
    cond_i -> init_value [label="i < length"];

    init_value -> init_j [label="value = a[i]"];
    init_j -> cond_j [label="j = i - 1"];
    cond_j -> assign_a_jp1 [label="a[j + 1] = value"];
    cond_j -> body_j [label="j >= 0 && a[j] > value"];

    body_j -> shift [label="a[j + 1] = a[j]"];
    shift -> update_j;
    update_j -> cond_j [label="j--"];
    
    assign_a_jp1 -> update_i;
    update_i -> cond_i [label="i++"];
}

Comparing the graph to the one created by human, we can see that the chatbot didn't succeed. The structure of the program is more or less correct (the "Shift" node is an anomaly), however the graph itself is not a proper Control Flow Graph.

The graph after chatbot was provided with instruction list with tags from the first Task:

With instruction list provided, the graph is more accurate when it comes to structure, weird "shift" node is gone. It is still not correct Control Flow Graph, node names for example. 

Task 3. (student 3)

Comparing the graph to the one created by human, we can see that the chatbot didn't succeed. The structure of the program is more or less correct (the "Shift" node is an anomaly), however the graph itself is not a proper Control Flow Graph.

Prompt: 

write an instruction test for the function insertSort in the C language. Here is the function:
void insertSort(int a[], int length)
{
int i, j, value;
for (i = 1; i < length; ++i)
{
value = a[i];
for (j = i - 1; j >= 0 && a[j] > value; --j)
{
a[j + 1] = a[j];
}
a[j + 1] = value;
}
}
Keep in mind to precisely test various data types and values, compare them with expected results

Answer:

Sure! Here's an instruction test for the insertSort function in C. This test will cover various data types and values, and compare them with the expected results.

This test function covers various scenarios:

1. A normal case with mixed values.
2. An already sorted array.
3. An array with negative numbers.
4. An array with duplicate values.
5. A single element array.
6. An empty array.

Each test case uses assert to compare the sorted array with the expected result. If all assertions pass, it prints "All test cases passed!" to indicate success.

Summary

Copilot created seperate function for printing array elements, which is good as it provides good code organization. Whole testing takes place in function testInsertSort(). There are 6 cases, including common numbers array, negative numbers array, empty array, sorted array, single element list and array with duplicates.

Running the code revealed an important issue with function:

main.c: In function ‘testInsertSort’:
main.c:77:5: warning: ‘insertSort’ accessing 4 bytes in a region of size 0 [-Wstringop-overflow=]
   77 |     insertSort(arr6, 0);
      |     ^~~~~~~~~~~~~~~~~~~
main.c:77:5: note: referencing argument 1 of type ‘int[0]’
main.c:11:6: note: in a call to function ‘insertSort’
   11 | void insertSort(int a[], int length)
      |      ^~~~~~~~~~
All test cases passed!

It turns out, that when empty array is passed, there is an overflow, as j value is not initialazed it defaults to 0. Then it tries to reach a[1] element of array, which triggers overflow warning. Even though, the code still runs and returns 0.

Copilot failed to test cases with extremely big numbers.