Advanced Algorithms and Recursion: Question 2

Syllabus 19.1

Structured A2 8 marks

A software company implements two Abstract Data Types (ADTs) using arrays, each with pointer variables to keep track of the current position.

An undo stack for a text editor stores the names of formatting actions the user has applied, so that the most recently applied action can be undone first. It is implemented using this pseudocode:

DECLARE MaxSize : INTEGER
CONSTANT MaxSize ← 5
DECLARE ActionStack : ARRAY[1:MaxSize] OF STRING
DECLARE Top : INTEGER
Top ← 0

PROCEDURE Push(Item : STRING)
    IF Top = MaxSize THEN
        OUTPUT "Stack full"
    ELSE
        Top ← Top + 1
        ActionStack[Top] ← Item
    ENDIF
ENDPROCEDURE

FUNCTION Pop() RETURNS STRING
    DECLARE Removed : STRING
    IF Top = 0 THEN
        OUTPUT "Stack empty"
    ELSE
        Removed ← ActionStack[Top]
        Top ← Top - 1
        RETURN Removed
    ENDIF
ENDFUNCTION

(a) Starting from an empty stack (Top = 0), these calls are made in order:

CALL Push("Bold")
CALL Push("Italic")
CALL Push("Underline")
LastAction ← Pop()
CALL Push("ResizeFont")
NextAction ← Pop()

Complete a trace showing the value of Top after each call, and state the final values of LastAction and NextAction. [4]

A print queue for a shared office printer stores the names of documents waiting to print, so that documents are printed in the order they were sent. It is implemented using this pseudocode:

DECLARE MaxSize : INTEGER
CONSTANT MaxSize ← 5
DECLARE PrintQueue : ARRAY[1:MaxSize] OF STRING
DECLARE Front, Rear : INTEGER
Front ← 0
Rear ← 0

PROCEDURE Enqueue(Item : STRING)
    IF Rear = MaxSize THEN
        OUTPUT "Queue full"
    ELSE
        Rear ← Rear + 1
        PrintQueue[Rear] ← Item
        IF Front = 0 THEN
            Front ← 1
        ENDIF
    ENDIF
ENDPROCEDURE

FUNCTION Dequeue() RETURNS STRING
    DECLARE Removed : STRING
    IF (Front = 0) OR (Front > Rear) THEN
        OUTPUT "Queue empty"
    ELSE
        Removed ← PrintQueue[Front]
        Front ← Front + 1
        RETURN Removed
    ENDIF
ENDFUNCTION

(b) Starting from an empty queue (Front = 0, Rear = 0), these calls are made in order:

CALL Enqueue("Report.docx")
CALL Enqueue("Invoice.pdf")
CALL Enqueue("Timetable.xlsx")
FirstPrinted ← Dequeue()
CALL Enqueue("Poster.png")
SecondPrinted ← Dequeue()

Complete a trace showing the values of Front and Rear after each call, and state the final values of FirstPrinted and SecondPrinted. [4]

Show worked solution Hide worked solution

Part (a): Tracing the stack (push and pop)

A stack is Last-In-First-Out (LIFO): Push adds an item above the current Top position, and Pop removes the item currently at Top.

Call	Top before	What happens	Top after	Stack contents (index : value)
`Push("Bold")`	0	`Top ← 1`; `ActionStack[1] ← "Bold"`	1	1:Bold
`Push("Italic")`	1	`Top ← 2`; `ActionStack[2] ← "Italic"`	2	1:Bold, 2:Italic
`Push("Underline")`	2	`Top ← 3`; `ActionStack[3] ← "Underline"`	3	1:Bold, 2:Italic, 3:Underline
`LastAction ← Pop()`	3	`Removed ← ActionStack[3]` = “Underline”; `Top ← 2`	2	1:Bold, 2:Italic
`Push("ResizeFont")`	2	`Top ← 3`; `ActionStack[3] ← "ResizeFont"` (overwrites the old, already-removed “Underline”)	3	1:Bold, 2:Italic, 3:ResizeFont
`NextAction ← Pop()`	3	`Removed ← ActionStack[3]` = “ResizeFont”; `Top ← 2`	2	1:Bold, 2:Italic

So LastAction = "Underline" and NextAction = "ResizeFont".

[4 marks]: [2] for correctly tracing Top through all six calls, [1] for the correct value of LastAction, [1] for the correct value of NextAction.

Part (b): Tracing the queue (enqueue and dequeue)

A queue is First-In-First-Out (FIFO): Enqueue adds an item at the position after Rear, and Dequeue removes the item at Front, always leaving items already enqueued but not yet printed in their original order.

Call	Front, Rear before	What happens	Front, Rear after
`Enqueue("Report.docx")`	0, 0	`Rear ← 1`; `PrintQueue[1] ← "Report.docx"`; `Front` was 0 so `Front ← 1`	1, 1
`Enqueue("Invoice.pdf")`	1, 1	`Rear ← 2`; `PrintQueue[2] ← "Invoice.pdf"`	1, 2
`Enqueue("Timetable.xlsx")`	1, 2	`Rear ← 3`; `PrintQueue[3] ← "Timetable.xlsx"`	1, 3
`FirstPrinted ← Dequeue()`	1, 3	`Removed ← PrintQueue[1]` = “Report.docx”; `Front ← 2`	2, 3
`Enqueue("Poster.png")`	2, 3	`Rear ← 4`; `PrintQueue[4] ← "Poster.png"`	2, 4
`SecondPrinted ← Dequeue()`	2, 4	`Removed ← PrintQueue[2]` = “Invoice.pdf”; `Front ← 3`	3, 4

So FirstPrinted = "Report.docx" and SecondPrinted = "Invoice.pdf". The remaining documents (“Timetable.xlsx” at index 3 and “Poster.png” at index 4) stay in the order they were sent.

[4 marks]: [2] for correctly tracing Front and Rear through all six calls, [1] for the correct value of FirstPrinted, [1] for the correct value of SecondPrinted.

Final answers

(a) Top: 1, 2, 3, 2, 3, 2. LastAction = "Underline", NextAction = "ResizeFont".
(b) (Front, Rear): (1,1), (1,2), (1,3), (2,3), (2,4), (3,4). FirstPrinted = "Report.docx", SecondPrinted = "Invoice.pdf".

Common mistakes

In (a), popping from a fixed array position such as ActionStack[1] instead of from the position given by Top, forgetting that a stack removes the most recently added item, not the first one added.
In (a), forgetting that CALL Push('ResizeFont') reuses array index 3 (overwriting the old 'Underline' value already removed by the first Pop), and so treating the stack as still holding four separate items afterwards.
In (b), confusing a queue's FIFO behaviour with a stack's LIFO behaviour, e.g. stating that FirstPrinted is 'Timetable.xlsx' (the most recently enqueued item) rather than 'Report.docx' (the first item enqueued).
In (b), incorrectly increasing Front every time Enqueue is called, instead of only setting it once, the first time an item is added to an empty queue.
In (b), forgetting that Dequeue only changes Front and not Rear, and incorrectly decreasing Rear as well when an item is removed.

Worked solution

Part (a): Tracing the stack (push and pop)

Part (b): Tracing the queue (enqueue and dequeue)

Final answers