Study guide

10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof

Praxis Computer Science 5652

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode

1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy

2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects

2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations

3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security

3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage

4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation

4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing

5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization

5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range

6 Chapter 6: Algorithms: Searching, Sorting, and Recursion

6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents

7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions

7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra

8 Chapter 8: Programming: Selection, Iteration, and Writing Code

8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code

9 Chapter 9: Programming: Procedures, Arrays, and Data Structures

9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)

10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality

10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback

11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs

11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs

12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design

12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding

13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption

13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs

14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection

14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing

15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments

15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored

16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity

16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs

10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof

Key Takeaways Explain This Topic AI

A precondition states what must be true before a procedure is called, such as "n is a positive integer" or "the array is sorted"; the caller is responsible for meeting it.

A postcondition states what a procedure guarantees when it finishes, provided its preconditions held, such as "returns the largest value in the array."

A loop invariant is a condition that is true before and after every iteration; in a find-the-maximum loop, max is always the largest value examined so far.

Testing (empirical evidence) can reveal bugs but cannot prove their absence, because it checks only some inputs; a proof establishes correctness for all valid inputs.

To compare two code segments, check whether they produce the same result for every valid input, especially boundary cases, and then compare efficiency and clarity.

Last updated: September 2026

What this competency asks

ETS asks you to understand how to analyze computer programs in terms of correctness :

Trace code and indicate the output printed or the value of variables after execution.

Indicate the inputs that produce given outputs for a code segment.

Describe what a program does, or choose the code segment that correctly implements an intended purpose.

Identify valid preconditions and postconditions.

Compare two code segments or algorithms.

Identify the type of error produced, and errors and fixes (Section 10.2).

The debugging competency adds: differentiate between empirical testing and proof .

What "correct" means

A program is correct if it meets its specification for every valid input . Passing one example does not make it correct. The specification is often written as a precondition and a postcondition.

  • Preconditions and postconditions // precondition: n ≥ 1 and a[0] … a[n - 1] contain integers
  • // postcondition: returns the largest value among a[0] … a[n - 1]
  • int findMax ( int[ ] a, int n )
  • int max ← a[0]
  • for ( int i ← 1; i < n; i ← i + 1 )
  • if ( a[i] > max )
  • max ← a[i]
  • end if
  • end for
  • return max
  • end findMax
  • Term Meaning In findMax
  • Precondition Must be true before the call; the caller's responsibility n ≥ 1, because a[0] must exist
  • Postcondition Guaranteed after the call, if the precondition held The return value is the largest element

ETS's sample procedures state preconditions in comments, such as // precondition: n is a positive integer .

Identifying valid preconditions

Ask: what could make this code fail or give a meaningless answer? The precondition should rule out exactly those inputs.

  • Procedure Valid precondition Why
  • Binary search The array is sorted in the order the code assumes Otherwise halving can discard the target
  • average ( a, n ) n > 0 Division by n
  • findMax ( a, n ) n ≥ 1 Reads a[0]
  • sqrtApprox ( x ) x ≥ 0 No real square root for negative numbers
  • substring ( b, e ) 0 ≤ b ≤ e ≤ length Positions must exist

A precondition that is too strong is also a poor choice. "n = 10" for findMax is true of some valid calls, but the code works for any n ≥ 1.

Identifying valid postconditions

A postcondition describes the result or final state , not the steps taken:

  • Good: "returns the index of the first occurrence of target, or −1 if target is not in the array."
  • Good: "the elements of arr are in nondecreasing order and are a rearrangement of the original elements."

Poor: "loops through the array." That describes steps, not a guarantee.

For a sort, "the array is sorted" is not enough on its own. A procedure that overwrote everything with zeros would satisfy it. The postcondition must also say the array holds the same values .

Loop invariants

A loop invariant is a condition that is true before the loop starts and remains true after every iteration. When the loop ends, the invariant plus the exit condition gives the postcondition.

For findMax , the invariant at the top of each iteration is: max is the largest value in a[0] … a[i − 1] .

Initially (i = 1): max = a[0], the largest of a[0] … a[0]. True.

Maintained: if a[i] > max, max becomes a[i]; otherwise max stays. Either way max is the largest of a[0] … a[i].

At exit (i = n): max is the largest of a[0] … a[n − 1], which is the postcondition.

ETS's own explanation of its find-the-maximum sample uses exactly this reasoning. An invariant is also a quick way to judge a missing condition : the choice that keeps the invariant true is the correct one.

  • Finding inputs that produce a given output
  • Work backward from the output, or test each candidate input: int mystery ( int x )
  • if ( x % 3 == 0 )
  • return x / 3
  • else
  • return x + 1
  • end if
  • end mystery

Which inputs make mystery return 4? Working backward: if x is a multiple of 3, then x / 3 = 4 gives x = 12 . Otherwise x + 1 = 4 gives x = 3 , but 3 is a multiple of 3, so that case never uses x + 1 (mystery(3) returns 1). The only input is 12 . Checking the "else" case for consistency is exactly the step that separates the right answer from a tempting wrong one.

Comparing two code segments or algorithms

When asked whether two segments are equivalent , or which is better :

Same results? Test ordinary values and boundary values: 0, 1, negative numbers, empty arrays, equal elements, and the first and last positions. One disagreement proves they are not equivalent.

Same side effects? Do both modify the array, print the same output, or change the same variables?

Efficiency: compare growth rates (Section 5.1). For example, both segments may be correct, but one is O(n²) and the other O(n).

Clarity and maintainability: fewer duplicated statements, meaningful names, and no hard-coded values (Section 10.4).

Empirical testing vs. proof

Empirical testing Proof

Method Run the program on selected inputs and compare with expected outputs Logical argument (for example, loop invariants or induction) that the code meets its specification

  • Covers Only the inputs tried All inputs that satisfy the precondition
  • Can show That a bug exists (a failing test) That no bug exists relative to the specification
  • Cost Cheap, automatable, repeatable Demanding; used for critical code

Edsger Dijkstra put the limitation of testing this way: testing can show the presence of bugs, but never their absence . A function that returns the correct result for 50 test inputs can still fail on the 51st, for example on an empty array or a negative number that no test included. In practice, teams combine thorough testing (Section 10.3) with reasoning such as invariants, and reserve formal proof for the most critical software.