Paper 3 Crash Course — G12 CS

1.1 Assembly Language & LMC

📌 Assembly Language (2GL)

A low-level programming language using mnemonics (short text codes) that map almost directly to machine code instructions. Each mnemonic represents one CPU instruction. Requires an assembler to translate to machine code.

📌 LMC (Little Man Computer)

A simplified educational model of a CPU with 100 memory cells (00–99), one accumulator, and a small set of instructions. Used to understand how a CPU executes fetch-decode-execute cycles.

LMC Instruction Set

Mnemonic	Opcode	Operation	Effect on Accumulator
`INP`	901	Input	ACC ← user input value
`OUT`	902	Output	Display current ACC value
`LDA xx`	5xx	Load from memory	ACC ← value at address xx
`STA xx`	3xx	Store to memory	Memory[xx] ← ACC
`ADD xx`	1xx	Add	ACC ← ACC + Memory[xx]
`SUB xx`	2xx	Subtract	ACC ← ACC − Memory[xx]
`BRA xx`	6xx	Branch always	Jump to address xx unconditionally
`BRZ xx`	7xx	Branch if zero	Jump to xx if ACC = 0
`BRP xx`	8xx	Branch if positive	Jump to xx if ACC ≥ 0
`HLT`	000	Halt	Stop program execution
`DAT xx`	—	Data declaration	Reserve memory cell with initial value xx

★ Example 1 — Add two numbers entered by user

INP          ; input first number → ACC
STA NUM1      ; store in NUM1
INP          ; input second number → ACC
ADD NUM1      ; ACC = ACC + NUM1
OUT          ; output sum
HLT          ; stop
NUM1 DAT 0   ; memory cell for first number

★ Example 2 — Count down from input to 1

LOOP INP       ; input the starting number
     STA COUNT   ; store in COUNT
NEXT LDA COUNT   ; load COUNT into ACC
     BRZ END     ; if ACC = 0, jump to END
     OUT         ; output current COUNT
     SUB ONE     ; ACC = ACC - 1
     STA COUNT   ; save updated COUNT
     BRA NEXT    ; loop back
END  HLT
COUNT DAT 0
ONE   DAT 1

★ Example 3 — Find larger of two numbers

     INP        ; input A
     STA A
     INP        ; input B
     STA B
     SUB A      ; ACC = B - A
     BRP BGRT   ; if B >= A, jump to BGRT
     LDA A      ; else A is larger
     OUT
     HLT
BGRT LDA B    ; B is larger
     OUT
     HLT
A    DAT 0
B    DAT 0

🧩 Task 1 — Analyse this LMC program

Trace through the program with input 5. What does it output? What does it calculate?

     INP
     STA N
     LDA ZERO
     STA SUM
LOOP LDA N
     BRZ END
     ADD SUM
     STA SUM
     LDA N
     SUB ONE
     STA N
     BRA LOOP
END  LDA SUM
     OUT
     HLT
N    DAT 0
SUM  DAT 0
ONE  DAT 1
ZERO DAT 0

Answer: Calculates 1+2+3+...+N = sum from 1 to N. With input 5 → outputs 15.

⚠️ Common LMC Mistakes

BRZ checks if ACC = 0, not if memory is 0. Always LDA before BRZ.
BRP branches if ACC ≥ 0 (including zero). Use BRZ first if you only want strictly positive.
Forgetting to STA before looping — the accumulator value will be lost on the next INP or ADD.
All LMC programs end with HLT — missing this causes the program to continue executing garbage.

1.2 Trace Tables

📌 Trace Table

A method of manually executing an algorithm step by step, recording the value of each variable after every instruction. Used to verify algorithm correctness, find bugs, and predict output.

📋 How to Complete a Trace Table

Create one column per variable + one column for output.
Execute each line of code in order — follow IF/ELSE branches and loops exactly.
Only fill in a cell when that variable's value CHANGES — leave blank if unchanged.
For loops: repeat the loop body rows until the exit condition is true.
Mark the output column whenever PRINT/OUTPUT is called.

★ Example 1 — Trace this algorithm (find max)

nums = [3, 7, 2, 9, 5]
max = nums[0]              # max = 3
FOR i = 1 TO 4
    IF nums[i] > max THEN
        max = nums[i]
    ENDIF
NEXT i
PRINT max

i	nums[i]	max	nums[i] > max?	OUTPUT
—	—	3	—
1	7	7	YES
2	2	7	NO
3	9	9	YES
4	5	9	NO
—	—	—	—	9

★ Example 2 — Trace with counter

count = 0
total = 0
WHILE count < 5
    total = total + count
    count = count + 1
ENDWHILE
PRINT total

count	total	count < 5?	OUTPUT
0	0	YES
1	0	YES
2	1	YES
3	3	YES
4	6	YES
5	10	NO	10

🧩 Task 2 — Complete the trace table

x = 10
y = 3
WHILE y > 0
    x = x - y
    y = y - 1
ENDWHILE
PRINT x

Complete the trace table for variables x, y. What does the program output?

x	y	y > 0?	OUTPUT
10	3	YES
?	?	YES
?	?	YES
?	?	NO	?

Answer: x=10-3=7, y=2 | x=7-2=5, y=1 | x=5-1=4, y=0 → output: 4

🧩 Task 3 — Nested loop trace

result = 0
FOR i = 1 TO 3
    FOR j = 1 TO i
        result = result + 1
    NEXT j
NEXT i
PRINT result

Trace the variables i, j, result. What is the final output?

Answer: i=1,j=1→result=1 | i=2,j=1→2,j=2→3 | i=3,j=1→4,j=2→5,j=3→6. Output: 6

1.3 Expert Systems

📌 Expert System

A computer system that simulates the decision-making ability of a human expert in a specific domain. It uses logic programming (like Prolog) to separate the knowledge base (facts + rules) from the inference engine (which applies rules to reach conclusions).

Core Components

Knowledge base: a database of facts (unconditional truths) and rules (conditional statements, written as Head :- Body in Prolog).
Inference engine: the reasoning mechanism that applies logic to known facts to answer queries or draw new conclusions.
User interface: how the user inputs data and receives the system's conclusions.
Explanation module: traces the logic path to explain HOW or WHY a conclusion was reached.

Examples & Uses

Medical diagnosis: (e.g., MYCIN) identifying illnesses based on patient symptoms.
Technical support: hardware/software troubleshooting diagnostics.
Finance: loan approval systems, credit scoring, fraud detection.
Agriculture: soil analysis and pest identification.

★ Example 1: Animal Identification (Prolog)

In Prolog, we define facts and rules. The :- operator means "IF", and the , means "AND".

% 1. FACTS (Knowledge Base)
has_feathers(tweety).
can_fly(tweety).
has_feathers(pingu).
swims(pingu).
has_fur(rex).
barks(rex).

% 2. RULES (Knowledge Base)
is_bird(Animal) :- has_feathers(Animal), can_fly(Animal).
is_penguin(Animal) :- has_feathers(Animal), swims(Animal).
is_dog(Animal) :- has_fur(Animal), barks(Animal).

% 3. QUERIES (Inference Engine in action)
% User asks: Is Tweety a bird?
% ?- is_bird(tweety).
% Output: true.

% User asks: Which animal is a dog?
% ?- is_dog(X).
% Output: X = rex.

★ Example 2: Medical Diagnosis (Prolog)

% FACTS: Patient symptoms
symptom(john, fever).
symptom(john, cough).
symptom(mary, headache).
symptom(mary, sneezing).

% RULES: Illness definitions
has_flu(Patient) :- symptom(Patient, fever), symptom(Patient, cough).
has_cold(Patient) :- symptom(Patient, headache), symptom(Patient, sneezing).

% QUERY: Does John have the flu?
% ?- has_flu(john).
% Output: true.

🧩 Task 4 — Weather Clothing Advisor in Prolog

Write a Prolog knowledge base (facts and rules) for a clothing advisor. Define facts for the current weather (e.g., temperature(monday, cold)., weather(monday, raining).) and write rules for when to wear a coat, umbrella, or sunscreen.

Example: wear_coat(Day) :- temperature(Day, cold), weather(Day, raining).

2.1 Arrays (1D & 2D)

📌 Array

A data structure storing a fixed-size, ordered collection of elements of the same data type, accessible by index. Arrays have a defined lower bound (usually 0 or 1) and upper bound (last valid index).

Term	Definition	Example (array of 5 items)
Lower bound	The index of the first element	0 (in Python/C) or 1 (in pseudocode)
Upper bound	The index of the last element	4 (0-indexed) or 5 (1-indexed)
Size / Length	Total number of elements	Upper bound − Lower bound + 1 = 5
Element	One item stored in the array	scores[2] = 85
Index / Subscript	Position of an element in the array	scores[0], scores[1], … scores[4]

★ 1D Array — Declaration & Access

# Python
scores = [72, 85, 91, 64, 78]    # 1D array, indices 0–4
print(scores[0])                  # 72 (first element)
print(scores[4])                  # 78 (last element)
print(len(scores))                # 5 (size)

# Sum all elements
total = 0
FOR i = 0 TO 4
    total = total + scores[i]
NEXT i
PRINT total   # 390

★ 2D Array — Grid / Matrix

# 2D array: 3 rows × 4 columns
grid = [[1,2,3,4],
        [5,6,7,8],
        [9,10,11,12]]

grid[0][0] = 1     # row 0, column 0
grid[1][2] = 7     # row 1, column 2
grid[2][3] = 12    # row 2, column 3

# Print all elements
FOR row = 0 TO 2
    FOR col = 0 TO 3
        PRINT grid[row][col]
    NEXT col
NEXT row

🧩 Task 5 — Array operations

Given: marks = [55, 72, 48, 91, 65, 80, 37]

Write pseudocode to: (a) find the highest mark, (b) count how many marks are above 60, (c) print all marks in reverse order.

a) Highest: loop comparing each to max, update max if larger → 91. b) Counter: loop, increment if marks[i]>60 → count=4. c) FOR i=6 TO 0 STEP -1: PRINT marks[i]

🧩 Task 6 — 2D Array: Class Grades

A 2D array grades[3][4] stores grades for 3 students across 4 subjects. Write pseudocode to calculate the average grade for each student (row average).

FOR row=0 TO 2: total=0; FOR col=0 TO 3: total+=grades[row][col]; NEXT col; PRINT total/4; NEXT row

2.2 Bubble Sort

📌 Bubble Sort

A simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Larger values "bubble up" to the end with each pass.

📋 Bubble Sort Algorithm (Pseudocode)

PROCEDURE BubbleSort(arr, n)
    FOR i = 0 TO n-2          # n-1 passes needed
        swapped = FALSE
        FOR j = 0 TO n-2-i    # last i elements already sorted
            IF arr[j] > arr[j+1] THEN
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                swapped = TRUE
            ENDIF
        NEXT j
        IF swapped = FALSE THEN   # optimisation: early exit
            EXIT FOR
        ENDIF
    NEXT i
END PROCEDURE

★ Worked Example — Sort [64, 34, 25, 12, 22]

Initial:  [64, 34, 25, 12, 22]

Pass 1:   64>34 → swap → [34, 64, 25, 12, 22]
          64>25 → swap → [34, 25, 64, 12, 22]
          64>12 → swap → [34, 25, 12, 64, 22]
          64>22 → swap → [34, 25, 12, 22, 64] ← 64 in place

Pass 2:   34>25 → swap → [25, 34, 12, 22, 64]
          34>12 → swap → [25, 12, 34, 22, 64]
          34>22 → swap → [25, 12, 22, 34, 64] ← 34 in place

Pass 3:   25>12 → swap → [12, 25, 22, 34, 64]
          25>22 → swap → [12, 22, 25, 34, 64] ← 25 in place

Pass 4:   12>22 → NO swap → [12, 22, 25, 34, 64] ✓ sorted!

✅ Key Facts for Exam

Time complexity: O(n²) worst/average; O(n) best (already sorted with flag)
After k passes, the last k elements are in their correct final position
Maximum passes needed = n−1 (for n elements)
The swapped flag optimisation exits early if no swaps occurred in a pass

🧩 Task 7 — Bubble Sort trace

Show each pass of bubble sort on: [5, 1, 4, 2, 8]. How many passes are needed? How many comparisons total?

Pass 1: [1,4,2,5,8] | Pass 2: [1,2,4,5,8] | Pass 3: no swaps → done. 3 passes, 4+3+2=9 comparisons.

2.3 Insertion Sort

📌 Insertion Sort

Builds a sorted list one element at a time by taking each unsorted element and inserting it into its correct position among the already-sorted elements, shifting others right to make room.

📋 Insertion Sort Algorithm (Pseudocode)

PROCEDURE InsertionSort(arr, n)
    FOR i = 1 TO n-1
        key = arr[i]          # element to insert
        j = i - 1
        WHILE j >= 0 AND arr[j] > key
            arr[j+1] = arr[j] # shift right
            j = j - 1
        ENDWHILE
        arr[j+1] = key        # insert in correct position
    NEXT i
END PROCEDURE

★ Worked Example — Sort [12, 11, 13, 5, 6]

Start:    [12 | 11, 13, 5, 6]   (sorted part | unsorted part)

Step 1:   key=11, compare 11<12 → shift 12 right
          [11, 12 | 13, 5, 6]

Step 2:   key=13, compare 13>12 → no shift
          [11, 12, 13 | 5, 6]

Step 3:   key=5, shift 13,12,11 right
          [5, 11, 12, 13 | 6]

Step 4:   key=6, shift 13,12,11 right, 5 stays
          [5, 6, 11, 12, 13] ✓

Bubble Sort

Compares adjacent pairs and swaps
Largest element bubbles to end each pass
Easy to understand; inefficient for large data
O(n²) time; O(1) space

Insertion Sort

Picks one element, inserts in correct place
Efficient for small or nearly-sorted arrays
O(n²) worst case; O(n) best (sorted)
Stable, in-place; O(1) space

🧩 Task 8 — Insertion Sort trace

Trace insertion sort on: [29, 10, 14, 37, 13]. Show the array state after each step. How many shifts were made in total?

Step 1: key=10 → [10,29,14,37,13] (1 shift) | Step 2: key=14 → [10,14,29,37,13] (1) | Step 3: key=37 → no shift | Step 4: key=13 → [10,13,14,29,37] (3 shifts). Total: 5 shifts.

2.4 Binary Search

📌 Binary Search

An efficient search algorithm for sorted arrays. Repeatedly divides the search interval in half by comparing the target with the middle element, eliminating half the remaining elements at each step.

⚠️ Binary search ONLY works on sorted arrays!

Applying binary search to an unsorted array will give incorrect results. Always sort the array first, or state that the array must be sorted.

📋 Binary Search Algorithm (Pseudocode)

FUNCTION BinarySearch(arr, target, low, high)
    WHILE low <= high
        mid = (low + high) DIV 2    # integer division
        IF arr[mid] = target THEN
            RETURN mid              # found at index mid
        ELSE IF arr[mid] < target THEN
            low = mid + 1           # search right half
        ELSE
            high = mid - 1          # search left half
        ENDIF
    ENDWHILE
    RETURN -1                       # not found
END FUNCTION

★ Example — Find 33 in [2, 5, 8, 12, 16, 23, 33, 42, 56, 70]

Step	low	high	mid	arr[mid]	Action
1	0	9	4	16	16 < 33 → low = 5
2	5	9	7	42	42 > 33 → high = 6
3	5	6	5	23	23 < 33 → low = 6
4	6	6	6	33	FOUND at index 6 ✓

★ Example — Search for 50 in [3, 7, 11, 18, 25, 37, 44, 60] (not found)

low	high	mid	arr[mid]	Action
0	7	3	18	18 < 50 → low = 4
4	7	5	37	37 < 50 → low = 6
6	7	6	44	44 < 50 → low = 7
7	7	7	60	60 > 50 → high = 6
7	6	—	—	low > high → return -1 (NOT FOUND)

✅ Binary vs Linear Search

Feature	Linear Search	Binary Search
Requires sorted array?	No	YES
Time complexity	O(n)	O(log n)
Best case	O(1) — found first	O(1) — found at mid first
Worst case (n=1000)	1000 comparisons	10 comparisons
Use when	Small or unsorted data	Large sorted data

🧩 Task 9 — Binary Search trace

Trace binary search for target=17 in: [1, 4, 7, 10, 14, 17, 21, 25, 30]. Show each step (low, high, mid, arr[mid]). How many comparisons?

Step 1: low=0,high=8,mid=4,arr[4]=14 < 17 → low=5 | Step 2: mid=6,arr[6]=21 > 17 → high=5 | Step 3: mid=5,arr[5]=17 = FOUND. 3 comparisons.

2.5 Algorithm Efficiency

📌 Time Efficiency

A measure of how the number of operations an algorithm performs grows as the size of the input (n) increases. Expressed using Big O notation.

📌 Space Efficiency

A measure of how the memory an algorithm requires grows as the size of the input (n) increases. An in-place algorithm uses O(1) extra space.

Notation	Name	Example	n=100 operations
O(1)	Constant	Access array element by index	1
O(log n)	Logarithmic	Binary search	~7
O(n)	Linear	Linear search, single loop	100
O(n log n)	Linearithmic	Merge sort, Quick sort	~665
O(n²)	Quadratic	Bubble sort, Insertion sort, nested loop	10,000
O(2ⁿ)	Exponential	Recursive Fibonacci, brute force	Huge!

Image to insert

График Big O: ось X = размер входа n, ось Y = количество операций. Кривые: O(1) плоская, O(log n) медленно растёт, O(n) линейная, O(n²) резко растёт. Разными цветами.

Поиск: "Big O notation complexity graph comparison O(1) O(n) O(n2)"

✅ Identifying Complexity from Code

Single loop over n items → O(n)
Two nested loops over n items → O(n²)
Halving the search space each step → O(log n)
No loop, fixed number of steps → O(1)

🧩 Task 10 — Identify time complexity

What is the time complexity of each algorithm? (a) Linear search in unsorted array of n items. (b) Bubble sort of n items. (c) Accessing grades[3][2] in a 2D array. (d) Binary search in sorted array of n items.

a) O(n) | b) O(n²) | c) O(1) | d) O(log n)

2.6 Stack & Queue

📌 Stack

A LIFO (Last In, First Out) data structure. Elements are added (PUSH) and removed (POP) from the same end, called the top. Like a stack of plates — you always take from the top.

📌 Queue

A FIFO (First In, First Out) data structure. Elements are added (ENQUEUE) at the rear and removed (DEQUEUE) from the front. Like a queue at a shop.

Image to insert

Две диаграммы рядом: (1) Stack — вертикальный столбик элементов, стрелки PUSH (вверх) и POP (вниз), TOP указатель; (2) Queue — горизонтальная очередь, ENQUEUE справа, DEQUEUE слева, FRONT и REAR указатели.

Поиск: "stack LIFO queue FIFO data structure diagram push pop enqueue dequeue"

Stack Operations

PUSH(x) — add x to the top
POP() — remove & return top element
PEEK/TOP() — view top without removing
isEmpty() — check if stack is empty
Stack overflow — pushing to a full stack
Stack underflow — popping from empty stack

Queue Operations

ENQUEUE(x) — add x to the rear
DEQUEUE() — remove & return front element
PEEK/FRONT() — view front without removing
isEmpty() — check if queue is empty
Overflow — enqueueing to a full queue
Underflow — dequeueing from empty queue

★ Stack Example — Bracket Checker

Expression: ( { [ ] } )
Stack trace:
( → PUSH  → Stack: [(]
{ → PUSH  → Stack: [(, {]
[ → PUSH  → Stack: [(, {, []
] → POP   → Stack: [(, {]    (matched with [)
} → POP   → Stack: [(]       (matched with {)
) → POP   → Stack: []        (matched with ()
Stack empty → BALANCED ✓

Expression: ( [ ) ]
( → PUSH → Stack: [(]
[ → PUSH → Stack: [(, []
) → POP  → Stack: [(]  (but [ ≠ ) → NOT BALANCED ✗

★ Queue Example — Print Queue Simulation

Documents arrive: Doc1, Doc2, Doc3, Doc4

ENQUEUE Doc1 → Queue: [Doc1]
ENQUEUE Doc2 → Queue: [Doc1, Doc2]
ENQUEUE Doc3 → Queue: [Doc1, Doc2, Doc3]
DEQUEUE → Print Doc1 → Queue: [Doc2, Doc3]
ENQUEUE Doc4 → Queue: [Doc2, Doc3, Doc4]
DEQUEUE → Print Doc2 → Queue: [Doc3, Doc4]
# Doc1 was added first → printed first (FIFO)

Stack — Real Applications

Undo/Redo in text editors
Browser back button history
Function call stack (recursion)
Bracket/parenthesis checking
Expression evaluation

Queue — Real Applications

Print spooling (print queue)
CPU process scheduling
Keyboard input buffer
Network packet queue
Ticket booking systems

🧩 Task 11 — Stack trace

Perform these operations on an empty stack. Show the stack state after each:

PUSH 5 → PUSH 3 → PUSH 8 → POP → PUSH 2 → POP → PEEK

[5] → [5,3] → [5,3,8] → [5,3] (popped 8) → [5,3,2] → [5,3] (popped 2) → PEEK = 3

🧩 Task 12 — Queue trace

Perform: ENQUEUE A → ENQUEUE B → DEQUEUE → ENQUEUE C → ENQUEUE D → DEQUEUE → DEQUEUE

What are the three dequeued values and in what order?

Queue: [A] → [A,B] → [B] (dequeued A) → [B,C] → [B,C,D] → [C,D] (dequeued B) → [D] (dequeued C). Dequeued: A, B, C

2.7 Binary Tree

📌 Binary Tree

A hierarchical data structure where each node has at most two children: a left child and a right child. The topmost node is the root. Nodes with no children are leaves.

📌 Binary Search Tree (BST)

A binary tree where: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This property enables efficient searching.

Image to insert

BST диаграмма: корень 50, левое поддерево (30 → 20, 40), правое поддерево (70 → 60, 80). Подписи: Root, Left child, Right child, Leaf nodes. Стрелки от родителя к детям.

Поиск: "binary search tree diagram root leaf nodes example 50"

📋 Inserting into a Binary Search Tree

Start at the root.
If new value < current node → go LEFT.
If new value > current node → go RIGHT.
If the position is empty → insert the new node here.
If new value = current node → handle as duplicate (usually ignore or go right).

★ Example — Build BST from: 50, 30, 70, 20, 40, 60, 80

Insert 50 → root
Insert 30 → 30 < 50 → left of 50
Insert 70 → 70 > 50 → right of 50
Insert 20 → 20 < 50 → left; 20 < 30 → left of 30
Insert 40 → 40 < 50 → left; 40 > 30 → right of 30
Insert 60 → 60 > 50 → right; 60 < 70 → left of 70
Insert 80 → 80 > 50 → right; 80 > 70 → right of 70

Final BST:
            50
          /    \
        30      70
       /  \    /  \
      20  40  60  80

★ Tree Traversals

# Using the tree above: 50, 30, 70, 20, 40, 60, 80

IN-ORDER (Left → Root → Right) → sorted ascending:
    20, 30, 40, 50, 60, 70, 80

PRE-ORDER (Root → Left → Right):
    50, 30, 20, 40, 70, 60, 80

POST-ORDER (Left → Right → Root):
    20, 40, 30, 60, 80, 70, 50

✅ In-order traversal of a BST always gives sorted order!

This is a key property. If you need to verify a BST is correct, perform in-order traversal — the result must be in ascending order.

🧩 Task 13 — Build a BST

Insert these values one by one into an empty BST: 45, 22, 77, 11, 33, 60, 90, 55

Draw the final tree. What is the in-order traversal? How many comparisons to find 55?

Tree: 45 → left:22(11,33) right:77(60→55,90) | In-order: 11,22,33,45,55,60,77,90 | Find 55: 55>45→right(77), 55<77→left(60), 55<60→left(55) → 3 comparisons

3.1 Types of Errors

Error Type	Definition	When detected	Example
Syntax Error	Code violates the grammatical rules of the programming language — the interpreter/compiler cannot understand it	Compile time / before running	`if x = 5` instead of `if x == 5`; missing colon; wrong indentation in Python
Runtime Error (Execution Error)	Code is syntactically correct but causes a crash or exception during execution	During program execution	Division by zero; accessing index out of bounds; opening a file that doesn't exist; calling method on None
Logic Error	Code runs without crashing but produces incorrect results because the algorithm or formula is wrong	When testing / checking output	Using `+` instead of `-`; wrong loop range; off-by-one error; incorrect condition (< vs ≤)

★ Identifying Error Types

# SYNTAX ERROR: missing = sign
if x 5:           # SyntaxError: invalid syntax
    print("yes")

# RUNTIME ERROR: division by zero
total = 100
count = 0
avg = total / count   # ZeroDivisionError!

# LOGIC ERROR: wrong formula for circle area
import math
radius = 5
area = math.pi * radius   # WRONG — should be radius**2
print(area)               # Runs but gives wrong answer: 15.7 instead of 78.5

⚠️ Logic Errors are the Hardest to Find

Syntax errors are caught by the compiler/interpreter immediately. Runtime errors crash the program with an error message. Logic errors are silent — the program runs fine but gives wrong output. They can only be found through careful testing.

🧩 Task 14 — Classify the errors

Identify the error type in each: (a) pint("Hello") (b) A program calculating average gives 200 when answer should be 20 (c) grades = [90,80,70]; print(grades[5])

a) Runtime error (NameError — pint is not defined) | b) Logic error (probably forgot to divide by n) | c) Runtime error (IndexError: list index out of range)

3.2 Testing Methods

📌 Normal (Valid) Data

Data that is within the expected, valid range and type. Tests that the program works correctly under typical conditions.

📌 Extreme (Boundary) Data

Data at the very edges of the valid range — the minimum and maximum allowed values. Tests boundary conditions where off-by-one errors commonly occur.

📌 Erroneous (Invalid) Data

Data that is outside the valid range, wrong type, or deliberately incorrect. Tests that the program rejects invalid input gracefully without crashing.

★ Testing Plan — Age Input (valid range: 0–120)

Test #	Data Type	Input	Expected Output	Reason
1	Normal	25	Accepted	Typical valid age
2	Normal	45	Accepted	Another typical valid age
3	Extreme	0	Accepted	Minimum valid age (boundary)
4	Extreme	120	Accepted	Maximum valid age (boundary)
5	Erroneous	-1	Error message	Below minimum — invalid
6	Erroneous	121	Error message	Above maximum — invalid
7	Erroneous	"hello"	Error message	Wrong data type — string
8	Erroneous	25.7	Error message	Decimal when integer expected

🧩 Task 15 — Design a test plan

Design a test plan for a program that accepts a mark between 0 and 100 (integer) and outputs a grade (A: 90–100, B: 75–89, C: 60–74, D: 0–59). Include at least 8 test cases covering all types.

Normal: 95→A, 80→B, 65→C, 30→D | Extreme: 0→D, 100→A, 90→A, 59→D, 60→C, 74→C, 75→B, 89→B | Erroneous: -1→error, 101→error, "abc"→error

3.3 Good Programming Style

📋 Rules of Good Programming Style

Meaningful variable names: use descriptive names (studentAge not x, totalScore not ts).
Comments and documentation: explain what each section does, especially complex logic.
Consistent indentation: use 4 spaces (Python) or consistent tabs to show code blocks visually.
Avoid magic numbers: use named constants instead of hard-coded values (MAX_SIZE = 100 not 100).
Modular code: break programs into functions/procedures, each doing one task.
Avoid duplication (DRY): Don't Repeat Yourself — use loops and functions instead of copy-pasting code.
Limit line length: keep lines readable (max ~80 characters).
Validate inputs: always check user input before using it.

★ BAD vs GOOD style comparison

❌ Bad Style

x = int(input())
y = int(input())
z = x * y * 3.14159
if z > 100:
    print("big")
else:
    print("small")

✅ Good Style

PI = 3.14159  # constant

# Get dimensions from user
length = int(input("Enter length: "))
width  = int(input("Enter width: "))

# Calculate volume of cylinder
volume = length * width * PI

# Classify volume
THRESHOLD = 100
if volume > THRESHOLD:
    print("Large volume")
else:
    print("Small volume")

🧩 Task 16 — Improve this code

a = int(input())
b = int(input())
c = a + b
d = c / 2
if d >= 50:
    print(1)
else:
    print(0)

Rewrite this code following good programming style rules. Add comments, meaningful names, and improve readability.

Rename: score1, score2, totalScore, averageScore, PASS_MARK=50. Add comments. Print "Pass"/"Fail" instead of 1/0.

4.1 HTML Basics

📌 HTML (HyperText Markup Language)

The standard language for creating web pages. Uses tags (enclosed in < >) to mark up content, defining its structure and meaning. Most tags come in pairs: opening <tag> and closing </tag>.

★ Basic HTML Page Structure

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>My Page Title</title>
  <link rel="stylesheet" href="style.css">
</head>
<body>
  <h1>Welcome to My Website</h1>
  <p>This is a paragraph of text.</p>
</body>
</html>

Essential HTML Tags Reference

Tag	Purpose	Example
`<h1> … <h6>`	Headings (h1=largest, h6=smallest)	`<h2>Section Title</h2>`
`<p>`	Paragraph of text	`<p>Text here.</p>`
`<a href="">`	Hyperlink to another page/URL	`<a href="page.html">Click</a>`
`<img src="">`	Embed an image (self-closing)	`<img src="photo.jpg" alt="desc">`
`<ul> / <ol>`	Unordered / Ordered list container	`<ul><li>Item</li></ul>`
`<li>`	List item (inside ul or ol)	`<li>List item text</li>`
`<table>`	Table container	See table tags below
`<tr>`	Table row	`<tr>…</tr>`
`<th>`	Table header cell (bold, centred)	`<th>Name</th>`
`<td>`	Table data cell	`<td>Asel</td>`
`<div>`	Block container for grouping	`<div class="card">…</div>`
`<span>`	Inline container for styling	`<span class="red">text</span>`
`<br>`	Line break (self-closing)	`Line one<br>Line two`
`<strong>`	Bold text (semantic)	`<strong>Important!</strong>`
`<em>`	Italic text (emphasis)	`<em>Italic text</em>`

★ Complete Example — Student Profile Page

<!DOCTYPE html>
<html><head>
  <title>Student Profile</title>
  <link rel="stylesheet" href="style.css">
</head><body>
  <h1>Student Profile</h1>
  <img src="photo.jpg" alt="Student photo" width="150">
  <h2>Asel Nurova</h2>
  <p>Grade: <strong>12A</strong></p>
  <h3>Subjects</h3>
  <ul>
    <li>Computer Science</li>
    <li>Mathematics</li>
    <li>Physics</li>
  </ul>
  <a href="index.html">Back to Home</a>
</body></html>

🧩 Task 17 — Build an HTML page

Create an HTML page for a school timetable. It should include: (a) a heading "Class Timetable", (b) a table with columns: Day, Subject, Teacher, Room — with 5 rows of data, (c) a link back to the school homepage.

4.2 HTML Forms

📌 HTML Form

A section of a web page allowing users to enter and submit data. Forms use the <form> element containing various input fields. The action attribute specifies where data is sent; method specifies GET or POST.

★ Complete Registration Form Example

<form action="register.php" method="POST">

  <label for="fname">First Name:</label>
  <input type="text" id="fname" name="firstname"
         placeholder="Enter your name" required>

  <label for="email">Email:</label>
  <input type="email" id="email" name="email" required>

  <label for="age">Age:</label>
  <input type="number" id="age" name="age"
         min="0" max="120">

  <label for="grade">Grade:</label>
  <select id="grade" name="grade">
    <option value="11">Grade 11</option>
    <option value="12">Grade 12</option>
  </select>

  <label>Gender:</label>
  <input type="radio" name="gender" value="M"> Male
  <input type="radio" name="gender" value="F"> Female

  <label>Interests:</label>
  <input type="checkbox" name="interest" value="cs"> CS
  <input type="checkbox" name="interest" value="math"> Math

  <label for="notes">Notes:</label>
  <textarea id="notes" name="notes" rows="4"></textarea>

  <input type="submit" value="Register">
  <input type="reset"  value="Clear">

</form>

✅ Input Type Reference

type=	Use case	Special attributes
`"text"`	Single line text input	placeholder, maxlength, required
`"email"`	Email address (validates format)	required
`"password"`	Hidden password input	minlength
`"number"`	Numeric input with min/max	min, max, step
`"date"`	Date picker	min, max
`"radio"`	Choose one option from group	name (same for group), value
`"checkbox"`	Toggle on/off option	checked (default checked)
`"submit"`	Submit button	value (button text)
`"reset"`	Reset all fields to default	value

⚠️ Radio Buttons Must Share the Same name Attribute

Radio buttons in a group MUST have the same name value. This is how the browser knows they are mutually exclusive (only one can be selected at a time). If they have different names, multiple can be selected — making them behave like checkboxes.

🧩 Task 18 — Create a quiz form

Build an HTML form for a quiz about Computer Science. It should include: (a) text field for student name, (b) three multiple-choice questions using radio buttons, (c) a text area for "any comments", (d) submit and reset buttons.

4.3 CSS Stylesheet

📌 CSS (Cascading Style Sheets)

A language that controls the presentation and layout of HTML elements — colours, fonts, spacing, borders, positioning. CSS separates content (HTML) from visual design, allowing one stylesheet to style an entire website.

★ CSS Syntax & Selectors

/* Syntax: selector { property: value; } */

/* Element selector — all h1 tags */
h1 {
    color: #333333;
    font-size: 2rem;
    text-align: center;
}

/* Class selector — elements with class="card" */
.card {
    background-color: #ffffff;
    border: 1px solid #ccc;
    border-radius: 8px;
    padding: 16px;
    margin: 10px;
}

/* ID selector — element with id="header" */
#header {
    background-color: #1a1a2e;
    color: white;
    padding: 20px 40px;
}

/* Descendant selector — p inside a div */
div p {
    line-height: 1.6;
    color: #555;
}

Common CSS Properties Reference

Property	Purpose	Example Values
`color`	Text colour	`red`, `#ff0000`, `rgb(255,0,0)`
`background-color`	Background colour of element	`lightblue`, `#f5f5f5`
`font-family`	Font typeface	`Arial, sans-serif`
`font-size`	Text size	`16px`, `1.2rem`, `large`
`font-weight`	Bold/normal/light	`bold`, `normal`, `700`
`text-align`	Horizontal text alignment	`left`, `center`, `right`
`margin`	Space outside the element border	`10px`, `10px 20px`, `auto`
`padding`	Space inside the element border	`8px`, `10px 20px`
`border`	Element border shorthand	`1px solid black`
`border-radius`	Rounded corners	`5px`, `50%` (circle)
`width / height`	Element dimensions	`200px`, `50%`, `auto`
`display`	Layout behaviour	`block`, `inline`, `flex`, `none`

★ Complete CSS Stylesheet Example — Student Card

/* Reset default browser styles */
* {
    box-sizing: border-box;
    margin: 0;
    padding: 0;
}

body {
    font-family: Arial, sans-serif;
    background-color: #f0f4f8;
    color: #333;
    padding: 20px;
}

h1 {
    font-size: 2rem;
    color: #0d9488;
    text-align: center;
    margin-bottom: 20px;
}

.student-card {
    background-color: white;
    border: 1px solid #ddd;
    border-radius: 12px;
    padding: 24px;
    max-width: 400px;
    margin: 0 auto;
    box-shadow: 0 4px 12px rgba(0,0,0,0.1);
}

.student-card img {
    width: 100px;
    height: 100px;
    border-radius: 50%;
    display: block;
    margin: 0 auto 16px;
}

.badge {
    background-color: #0d9488;
    color: white;
    padding: 4px 12px;
    border-radius: 20px;
    font-size: 0.8rem;
    display: inline-block;
}

⚠️ margin vs padding — Know the difference!

Padding = space INSIDE the element, between content and border (affects background colour area). Margin = space OUTSIDE the element, between the border and other elements. Writing margin: 10px 20px means 10px top/bottom, 20px left/right.

★ Inline vs Internal vs External CSS

<!-- 1. INLINE — directly on element (avoid) -->
<p style="color:red; font-size:16px">Red text</p>

<!-- 2. INTERNAL — inside <style> in <head> -->
<head>
  <style>
    p { color: blue; }
  </style>
</head>

<!-- 3. EXTERNAL — separate .css file (BEST PRACTICE) -->
<head>
  <link rel="stylesheet" href="style.css">
</head>

Best practice: always use external CSS. It keeps HTML clean, one file styles all pages, and it is easier to maintain.

🧩 Task 19 — Style the timetable

Write a CSS stylesheet for the HTML timetable page from Task 17. Include: (a) a navy background for the table header row, (b) alternating row colours (white and light grey), (c) a border around all table cells, (d) the page title centred in green, (e) the body using Arial font.

🧩 Task 20 — Full project task

Create a complete 2-page website for a school library system:

Page 1 (index.html): Library homepage with name, navigation links, list of available books as a table (Title, Author, Genre, Available?)

Page 2 (borrow.html): Borrow a book form — student name (text), student ID (number), book title (dropdown select from 5 options), borrow date (date input), submit/reset buttons

style.css: Style both pages consistently — matching header colour, table styling, form layout, button colours.

A — Command Words

Command	Expected Response	Marks
STATE / NAME / IDENTIFY	Provide only a specific fact, data structure, or error type. No explanations or justifications are required.	1
WRITE / COMPLETE	Write or complete pseudocode, HTML/CSS code, or SQL/PHP/Prolog queries. Strict attention to exact syntax is required.	2–6
EXPLAIN	State a fact and provide a reason, consequence, or detailed mechanism. Explain why or how exactly an algorithm or code snippet works.	2–3
FILL IN / TRACE	Complete a trace table or build a data structure (e.g., Binary Search Tree). Pay close attention to every single loop iteration and variable update.	3–6

B — Topic Frequency (2023–2025)

Topic	2023	2024	2025	Priority
Trace Tables (LMC, Assembly, Pseudocode)	✓	✓	✓	🔴 Critical
HTML (Forms, Inputs, Tags)	✓	✓	✓	🔴 Critical
Arrays (1D & 2D) & Loops	✓	✓	✓	🔴 Critical
Binary Search Tree (Building nodes/pointers)	✓	✓	✓	🔴 Critical
Error Types (Syntax, Logic, Runtime)	✓	✓	✓	🔴 Critical
CSS (Selectors, Properties, Inline/Internal)	—	—	✓	🟠 High
Prolog (Facts, Rules, Queries)	✓	—	✓	🟠 High
Sorting Algorithms (Bubble Sort)	—	✓	✓	🟠 High
Stack & Queue (Concepts & Tracing)	✓	✓	✓	🟠 High
Test Data (Normal, Extreme, Erroneous)	—	✓	✓	🟠 High
Algorithm Efficiency / Good Programming Style	—	✓	✓	🟡 Medium
Binary Search (Algorithm / Pseudocode)	—	—	✓	🟡 Medium
PHP / Web Server Basics	✓	—	✓	🟡 Medium

C — All Warnings (Pre-exam Review)

W1 — Prolog Syntax & Case Sensitivity

In Prolog, Variables must always start with an Uppercase letter (e.g., X, Animal). Facts and atoms must always start with a lowercase letter (e.g., almaty, jiger). Examiners strictly deduct marks for facts written with capital letters.

W2 — Trace Tables: Only log changes!

Fill in a cell in a trace table ONLY when the value of the variable has actually changed. Do not duplicate the previous value down the column. Pay special attention to the Output column — write the result there only at the exact moment a PRINT or OUTPUT command is executed in the code.

W3 — Array Bounds & Loops

Remember array boundaries to avoid an "Array Out of Bounds" error. If an array has length N and uses 0-based indexing, the loop must go up to N-1. Going out of bounds is a classic Runtime error. In Bubble Sort tasks, always accurately check the range of the inner loop.

W4 — HTML vs CSS Syntax Confusion

Do not mix up the syntax between languages. In HTML, attributes use an equals sign and quotes: <input type="text">. In CSS, properties use colons and semicolons: color: red;. CSS rules are always wrapped in curly braces {}.

W5 — Knowing Error Types Exactly

Syntax error: The code will not even run or compile (e.g., typographical error, missing bracket).
Runtime error: The code compiles and starts but crashes during execution (e.g., division by zero, reading outside array boundaries).
Logic error: The code runs without crashing but produces the wrong output (e.g., incorrect mathematical formula, using < instead of >).

W6 — Building Binary Search Trees

Build the Binary Search Tree (BST) by taking elements strictly from left to right from the given list. Do not try to pre-sort the array before drawing. The very first element in the list ALWAYS becomes the root node.

W7 — Test Data Identification

Extreme data refers to valid values at the very boundaries of the acceptable range (e.g., if the acceptable range is 1 to 10, then 1 and 10 are Extreme data). Erroneous data refers to values completely outside the acceptable range or of the wrong data type (e.g., 11, or "hello"), which should trigger an error message.

W8 — Good Programming Style

When asked to state rules or features of good programming style (frequently seen in the mark schemes), always use these exact phrases: "meaningful variable names", "indentation", and "use of comments".

Paper 3 — Programming Crash Course

How to use this guide

Contents

Chapter 1 — Programming Paradigms

1.1 Assembly Language & LMC

📌 Assembly Language (2GL)

📌 LMC (Little Man Computer)

LMC Instruction Set

★ Example 1 — Add two numbers entered by user

★ Example 2 — Count down from input to 1

★ Example 3 — Find larger of two numbers

🧩 Task 1 — Analyse this LMC program

⚠️ Common LMC Mistakes

1.2 Trace Tables

📌 Trace Table

📋 How to Complete a Trace Table

★ Example 1 — Trace this algorithm (find max)

★ Example 2 — Trace with counter

🧩 Task 2 — Complete the trace table

🧩 Task 3 — Nested loop trace

1.3 Expert Systems

📌 Expert System

Core Components

Examples & Uses

★ Example 1: Animal Identification (Prolog)

★ Example 2: Medical Diagnosis (Prolog)

🧩 Task 4 — Weather Clothing Advisor in Prolog

Chapter 2 — Algorithms & Data Structures

2.1 Arrays (1D & 2D)

📌 Array

★ 1D Array — Declaration & Access

★ 2D Array — Grid / Matrix

🧩 Task 5 — Array operations

🧩 Task 6 — 2D Array: Class Grades

2.2 Bubble Sort

📌 Bubble Sort

📋 Bubble Sort Algorithm (Pseudocode)

★ Worked Example — Sort [64, 34, 25, 12, 22]

✅ Key Facts for Exam

🧩 Task 7 — Bubble Sort trace

2.3 Insertion Sort

📌 Insertion Sort

📋 Insertion Sort Algorithm (Pseudocode)

★ Worked Example — Sort [12, 11, 13, 5, 6]

Bubble Sort

Insertion Sort

🧩 Task 8 — Insertion Sort trace

2.4 Binary Search

📌 Binary Search

⚠️ Binary search ONLY works on sorted arrays!

📋 Binary Search Algorithm (Pseudocode)

★ Example — Find 33 in [2, 5, 8, 12, 16, 23, 33, 42, 56, 70]

★ Example — Search for 50 in [3, 7, 11, 18, 25, 37, 44, 60] (not found)

✅ Binary vs Linear Search

🧩 Task 9 — Binary Search trace

2.5 Algorithm Efficiency

📌 Time Efficiency

📌 Space Efficiency

Image to insert

✅ Identifying Complexity from Code

🧩 Task 10 — Identify time complexity

2.6 Stack & Queue

📌 Stack

📌 Queue

Image to insert

Stack Operations

Queue Operations

★ Stack Example — Bracket Checker

★ Queue Example — Print Queue Simulation

Stack — Real Applications

Queue — Real Applications

🧩 Task 11 — Stack trace

🧩 Task 12 — Queue trace

2.7 Binary Tree

📌 Binary Tree

📌 Binary Search Tree (BST)

Image to insert

📋 Inserting into a Binary Search Tree

★ Example — Build BST from: 50, 30, 70, 20, 40, 60, 80

★ Tree Traversals