Chapter 3: Advanced Control Structures

Section 3.1

Nested Control Structures

Placing a control structure inside another is called a nested structure. A nested conditional statement decides whether to enter another conditional statement based on the result of the previous condition.

Pattern 1: Nested in the else-branch

Pseudocode / Python

if condition1:
    body1
elif condition2:
    body2
elif condition3:
    body3
else:
    else_body

Nested equivalent

if condition1:
    body1
else:
    if condition2:
        body2
    else:
        if condition3:
            body3
        else:
            else_body

Pattern 2: Nested in any branch

A conditional statement can be nested in not only the 'else' branch but also other branches, allowing complex decision trees.

if condition1:
    if condition2:   # nested inside if-branch
        body2
else:
    if condition3:   # nested inside else-branch
        body3

Example: Triangle Classifier

Given three side lengths a, b, c — classify the triangle type:

Input a, b, c
if a <= 0 OR b <= 0 OR c <= 0 then
    Output "Cannot form a triangle"
else if a+b <= c OR a+c <= b OR b+c <= a then
    Output "Cannot form a triangle"
else
    if a=b AND b=c then
        Output "Equilateral triangle"
    else if a=b OR b=c OR a=c then
        Output "Isosceles triangle"
    else
        Output "Scalene triangle"

Triangle Inequality A valid triangle requires: any two sides' sum > the third side. Check ALL three combinations.

Section 3.2

Nested Loops

Placing a loop inside another loop is called a nested loop. Each time the outer loop body executes once, the inner loop body executes completely.

Clock Analogy A clock works just like a nested loop: the 'minute' hand is the outer loop body, and the 'second' hand is the inner loop body. When a minute passes (outer loop advances by 1), the second hand has made a full rotation (inner loop runs 60 times).

Nested for Loop Structure

Pseudocode

for i from 0 to 1
    Output i         # outer body
    for j from 0 to 2
        Output j     # inner body

Python

for i in range(0, 2):
    print(i)
    for j in range(0, 3):
        print(j)

Key Rule: Total Repetitions

Total repetitions of inner loop body = Repetitions of outer loop body × Repetitions of inner loop body

Trace Table: Nested for Loop

For the example above (i: 0→1, j: 0→2), the trace table is:

Line	i	j	Output	Note
for i←0	0
Output i			0
for j←0		0
Output j			0	Inner (i=0)
for j←1		1
Output j			1
for j←2		2
Output j			2
for i←1	1
Output i			1
for j←0		0
Output j			0	Inner (i=1)
for j←1		1
Output j			1
for j←2		2
Output j			2

Each time the outer loop body (i=0, i=1) executes once, the inner loop body executes 3 times. Total inner body executions = 2 × 3 = 6.

Example 3.1: Drawing a Square with *

Design an algorithm to draw a square of * with side length L.

# Pseudocode
Input L
for i from 1 to L
    for j from 1 to L
        Output "*"
    Output Newline character

# Python
L = int(input())
for i in range(0, L):
    for j in range(0, L):
        print("*", end="")
    print()

Python print() tip By default, print() adds a newline after printing. Use end='' to suppress the newline and print on the same line. Use print() with no arguments to output a blank newline.

Section 3.3

Nested Loops and Two-Dimensional Arrays

We often use a nested for loop to access items in a two-dimensional array one by one. The outer loop iterates over rows (i), and the inner loop iterates over columns (j).

Traversal Pattern

Row-first (common)

for i from 0 to 2
    for j from 0 to 5
        num[i,j] ← i * j

Column-first (alternative)

for j from 0 to 5
    for i from 0 to 2
        num[i,j] ← i * j

Initialisation of 2D Lists in Python

Before accessing items in a 2D list, you must first create it and assign default values. This process is called initialisation.

# Create a 3×6 2D list, all zeros
num = []
for i in range(0, 3):
    num = num + [[]]          # add an empty row
    for j in range(0, 6):
        num[i] = num[i] + [0]  # add 0 to each column
        num[i][j] = i * j

Example 3.2: Bookshelf Sum

Jonathan's bookshelf is a 3×6 2D array B. B[i,j] stores the number of books. Calculate the total.

	j=0	j=1	j=2	j=3	j=4	j=5
i=0	5	9	6	5	3	4
i=1	2	3	8	2	6	5
i=2	8	3	5	3	9	9

total ← 0
for i from 0 to 2
    for j from 0 to 5
        total ← total + B[i,j]
Output total   # = 96

Application: Image Manipulation with 2D Arrays

Photos are lattices of pixels. Each pixel's colour can be represented as an integer. Using 2D arrays and nested loops, we can perform image operations like:

Rotate — rearrange pixel positions
Flip — mirror pixel values horizontally or vertically
Scale — resize by duplicating or removing pixels
Pattern matching — compare sub-arrays to find shapes

# Flip image horizontally (mirror left-right)
# art[i,j] ← art[i, 7-j] for an 8×8 array
for i from 0 to 7
    for j from 0 to 7
        art[i, 7-j] ← art[i, j]

Section 3.4

Integrated Application of Control Structures

Control structures (sequence, selection, iteration) can be combined with data structures (1D/2D arrays) to form multi-layered nested structures. This allows us to design algorithms that solve complex real-world problems.

Example: Bingo Game — Check Row Win

A 5×5 Bingo grid is stored in 2D array result[i,j]. True = drawn, False = not drawn. Check if any row is fully crossed.

win ← False
for i from 0 to 4
    row ← True
    for j from 0 to 4
        if result[i,j] = False then
            row ← False
    if row = True then
        win ← True
Output win

Example: Password Verification

password ← "iloveict"
Input input_pw
correct ← True
for j from 1 to length of password
    if length of password ≠ length of input_pw
        OR input_pw[j] ≠ password[j] then
        correct ← False
Output correct

Example: Word Search (Row Search)

Search for a word horizontally in a 10×10 letter grid:

word = input()
found = False
for i in range(10):         # rows
    for j in range(10):     # starting column
        if puzzle[i][j] == word[0] and found == False:
            found = True
            for k in range(0, len(word)):
                if j+k >= 10 or puzzle[i][j+k] != word[k]:
                    found = False
print(found)

Example: Tic-Tac-Toe — 2D to 1D Conversion

Copy a 3×3 2D array ttt_2d to a 1D array ttt_1d row by row:

# Index formula: ttt_1d[(i-1)*3 + j] = ttt_2d[i,j]
for i from 1 to 3
    for j from 1 to 3
        ttt_1d[(i-1)*3 + j] ← ttt_2d[i,j]

For an m×n 2D array, the 1D index formula is: (i-1)×n + j, where i is the row and j is the column.

Section 3.5

Algorithm Comparison

A problem can often be solved using several algorithms. We compare algorithms to select the most correct and appropriate solution. Algorithms can be compared in two main aspects: steps of operation and resource usage.

Time Complexity (時間複雜度)

More steps of operation → longer running time → higher time complexity. Fewer steps = more efficient.

Space Complexity (空間複雜度)

More computer resources (memory, variables) used → higher space complexity. Different data structures affect space usage.

Criteria for Algorithm Comparison

Criterion	Description	Key Question
Correctness	Does the algorithm produce the right answer for all valid inputs?	Are there edge cases it fails?
Appropriateness	Is the algorithm suitable for the given problem constraints?	Does it handle all required cases?
Steps of Operation	How many operations does the algorithm perform?	Which algorithm is faster?
Resource Usage	How much memory/variables does the algorithm use?	Which algorithm uses less memory?
Data Structures	What data structures does the algorithm use?	Are they appropriate for the problem?

Case Study: Finding a Missing Item (3 Algorithms)

A box should contain items A to A+9. One item is missing. Array C stores the actual items. Find the missing item number.

Algorithm 1 (Sum)

weight ← 0
for i from A to A+9
    weight ← weight + i
total ← 0
for j from 0 to 8
    total ← total + C[j]
Output weight-total

Steps~20

Variables2

Special cases?No

Algorithm 2 (Search)

for i from A to A+9
    found ← False
    for j from 0 to 8
        if C[j]=i then
            found ← True
    if found=False then
        Output i

Steps~100

Variables1

Special cases?Yes

Algorithm 3 (Boolean Array)

for i from A to A+9
    found[i] ← False
for i from 0 to 8
    found[C[i]] ← True
for i from A to A+9
    if found[i]=False then
        Output i

Steps~30

Variablesfound[]

Special cases?Yes

Trade-off Analysis

Algorithm 1 is fastest (fewest steps) but cannot handle special cases (e.g., duplicate items).
Algorithm 3 is faster than Algorithm 2 (avoids nested loop) and handles special cases, but uses more memory (boolean array).
Algorithm 2 uses the least memory but is slowest due to the nested loop (~100 steps).

Interactive Quiz

Test Your Knowledge

Answer all 12 questions then click Submit to see your score.

Q1. Placing a control structure inside another is called:

A. An integrated structure

B. A nested structure

C. A recursive structure

D. A sequential structure

Q2. The outer loop runs 4 times and the inner loop runs 5 times per outer iteration. How many times does the inner loop body execute in total?

A. 4

B. 5

C. 9

D. 20

Q3. In Python, to print on the same line without a newline, you use:

A. print("*", newline=False)

B. print("*", end="")

C. print("*", sep="")

D. print("*", stop=True)

Q4. What must be done before accessing items in a 2D list in Python?

A. Declare the list type

B. Initialise the list with default values

C. Import the array module

D. Define the maximum size

Q5. For a nested for loop: for i in range(0,3): for j in range(0,4): — how many total inner loop body executions?

A. 3

B. 4

C. 7

D. 12

Q6. In a nested loop analogy, the clock's 'second hand' corresponds to:

A. The outer loop body

B. The inner loop body

C. The loop counter

D. The loop condition

Q7. To access element at row 2, column 3 in a 2D array called grid, you write:

A. grid[3][2]

B. grid(2,3)

C. grid[2][3]

D. grid[2,3]

Q8. Time complexity refers to:

A. The amount of memory an algorithm uses

B. The number of steps/operations an algorithm performs

C. The time it takes to write the algorithm

D. The correctness of the algorithm

Q9. Which control structures can programs be broadly divided into?

A. Input, Process, Output

B. Sequence, Selection, Iteration

C. Linear, Binary, Recursive

D. If, For, While

Q10. In the missing item case study, Algorithm 1 is more efficient than Algorithm 2 because:

A. It uses more variables

B. It has fewer steps (no nested loop)

C. It handles more special cases

D. It uses a 2D array

Q11. A 3×5 2D array is copied to a 1D array row by row. What is the 1D index of element [2][3]? (rows and columns start from 1)

A. 6

B. 7

C. 8

D. 13

Q12. Space complexity increases when an algorithm:

A. Uses fewer loops

B. Has more conditional statements

C. Uses more computer resources (memory/variables)

D. Produces incorrect output

0/12

Past Questions

Exam Practice

Filter by difficulty and click 'View Reference Answer' to see model answers.

BasicChapter Exercise

The map array stores population (thousands) in a 5×7 grid. (a) What is the total population? (b) Write the algorithm to calculate it.

Reference Answer:

(a) Total = 96 (thousands)

(b) population←0; for i from 1 to 5; for j from 1 to 7; population←population+map[i,j]; Output population

BasicActivity 3.2

For the nested loop: for i from 1 to 5 / for j from 1 to 6 / Output i*j — state the repetitions of (a) outer loop body, (b) inner loop body per outer iteration, (c) total inner loop body executions.

Reference Answer:

(a) 5 times. (b) 6 times per outer iteration. (c) 5 × 6 = 30 total.

MediumChapter Exercise

Mr Wong uses 2D array form5_chi to store F5 Chinese exam marks. Each row = a class (5A–5D), each column = a student (0–9). (a) Write algorithm to count students who failed (mark < 50). (b) Write Python to find the highest mark.

Reference Answer:

(a) fail←0; for i from 0 to 3; for j from 0 to 9; if form5_chi[i][j] < 50: fail+=1; print(fail)

(b) highest_mark = form5_chi[0][0]; for i in range(4): for j in range(10): if form5_chi[i][j] > highest_mark: highest_mark = form5_chi[i][j]

MediumCheckpoint 3.2

Marco defines a 2D array M for the multiplication table, M[i,j] = i×j. Design an algorithm to fill in the whole multiplication table (i, j from 1 to 10).

Reference Answer:

for i from 1 to 10; for j from 1 to 10; M[i,j] ← i * j

HardChapter Exercise

Candice uses a 3×3 array human to represent a human image pattern. She writes an algorithm to count occurrences of human in a 4×8 photo array. Complete the pseudocode: match←___; for p from 1 to 3; for q from 1 to 3; if human[p,q] ≠ photo[i+p-1, j+q-1] then match←___; Output match

Reference Answer:

match←True; for p from 1 to 3; for q from 1 to 3; if human[p,q] ≠ photo[i+p-1, j+q-1] then match←False; Output match. Blanks: True, p, q, i+p-1, j+q-1, False.

HardCheckpoint 3.4

In the missing item problem (Algorithm 2 vs Algorithm 3): (i) Explain the advantage of Algorithm 3 over Algorithm 2. (ii) Explain the advantage of Algorithm 1 over Algorithm 3. (iii) Which of Algorithm 1 and 2 is more efficient in terms of steps?

Reference Answer:

(i) Algorithm 3 uses ~30 steps vs Algorithm 2's ~100 steps. Algorithm 3 is more time-efficient.

(ii) Algorithm 1 uses only 2 variables vs Algorithm 3's boolean array. Algorithm 1 has lower space complexity.

(iii) Algorithm 1 is more efficient (~20 steps vs ~100 steps).

Advanced Control Structures

What You Will Learn

Nested Control Structures

Pattern 1: Nested in the else-branch

Pattern 2: Nested in any branch

Example: Triangle Classifier

Nested Loops

Nested for Loop Structure

Key Rule: Total Repetitions

Trace Table: Nested for Loop

Example 3.1: Drawing a Square with *

Nested Loops and Two-Dimensional Arrays

Traversal Pattern

Initialisation of 2D Lists in Python

Example 3.2: Bookshelf Sum

Integrated Application of Control Structures

Algorithm Comparison

Time Complexity (時間複雜度)

Space Complexity (空間複雜度)

Criteria for Algorithm Comparison

Case Study: Finding a Missing Item (3 Algorithms)

Key Concepts at a Glance

Test Your Knowledge

Q1. Placing a control structure inside another is called:

Q2. The outer loop runs 4 times and the inner loop runs 5 times per outer iteration. How many times does the inner loop body execute in total?

Q3. In Python, to print on the same line without a newline, you use:

Q4. What must be done before accessing items in a 2D list in Python?

Q5. For a nested for loop: for i in range(0,3): for j in range(0,4): — how many total inner loop body executions?

Q6. In a nested loop analogy, the clock's 'second hand' corresponds to:

Q7. To access element at row 2, column 3 in a 2D array called grid, you write:

Q8. Time complexity refers to:

Q9. Which control structures can programs be broadly divided into?

Q10. In the missing item case study, Algorithm 1 is more efficient than Algorithm 2 because:

Q11. A 3×5 2D array is copied to a 1D array row by row. What is the 1D index of element [2][3]? (rows and columns start from 1)

Q12. Space complexity increases when an algorithm:

Key Terms Flashcards

Exam Practice

Key Terms & Definitions