Property Checking

A property checking problem involves validating whether a given structured input satisfies a particular property. The goal is to verify the input adheres to the property.

Java - Validate binary search tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
boolean isValidBST(TreeNode root) {
  return validate(root, null, null);
}

boolean validate(TreeNode node, Integer min, Integer max) {
  if (node == null) return true;
  if (min != null && node.val <= min) return false;
  if (max != null && node.val >= max) return false;

  return validate(node.left, min, node.val) && 
         validate(node.right, node.val, max);
}

C++ - Check graph connectivity:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
bool isConnected(vector<vector<int>>& graph) {
  vector<bool> visited(graph.size(), false);
  dfs(graph, 0, visited);
  for (bool v : visited) 
    if (!v) return false;
  return true;
}

void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited) {
  visited[node] = true;
  for (int nei : graph[node]) {
    if (!visited[nei])
      dfs(graph, nei, visited);
  }
}

Python - Validate Sudoku board:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def isValidSudoku(board):
  
  rows = [set() for _ in range(9)]
  cols = [set() for _ in range(9)]
  boxes = [set() for _ in range(9)]

  for r in range(9):
    for c in range(9):
      val = board[r][c]
      if val != '.':
        box = r // 3 * 3 + c // 3

        if val in rows[r] or val in cols[c] or val in boxes[box]:
          return False

        rows[r].add(val)
        cols[c].add(val)
        boxes[box].add(val)

  return True

Property checking is fundamental for testing, verification, and validation.

Concept of Property Checking

Property Checking is a technique used in software engineering and formal methods to automatically verify that a program, system, or algorithm meets certain specified properties. These properties could range from functional requirements like “the algorithm should sort an array” to non-functional requirements like “the algorithm should not have memory leaks.” Common methods for property checking include model checking, runtime verification, and static analysis.

This technique is crucial in industries where reliability and correctness are paramount, such as aerospace, automotive, and medical devices.

Example Code

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class PropertyCheck {
  public static boolean isArraySorted(int[] array) {
    for (int i = 1; i < array.length; i++) {
      if (array[i-1] > array[i]) {
        return false;
      }
    }
    return true;
  }

  public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5};
    System.out.println("Is array sorted? " + isArraySorted(array));
  }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>

bool isArraySorted(std::vector<int> array) {
  for (int i = 1; i < array.size(); ++i) {
    if (array[i-1] > array[i]) {
      return false;
    }
  }
  return true;
}

int main() {
  std::vector<int> array = {1, 2, 3, 4, 5};
  std::cout << "Is array sorted? " << std::boolalpha << isArraySorted(array) << std::endl;
  return 0;
}

Python

1
2
3
4
5
6
7
8
def is_array_sorted(array):
  for i in range(1, len(array)):
    if array[i-1] > array[i]:
      return False
  return True

array = [1, 2, 3, 4, 5]
print("Is array sorted?", is_array_sorted(array))

Key Takeaways

Scope: Property checking can be applied to both functional and non-functional requirements.
Techniques: Various methods exist for property checking, including model checking, static analysis, and runtime verification.
Automated Validation: Property checking can often be automated, leading to more robust and reliable systems.
Example Code: Simple property checks, like verifying if an array is sorted, can be implemented easily but provide valuable information about the system’s state.

Understanding the concept of property checking gives you another tool to ensure the correctness and reliability of your code. It’s a foundational aspect of rigorous software engineering practices.