GATE CSE 2015 | Set 1 | Question: 42

Question

Consider the following C program segment.

while (first <= last)
{
    if (array[middle] < search)
        first = middle + 1; 
    else if (array[middle] == search)
        found = TRUE;
    else
        last = middle - 1;
    
    middle = (first + last)/2;
}

if (first > last)
    notpresent = TRUE;

The cyclomatic complexity of the program segment is_______________.

Comments

Is this topic out of  syllabus now ??

---

I also want to know, because in my study material it is not there...

Answer 1

Number of predicates $= 4,$ if, else if, while and if.

Cyclomatic complexity $=$ No. of predicates $+ 1 = 5.$

Comments

I think it is a part of software engineering and it is now out of syllabus ?

Right ??

---

Predicate nodes = only statements that have a condition to evaluate (true/false decision).
else is NOT a predicate node. It doesn't make a decision. it's just the default path when all conditions above fail.

---

In a CFG:

- Each statement is a node
- Arrows between them are edges
- Out-degree = number of edges going OUT from a node

A predicate node has out-degree ≥ 2 meaning the flow can go in 2 or more directions based on a condition.

Think about it:

`while(first <= last)` : outdegree = 2 (enter loop OR exit)
`if (array[middle] < search)`: outdegree = 2 (true OR false)
`else if (array[middle] == search)`: outdegree = 2 (true OR false)
`else`: outdegree = 1 (only one path)
`if (first > last)`: outdegree = 2 (true OR false)

So `else` has out-degree 1, there's no decision, the code just flows straight through. That's why it's not a predicate node.

And for the second question, "why is the last `if` included?" it's simply because `if (first > last)` is a decision with two possible outcomes (true or false), regardless of where it appears in the code.

Answer 2

The cyclomatic complexity of a structured program[a] is defined with reference to the control flow graph of the program, a directed graph containing the basic blocks of the program, with an edge between two basic blocks if control may pass from the first to the second. The complexity M is then defined as

    M = E − N + 2P,
where
    E = the number of edges of the graph.
    N = the number of nodes of the graph.
    P = the number of connected components.  

Source: http://en.wikipedia.org/wiki/Cyclomatic_complexity For a single program (or subroutine or method), P is always equal to 1. So a simpler formula for a single subroutine is

    M = E − N + 2 

For the given program, the control flow graph is:

 E = 13, N = 10.

Therefore, E - N + 2 = 5. 

Comments

@ Regina Phalange

Can you please explain how you got this control flow graph?

---

I learnt from this- https://www.youtube.com/watch?v=FOZInDh8Ym0&list=LLzuMhNIxVjHInJfZYcm4EbQ&index=11

---

Thank you.

But Im not getting the graph as you got. Can you name the nodes with variables please?