Skip to content

Course home

Representing algorithms

Representing algorithms

EasyMediumHard
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
Question 61

Run length encoding (RLE) is a lossless compression algorithm that represents consecutive repeating data values as a count and data pair.

For example, the character sequence AAAAABBBCC can be represented as 5 A 3 B 2 C because there are five 'A's, followed by three 'B's, and finally two 'C's.

The algorithm below in Figure 1 is designed to output the RLE pairs for any text sequence entered by a user.

Three parts of the pseudocode labelled L1, L2, and L3 are missing.

  • Note that string indexing starts at zero.

Figure 1

sequence ← USERINPUT
index ← 0
current_run ← 1
WHILE index < LEN(sequence) - 1
    IF sequence[index] == sequence[index + 1] THEN
        current_run ← current_run + 1
    ELSE
        OUTPUT current_run
        OUTPUT sequence[index]
        current_run ← L1
    ENDIF
    L3
ENDWHILE
OUTPUT current_run
OUTPUT sequence[index]

Which code should be written at point L3 of the algorithm to ensure the sequence is processed correctly without causing an infinite loop?

A

index←index+1\text{index} \leftarrow \text{index} + 1index←index+1

B

index←1\text{index} \leftarrow 1index←1

C

current_run←current_run+1\text{current\_run} \leftarrow \text{current\_run} + 1current_run←current_run+1

D

index←index+current_run\text{index} \leftarrow \text{index} + \text{current\_run}index←index+current_run

Markscheme

Representing algorithms Questions

  1. GCSE
  2. /Computer Science
  3. /Representing algorithms

208 exam-style questions on AQA GCSE Computer Science Representing algorithms. Each one has a worked solution and a mark scheme showing where the marks go.

Question bank