Programming Fundamentals

This document provides comprehensive coverage of programming fundamentals for the DSE ICT examination. Basic programming concepts and SQL are covered in ../3-programming-and-databases/2_programming-and-databases. This document extends those topics with Deeper treatment of algorithms, string manipulation, file handling, debugging, and DSE-specific exam Techniques.

Variables and Constants

Variable Naming Conventions

Data Types in Detail

Type coercion and conversion:

Converting between types is a common source of errors. In many languages, mixing types in an expression Causes automatic type promotion.

x = 7 / 2       # x = 3.5 (float division)
y = 7 // 2      # y = 3 (integer division)
z = int(3.9)    # z = 3 (truncation, NOT rounding)

# Common error:
score = input("Enter score: ")   # score is a STRING, e.g., "85"
total = score + 10               # ERROR: cannot add string and integer
total = int(score) + 10          # CORRECT: convert string to int first

Control Structures in Depth

Nested Selection

Nested IF statements occur when one IF statement is placed inside another. Each level of nesting Should be indented for clarity.

BEGIN
    INPUT age, isWeekend
    IF age < 12 THEN
        IF isWeekend = TRUE THEN
            price = 60
        ELSE
            price = 50
        ENDIF
    ELSE IF age <= 64 THEN
        IF isWeekend = TRUE THEN
            price = 120
        ELSE
            price = 100
        ENDIF
    ELSE
        IF isWeekend = TRUE THEN
            price = 70
        ELSE
            price = 60
        ENDIF
    ENDIF
    OUTPUT price
END

FOR vs WHILE Loops

Choosing between FOR and WHILE:

• Use FOR when you know exactly how many times the loop should run (e.g., processing every element in an array).
• Use WHILE when the number of iterations depends on a condition that is evaluated at runtime (e.g., keep asking for input until the user enters a valid value).

Loop Patterns

Sentinel-Controlled Loop

A loop that continues until a special value (sentinel) is entered.

BEGIN
    SET total = 0
    SET count = 0
    INPUT score
    WHILE score <> -1
        total = total + score
        count = count + 1
        INPUT score
    ENDWHILE
    IF count > 0 THEN
        OUTPUT total / count
    ELSE
        OUTPUT "No valid data"
    ENDIF
END

Accumulator Pattern

Accumulates a running total.

BEGIN
    SET sum = 0
    FOR i = 1 TO 100
        sum = sum + i
    NEXT i
    OUTPUT sum
END

Counting Pattern

Counts how many items satisfy a condition.

BEGIN
    SET count = 0
    FOR i = 0 TO N - 1
        IF numbers[i] > 50 THEN
            count = count + 1
        ENDIF
    NEXT i
    OUTPUT count
END

Finding Maximum/Minimum

BEGIN
    SET maximum = numbers[0]
    FOR i = 1 TO N - 1
        IF numbers[i] > maximum THEN
            maximum = numbers[i]
        ENDIF
    NEXT i
    OUTPUT maximum
END

BEGIN
    INPUT N
    SET numbers = array of size N
    FOR i = 0 TO N - 1
        INPUT numbers[i]
    NEXT i

    SET sum = 0
    SET maximum = numbers[0]
    SET minimum = numbers[0]
    FOR i = 0 TO N - 1
        sum = sum + numbers[i]
        IF numbers[i] > maximum THEN
            maximum = numbers[i]
        ENDIF
        IF numbers[i] < minimum THEN
            minimum = numbers[i]
        ENDIF
    NEXT i

    SET average = sum / N
    SET aboveAverage = 0
    FOR i = 0 TO N - 1
        IF numbers[i] > average THEN
            aboveAverage = aboveAverage + 1
        ENDIF
    NEXT i

    OUTPUT "Sum: " + sum
    OUTPUT "Average: " + average
    OUTPUT "Maximum: " + maximum
    OUTPUT "Minimum: " + minimum
    OUTPUT "Above average: " + aboveAverage
END

Functions and Procedures in Depth

Parameter Passing

In many exam-style pseudocode languages, parameters are passed by value by default. To pass by Reference (allowing the procedure to modify the original), some notations use BYREF.

PROCEDURE addBonus(BYREF salary, bonus)
    salary = salary + bonus
END PROCEDURE

BEGIN
    SET pay = 30000
    CALL addBonus(pay, 5000)
    OUTPUT pay
END

Recursion

A recursive function calls itself to solve a problem by breaking it into smaller subproblems.

FUNCTION fibonacci(n)
    IF n <= 1 THEN
        RETURN n
    ELSE
        RETURN fibonacci(n - 1) + fibonacci(n - 2)
    ENDIF
END FUNCTION

String Manipulation

String operations are frequently tested in DSE ICT programming questions.

Common String Operations

Character Analysis

FUNCTION countVowels(text)
    SET count = 0
    SET vowels = "aeiouAEIOU"
    FOR i = 0 TO LEN(text) - 1
        SET char = MID(text, i + 1, 1)
        IF FIND(char, vowels) > 0 THEN
            count = count + 1
        ENDIF
    NEXT i
    RETURN count
END FUNCTION

FUNCTION reverseString(text)
    SET result = ""
    FOR i = LEN(text) DOWNTO 1
        result = result + MID(text, i, 1)
    NEXT i
    RETURN result
END FUNCTION

FUNCTION isPalindrome(text)
    SET length = LEN(text)
    FOR i = 1 TO length / 2
        IF MID(text, i, 1) <> MID(text, length - i + 1, 1) THEN
            RETURN FALSE
        ENDIF
    NEXT i
    RETURN TRUE
END FUNCTION

File Input/Output in Depth

File Operations

Sequential vs Random Access

Chan Tai Man,5A,85
Lee Siu Ming,5B,72
Wong Ka Wai,5A,93

BEGIN
    OPEN FILE "students.txt" FOR READ
    SET highestScore = -1
    SET topStudent = ""

    WHILE NOT end of file
        READ line FROM FILE
        SET commaPos = FIND(",", line)
        SET name = LEFT(line, commaPos - 1)
        SET rest = MID(line, commaPos + 1, LEN(line) - commaPos)
        SET commaPos2 = FIND(",", rest)
        SET class = LEFT(rest, commaPos2 - 1)
        SET scoreStr = MID(rest, commaPos2 + 1, LEN(rest) - commaPos2)
        SET score = CONVERT_TO_INT(scoreStr)

        IF score > highestScore THEN
            highestScore = score
            topStudent = name
        ENDIF
    ENDWHILE

    CLOSE FILE
    OUTPUT "Top student: " + topStudent + " with score: " + highestScore
END

Algorithms — Search and Sort

Linear Search

Linear search checks each element in sequence until the target is found or all elements have been Checked.

FUNCTION linearSearch(arr, size, target)
    FOR i = 0 TO size - 1
        IF arr[i] = target THEN
            RETURN i
        ENDIF
    NEXT i
    RETURN -1
END FUNCTION

Binary Search

Binary search works on sorted arrays by repeatedly dividing the search range in half.

FUNCTION binarySearch(arr, size, target)
    SET low = 0
    SET high = size - 1
    WHILE low <= high
        SET mid = (low + high) / 2  (integer division)
        IF arr[mid] = target THEN
            RETURN mid
        ELSE IF arr[mid] < target THEN
            low = mid + 1
        ELSE
            high = mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
END FUNCTION

Insertion Sort

Insertion sort builds a sorted array one element at a time by inserting each element into its correct Position among the previously sorted elements.

FUNCTION insertionSort(arr, size)
    FOR i = 1 TO size - 1
        SET key = arr[i]
        SET j = i - 1
        WHILE j >= 0 AND arr[j] > key
            arr[j + 1] = arr[j]
            j = j - 1
        ENDWHILE
        arr[j + 1] = key
    NEXT i
END FUNCTION

Comparison of Sorting Algorithms

Top-Down Design

Top-down design (stepwise refinement) is a problem-solving approach where a complex problem is broken Down into smaller, more manageable sub-problems. Each sub-problem is then further refined until the Solutions are simple enough to implement directly.

Process

1. Identify the main task: State the overall problem in one sentence.
2. Decompose into sub-tasks: Break the main task into 2—5 major sub-tasks.
3. Refine each sub-task: Further break down each sub-task until each component is a simple, well-defined operation.
4. Implement each component: Write code (or pseudocode) for each leaf-level component.
5. Combine and test: Integrate all components and test the complete solution.

Advantages of Top-Down Design

Flowcharts and Pseudocode — DSE Exam Requirements

Flowchart Symbols

Pseudocode Conventions for DSE

The DSE ICT examination uses structured pseudocode. Key conventions:

Converting Between Flowcharts and Pseudocode

Every flowchart symbol maps directly to pseudocode:

Debugging and Testing

Types of Errors

Debugging Techniques

Testing Strategies

Common Pitfalls

1. Off-by-one errors in loops: When iterating through an array of size N, the loop should run from 0 to N-1 (inclusive), not 0 to N. Accessing index N causes an out-of-bounds error.

2. Not initialising variables before use: If a variable used as a maximum or minimum is initialised to 0 instead of the first array element, the algorithm fails when all values are negative.

3. Confusing assignment (=) and comparison (==): In many languages, = assigns a value and == compares. Using = in a condition assigns the value instead of comparing it.

4. Forgetting to update the loop counter in WHILE loops: If the loop variable is not modified inside the loop body, the condition never becomes false, causing an infinite loop.

5. Binary search requires sorted data: Applying binary search to an unsorted array produces incorrect results. Always verify the array is sorted before using binary search.

6. String indexing: Some pseudocode conventions use 1-based indexing (first character is at position 1), while programming languages like Python use 0-based indexing. Be consistent with the convention specified in the exam.

7. Infinite recursion without a base case: A recursive function must have a condition that stops the recursion. Without it, the function calls itself indefinitely, eventually causing a stack overflow.

8. Not closing files: Forgetting to close a file after reading or writing can cause data loss (for writes) or resource leaks (files remaining locked).

9. Integer division truncation: In many languages, dividing two integers produces an integer result (truncated). 7 / 2 gives 3Not 3.5. Use floating-point division when a decimal result is needed.

10. Scope of variables: Local variables inside a function are not accessible outside the function. Using a variable name that conflicts with a global variable can lead to unexpected behaviour.

Practice Problems

BEGIN
    INPUT N
    SET positive = 0
    SET negative = 0
    SET zero = 0
    FOR i = 1 TO N
        INPUT num
        IF num > 0 THEN
            positive = positive + 1
        ELSE IF num < 0 THEN
            negative = negative + 1
        ELSE
            zero = zero + 1
        ENDIF
    NEXT i
    OUTPUT positive, negative, zero
END

FUNCTION countWords(text)
    SET count = 0
    SET inWord = FALSE
    FOR i = 1 TO LEN(text)
        SET char = MID(text, i, 1)
        IF char <> " " THEN
            IF inWord = FALSE THEN
                count = count + 1
                inWord = TRUE
            ENDIF
        ELSE
            inWord = FALSE
        ENDIF
    NEXT i
    RETURN count
END FUNCTION

BEGIN
    OPEN FILE "attendance.txt" FOR READ
    SET names = empty array
    SET percentages = empty array
    SET studentCount = 0

    WHILE NOT end of file
        READ line FROM FILE
        SET spacePos = FIND(" ", line)
        SET name = LEFT(line, spacePos - 1)
        SET attendance = MID(line, spacePos + 1, LEN(line) - spacePos)

        SET totalDays = LEN(attendance)
        SET presentDays = 0
        FOR i = 1 TO totalDays
            IF MID(attendance, i, 1) = "P" THEN
                presentDays = presentDays + 1
            ENDIF
        NEXT i

        SET percentage = (presentDays / totalDays) * 100
        APPEND name TO names
        APPEND percentage TO percentages
        studentCount = studentCount + 1
    ENDWHILE
    CLOSE FILE

    OUTPUT "Students with attendance below 80%:"
    FOR i = 0 TO studentCount - 1
        IF percentages[i] < 80 THEN
            OUTPUT names[i] + " - " + percentages[i] + "%"
        ENDIF
    NEXT i
END

BEGIN
    INPUT N
    SET prices = array of size N
    SET total = 0

    FOR i = 0 TO N - 1
        INPUT prices[i]
        total = total + prices[i]
    NEXT i

    OUTPUT "Total before discount: " + total

    IF total >= 1000 THEN
        discountRate = 15
    ELSE IF total >= 500 THEN
        discountRate = 10
    ELSE IF total >= 100 THEN
        discountRate = 5
    ELSE
        discountRate = 0
    ENDIF

    SET discountAmount = total * discountRate / 100
    SET finalAmount = total - discountAmount

    OUTPUT "Discount: " + discountRate + "%"
    OUTPUT "Discount amount: " + discountAmount
    OUTPUT "Final amount: " + finalAmount
END

Summary

theory, practical implementation, and key applications.

Stashed changes:docs/docs_dse/ICT/programming-fundamentals.md

Key concepts include:

• Big O notation and complexity analysis
• searching algorithms (binary, linear)
• sorting algorithms (bubble, merge, quick)
• graph algorithms (Dijkstra, BFS, DFS)
• dynamic programming

Understanding these concepts thoroughly is essential for both examinations and practical programming, and requires both theoretical knowledge and hands-on practice.

Stashed changes:docs/docs_dse/ICT/programming-fundamentals.md

Worked Examples

Worked examples demonstrating the application of key concepts are covered in the detailed sub-pages linked above.