Programming with pseudocode

Pseudocode is a formalized representation of an algorithm in natural language with a minimal set of strict constructs (variables, expressions, branches, loops, subroutines) sufficient for unambiguous human interpretation and easy translation into any programming language. Pseudocode serves as a bridge between the problem and the implementation: it captures the logic and invariants without distracting with the syntactic details of a specific language.
For the Unified State Exam in Computer Science, mastery of pseudocode is a practical skill: it is required for parsing conditions, constructing algorithms, analyzing complexities, proving the correctness of loops, and converting flowcharts into programs.

Formal model of pseudocode

1. Algorithm as a tuple
   

   An algorithm in pseudocode is considered a tuple

   A = (Σ, V, T, S, R)

   Where

   • Σ – alphabet of lexemes (identifiers, literals, operators);
   • V is a finite subset of identifiers (variables, constants, subroutine names);
   • T – type system (integer, real, logical, strings, arrays, records);
   • S – a set of correct operators (assignment, if, for, while, subroutine call, return/output/input);
   • R – inference relations that define syntax rules and operational semantics.

    

   Execution is the transformation of the memory state M (mapping V → value T) by sequential (or branching) application of operators S according to the rules R.

2. Syntactic form
   

   We use a structural indentation style (like Python/CLRS pseudocode). Basic elements:

    

   • Assignment:
   • x ← expr
   • Condition:
   • if cond then
   •     S1
   • otherwise
   •     S2
   • All
   • Cycles:
   • Bye, cond do S all
   • for i from a to b step h do S all
   • repeat S until cond
   • Subroutines:
   • function f(parameters): type
   •     body
   •     return value
   • end
3. Operational semantics (sketch)
   
   • Assignment: evaluate expr in the current environment Env, write the result to x.
   • Condition: if cond = true, execute S1, otherwise S2 (if any).
   • While loop: predicate iteration – test cond before body; invariant Inv must be true before/after each iteration; variant (decreasing value) ensures termination.
   • For loop: syntactic sugar over while with automatic counter change.
   • Subroutine: When called, a new local environment is created; parameters are passed by value (default) or by reference (by explicit marking).

Types, expressions, and scopes

1. Type system 
   

   whole // whole

   thing // material

   log // boolean

   string // strings

   array[T] // indexed collection

   record {…} // aggregates (if necessary)

    

   Implicit conversions are prohibited: if necessary, write explicitly int(x) or thing(x) explicitly.

2. Scope
   
   • Local variables: declared within a subroutine/block, not accessible from outside.
   • Global: declared outside all routines (for learning purposes, avoid unless required).
   • Shadows: A local name can overlap a global one; it is recommended not to overuse it.
3. Subroutine parameters
   
   • sign – transfer by value (copy);
   • reference – alias to argument (changes are visible from the outside);
   • result – return value; for functions – via return; for procedures – through the parameters via the link.

Subroutines: contracts, pre- and post-conditions 

1. Contract (Design by Contract)
   

   For each function/procedure, we record:

   name(parameter types) → result type

   preconditions: P(args) // what must be true at input

   postconditions: Q(args, result) // what is guaranteed at the output

   Side effects: description (or not)

   Example (argmin) :

   function argmin(A: array[int]) → entry {value: int, index: int}

   prev: |A| ≥ 1

    

   post: A[result.index] = min(A) and this is the first occurrence

2.  Purity and Determinism
   

   A pure function: the return value is determined only by the parameters, without I/O or changes to external state. In Unified State Exam (USE) problems, we strive for purity.

Pseudocode Operators and Patterns

1. Linear design
   

   input n

   S ← 0

   for i from 1 to n do

       S ← S + i

   All

    

   conclusion S

2. Branching
   

   if x % 2 = 0 then

       output “even”

   otherwise

       output “odd”

    

   All

3. Cycles and invariants
   

   Template for proving the correctness of a while cycle:

   invariant Inv: … // formulate

   // base: Inv true before input

   while you do the cond

       // assume Inv is true at the start of the iteration

       loop body

       // prove that Inv is true at the end of the iteration

   All

   // after exit: Inv and ¬cond → goal proven

   Example (finding the minimum):

   m ← A[1]; i_min ← 1

   for k from 2 to n do

       if A[k] < m then

           m ← A[k]; i_min ← k

       All

   All

    

   Invariant: after processing A[1..k]: m = min(A[1..k]), i_min is the index of the first minimum.

4. Arrays and processing algorithms
   
   • Single-pass aggregates: sum/min/max/counters.
   • Two-pointer method (two indices) for compression/filtering.
   • Prefix sums for fast queries over segments:

   P[0] ← 0

   for i from 1 to n do

       P[i] ← P[i−1] + A[i]

   All

    

   // sum over [l..r] = P[r] − P[l−1]

5. Recursion and divide and conquer
   

   function gcd(a:int, b:int) → int

       if b = 0 then return |a|

       return gcd(b, a % b)

    

   end

Design and quality standards

1. Naming: descriptive names in “snake” or “verbal” style – sum_digits, is_prime, read_count.
2. Indents and block structure: each nesting level – +2–4 spaces.
3. Comments on the matter: they explain why, but not what.
4. Boundaries and extreme cases: n=0, empty arrays, negative values.
5. Complexity: indicate time/memory estimate next to the algorithm:
   complexity: time Θ(n), memory Θ(1)
6. Input/output: separate from computational logic – pure functions + I/O wrapper.
7. Consistency of style: the same words for the same actions (“input”, “output”, “return”, “all”). 

Mini-cheat sheet

Assignment

x ← expression

Condition

if condition then

    S1

otherwise

    S2

All

Cycles

fulfill the condition for now

    body

All 

for i from a to b step h do

    body

All 

repeat

    body

while the condition

Subroutine

function f(a:type, b:type) → typeRes

    // precondition: …

    // postcondition: …

    …

    return the result

end

Prefix sums

P[0] ← 0

for i from 1 to n do P[i] ← P[i−1] + A[i] all

sum(l, r) = P[r] − P[l−1]

Parameter by reference

procedure swap(reference x:target, reference y:target)

    t ← x; x ← y; y ← t

end

Common mistakes and how to prevent them

• Vague language: mixing colloquial and coded phrases – → ambiguity. Solution: use a fixed vocabulary of constructions.
• No invariants: the loop is written, but its correctness is unclear. Solution: formulate Inv and the termination variant.
• Index confusion : 0- and 1-indexing. Solution: declare the agreement at the beginning and follow it.
• Mixing I/O and computation: a function prints its result instead of returning it. Solution: Separate output from logic.
• Undefined edge cases: empty inputs. Solution: explicit preconditions/processing branches.
• Ambiguous parameters: does the argument change? Solution: mark ref/value.
• Lack of complexity estimation: It is difficult to justify the choice of the solution. Solution: write asymptotics.

Connection with preparation for the  Exam in Computer Science

• Algorithmization: Pseudocode is the standard form of answer in programming/flowchart problems.
• Invariants and proofs: The while loop with a formal invariant is a frequent check of understanding.
• Structuring: translation from flowchart to pseudocode and back.
• Difficulty: Specifying Θ(n), Θ(log n) increases the parsing score.
• Working with arrays and strings: one-pass aggregate patterns, prefixes, two pointers.
• Features: return value, contract, no side effects – makes it easier to check automatically.

Five exercises with detailed solutions

Exercise 1. Formal invariant for the sum and number of positive

Problem: Write pseudocode that returns the sum of positive elements and their number for the array A[1..n], and prove its correctness using a loop invariant.

Solution (pseudocode):

function sum_pos(A: array[int]) → entry {S:int, K:int}

    req: |A| ≥ 0

    S ← 0; K ← 0

    for i from 1 to |A| do

        if A[i] > 0 then

            S ← S + A[i]

            K ← K + 1

        All

    All

    return {S, K}

end

Invariant after step i:
S = sum of positive integers from A[1..i], K = their number. Base: i=0 – true. Transition: at i+1, either add A[i+1] and 1, or not; properties are preserved. After i=n, ​​we obtain the required result.

Exercise 2. Argmin with the first entry

Condition. Implement pseudocode for the argmin(A) function (minimum and index of first occurrence). Provide preconditions/postconditions.

Solution:

function argmin(A: array[int]) → entry {value:int, index:int}

    prev: |A| ≥ 1

    m ← A[1]; i_min ← 1

    for k from 2 to |A| do

        if A[k] < m then

            m ← A[k]; i_min ← k

        All

    All

    post: A[i_min] = m and ∀j< i_min: A[j] ≥ m

    return {m, i_min}

end

Complexity: time Θ(n), memory Θ(1).

Exercise 3. Prefix sums and queries over segments

Problem: Given an array A[1..n], answer q queries for “sum of elements on [l..r]”. Provide pseudocode with preprocessing and complexity estimates.

Solution:

procedure build_prefix(A: array[int], ref P: array[int])

    P[0] ← 0

    for i from 1 to |A| do

        P[i] ← P[i−1] + A[i]

    All

end

function range_sum(P: array[int], l:int, r:int) → int

    return P[r] − P[l−1]

end

Complexity: preprocessing Θ(n), one query – Θ(1), memory Θ(n).

Exercise 4. Two pointers: filtering odd numbers

Condition: Compress the array in place, leaving only the odd elements at the beginning, preserving the order. Return the new length.

Solution:

procedure compact_odds(ref A: array[int]) → int

    write ← 1

    to read from 1 to |A| do

        if A[read] % 2 ≠ 0 then

            A[write] ← A[read]

            write ← write + 1

        All

    All

    return write – 1

end

Invariant: before each iteration, A[1..write−1] are the original odd ones in the same order. Complexity Θ(n).

Exercise 5. Proof of loop correctness: Finding the subarray with the maximum sum (Kadane)

Condition. Write Kadane’s pseudocode (meaning and bounds) and justify the correctness of the step.

Solution:

function max_subarray(A: array[int]) → entry {best:int, l: int, r: int}

    req: |A| ≥ 1

    cur ← A[1]; best ← A[1]

    start ← 1; l ← 1; r ← 1

    for j from 2 to |A| do

        if A[j] ≥ cur + A[j] then

            cur ← A[j]

            start ← j

        otherwise

            cur ← cur + A[j]

        All

        if (cur > best) or (cur = best and (j − start < r − l)) then

            best ← cur; l ← start; r ← j

        All

    All

    return {best, l, r}

end

Invariant: cur is the maximum of the sums of subarrays ending in j; best is the maximum over all positions < j. The step is correct because the best sum ending in j either starts at j or continues the optimum at j−1. 

Pseudocode Author Self-Assessment Checklist

• The contract of subroutines (pre/post conditions) is formulated.
• Invariants and variants of cycles are defined.
• Array boundaries and indexing conventions are clearly defined.
• Pure computational logic vs I/O is highlighted.
• Time/memory difficulties are assessed.
• Extreme cases (empty, negative, equal) are handled.
• A consistent style is used (lexemes, indents, keywords).

Security questions

1. What are the advantages of pseudocode over flowcharts and concrete language?
2. Formulate an invariant for the minimum search algorithm and explain its role.
3. How do “by-value” and “by-reference” parameters differ in pseudocode semantics?
4. Why is it important to separate I/O from pure functions?
5. What is the asymptotic behavior of prefix sums in preprocessing and queries?

Conclusion

Pseudocode is a discipline of precise thinking: it makes an algorithm independent of language syntax, emphasizes invariants and complexity, removes ambiguity, and simplifies verification. For the computer science Exam, mastering pseudocode speeds up the process from an idea to a correct solution, improves the quality of argumentation, and reduces the risk of errors at boundaries and in loops. Master the suggested templates, follow the checklist, and work through the exercises—and your pseudocode will become a reliable support for solving any exam problems.