Based On The Program Above, Please Draw A Control Flow Graph ✓ Solved

Based on the program above, please draw a control flow graph

1. Based on the program above, please draw a control flow graph for it. Hint: Annotating some statements or conditions on nodes/edges will be very helpful.

2. In your control flow graph, what are the test requirements for edge coverage?

3. List test path(s) that achieves the edge coverage.

4. Provide test cases for each test path you list in the previous question. If it is not possible to find the test input for certain test path, describe the reason.

Hint: Not providing expected outputs will get 2 points deduction. Not matching test paths with their corresponding input/output will get 3 points deduction.

5. In your control flow graph, what are the test requirements for edge-pair coverage?

6. List test paths that achieve the edge-pair coverage.

7. Provide test cases for each test path you list in the previous question. If it is not possible to find the test input for certain test path, describe the reason.

Paper For Above Instructions

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The process is repeated until no swaps are needed, which means the array is sorted. The given program defines the bubble sort algorithm in Java, and from this, we can derive a control flow graph (CFG) which will help in understanding the flow of execution and testing requirements.

Control Flow Graph (CFG)

The control flow graph for the bubble sort program can be drawn by identifying key points of interest in the program. Here's how it looks conceptually:

  • Start Node
  • Node representing the length of the array.
  • Entry point into the outer loop (i)
  • Entry point into the inner loop (j)
  • Condition to check if arr[j - 1] > arr[j]
  • Node representing the swap operation.
  • Exit point from the inner loop.
  • Exit point from the outer loop.
  • End Node

Each node represents a point in the program where control can branch or change direction depending on conditions evaluated (like whether to swap elements). Edges will connect nodes based on the flow of execution.

Test Requirements for Edge Coverage

For edge coverage, we need to cover all edges in the control flow graph. This means we need to ensure that:

  • All paths through the inner and outer loops are executed.
  • All conditional checks (like comparisons) in the loops are evaluated both to true and false.

Test Paths for Edge Coverage

  • Path 1: Start -> Length Node -> Outer Loop (i=0) -> Inner Loop (j=1) -> Swap Node (if condition true) -> Inner Loop Exit -> Outer Loop Next Iteration.
  • Path 2: Start -> Length Node -> Outer Loop (i=0) -> Inner Loop (j=1) -> No Swap (if condition false) -> Inner Loop Exit -> Outer Loop Next Iteration.
  • Path 3: Repeat the above steps for i > 0 until the array is sorted.

Test Cases for Each Test Path

Here are potential test cases based on identified test paths for edge coverage:

  • Test Case for Path 1: Input: [5, 3, 4, 2, 1]. Expected Output: [1, 2, 3, 4, 5] – This path will execute the swap operation.
  • Test Case for Path 2: Input: [1, 2, 3, 4, 5]. Expected Output: [1, 2, 3, 4, 5] – No swaps occur since the array is already sorted.

Test Requirements for Edge-Pair Coverage

Edge-pair coverage means each pair of edges in the control flow graph should be covered by at least one test case. For the bubble sort algorithm, the pairs of edges to be covered include:

  • Transition from initializing the outer loop to the entry of the inner loop.
  • Transition from evaluating the condition to executing the swap or skipping it.
  • Transition from the inner loop exit back to the outer loop to process the next element.

Test Paths for Edge-Pair Coverage

  • Path A: Start -> Length Node -> Outer Loop -> Inner Loop -> Condition Check -> Swap Node -> Inner Loop Exit -> Outer Loop Next Iteration.
  • Path B: Start -> Length Node -> Outer Loop -> Inner Loop -> Condition Check -> No Swap Node -> Inner Loop Exit -> Outer Loop Next Iteration.

Test Cases for Edge-Pair Coverage

The following test cases can be created to cover the identified edge pairs:

  • Test Case for Path A: Input: [4, 3, 2, 1]. Expected Output: [1, 2, 3, 4] – This will create a scenario where swaps are consistently made.
  • Test Case for Path B: Input: [1, 2, 3]. Expected Output: [1, 2, 3] – This tests the scenario where no swaps are necessary.

Conclusion

Through the analysis of the bubble sort algorithm, we've constructed a control flow graph to identify the various paths through the program. We established the requirements for edge coverage and edge-pair coverage and provided test cases for these paths. This approach ensures comprehensive testing of the bubble sort function, helping to validate that it behaves correctly under different conditions.

References

  • Weiss, S. (2013). Data Structures and Algorithm Analysis in C++. Pearson Education.
  • Knuth, D. E. (1997). The Art of Computer Programming. Addison-Wesley.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
  • Wegner, P. (1988). Support for Program Testing and Debugging. IEEE Transactions on Software Engineering, 14(9).
  • Myers, G. J. (2011). The Art of Software Testing. Wiley.
  • Junit. (2023). https://junit.org/junit5/
  • Freeman, S., & Pryce, N. (2009). Growing Object-Oriented Software, Guided by Tests. Addison-Wesley.
  • Pressman, R. S. (2014). Software Engineering: A Practitioner’s Approach. McGraw-Hill.
  • Beck, K., & Anderson, R. (2004). Extreme Programming Explained: Embrace Change. Addison-Wesley.
  • IEEE. (2020). IEEE Standard for Software and System Test Documentation. IEEE Std 829-2008.

Related Assignments