Computer Science 9618/42 — October/November 2022

Background Concept

In Paper 4, a 2D array in pseudocode is usually implemented in Python using a list of lists. Here, ARRAY[0:99, 0:1] OF INTEGER means 100 rows and 2 columns. Each row stores one job record:

• column 0 = job number
• column 1 = priority

A global variable is one that can be accessed throughout the program. NumberOfJobs is used to keep track of how many rows are currently filled with valid data.

Understanding the Question

You are not being asked to write any processing yet. You only need to create:

• a global 2D structure called Jobs
• a global variable called NumberOfJobs

The structure must be large enough for 100 jobs, and each job needs exactly 2 integer positions.

Approach

Use a nested list:

• the outer list gives the 100 rows
• each inner list gives the 2 columns

Then create NumberOfJobs and set it to 0, because at the start there are no jobs stored.

Step-by-Step Reasoning

Jobs = [[0 for Column in range(2)] for Row in range(100)]

• range(100) creates 100 rows.
• range(2) creates 2 columns in each row.
• Every element is initially set to 0.
• This gives a structure equivalent to the required 2D integer array.

NumberOfJobs = 0

• This means no jobs have been stored yet.
• Later, when a job is added, this variable will increase.

Even though part (b) later changes every element to -1, it is still correct here to declare the array with initial values such as 0, because part (a) is only about declaration.

Key Takeaways

• A pseudocode 2D array can be represented in Python as a list of lists.
• The first dimension is the number of rows; the second is the number of columns.
• A separate counter variable is often used to track how many entries are valid.

Common Mistakes

• Creating the wrong size array, such as 99 rows instead of 100.
• Forgetting that there are 2 columns per job.
• Not declaring NumberOfJobs at all.
• Using a one-dimensional list instead of a two-dimensional structure.

Things to Be Careful About

• Jobs[0][0] is the first job number and Jobs[0][1] is its priority, so each row must contain exactly two values.
• Avoid Jobs = [[0, 0]] * 100 in teaching contexts, because it creates repeated references to the same inner list; a list comprehension is safer.
• Keep the identifier names exactly as required: Jobs and NumberOfJobs.

Background Concept

Initialisation means putting a data structure into a known starting state before the rest of the program uses it. For arrays, this often means assigning a default value to every element. For counters, it usually means setting them back to zero.

Because Jobs is two-dimensional, every cell must be visited. That is why nested loops are needed:

• outer loop for rows
• inner loop for columns

Understanding the Question

The question tells you exactly what Initialise() must do:

• store -1 in every element of the Jobs array
• assign 0 to NumberOfJobs

So this is not just resetting the count; it is also clearing all stored job numbers and priorities.

Approach

Write a procedure named Initialise() that:

1. accesses the global array and global counter
2. loops through all 100 rows
3. loops through both columns in each row
4. stores -1 in each position
5. resets NumberOfJobs to 0

Step-by-Step Reasoning

def Initialise():

• Defines the procedure with the exact required name.

global Jobs, NumberOfJobs

• The procedure changes global data, so it should explicitly refer to the global variables.

for Row in range(100):

• Visits rows 0 to 99.

for Column in range(2):

• Visits columns 0 and 1.

Jobs[Row][Column] = -1

• Places -1 in every cell.
• After both loops finish, all 200 array elements have been cleared.

NumberOfJobs = 0

• Resets the count of valid jobs.
• This is essential, because even if the array is cleared, the program must also know that no jobs are currently stored.

Key Takeaways

• Initialisation puts program data into a predictable starting state.
• A 2D array needs nested loops if every element must be processed.
• Resetting the counter is just as important as clearing the data values.

Common Mistakes

• Only setting one row or one column to -1.
• Forgetting to reset NumberOfJobs.
• Writing one loop instead of nested loops.
• Using the wrong loop bounds, such as range(99) or range(1, 100).

Things to Be Careful About

• The valid row indices are 0 to 99, so range(100) is correct.
• The valid column indices are 0 and 1, so range(2) is correct.
• Do not set NumberOfJobs inside the loops; it should be reset once after clearing the array.
• In Python, changing a global scalar such as NumberOfJobs inside a procedure needs the global declaration.

Background Concept

When data is stored in an array using a counter, the next free position is usually the position indicated by the counter. After storing the new item, the counter is increased.

This is a common pattern:

1. check there is space
2. store the new data
3. update the count
4. report success or failure

Because the array has 100 rows, the program must not try to store data once NumberOfJobs reaches 100.

Understanding the Question

AddJob() must do four things:

• receive a job number and a priority as parameters
• store them in the next free row of Jobs
• print Added if successful
• print Not added if the array is full

The important phrase is “next free array element”. That tells you to use NumberOfJobs as the row index.

Approach

Use an if statement:

• if NumberOfJobs < 100, there is room
• write the job number into column 0
• write the priority into column 1
• increase NumberOfJobs
• print Added

Otherwise, print Not added.

Step-by-Step Reasoning

def AddJob(JobNumber, Priority):

• The procedure takes exactly the two required parameters.

global Jobs, NumberOfJobs

• The procedure needs to change the main program's data.

if NumberOfJobs < 100:

• Valid rows go from 0 to 99.
• So if 100 jobs are already stored, there is no free row left.

Jobs[NumberOfJobs][0] = JobNumber

• Stores the job number in the first column of the next free row.

Jobs[NumberOfJobs][1] = Priority

• Stores the matching priority in the second column of the same row.
• Keeping both pieces of data in the same row is essential.

NumberOfJobs += 1

• The row is now occupied, so the number of valid jobs increases by 1.

print('Added')

• Confirms success.

else: / print('Not added')

• This handles the full-array case.

Key Takeaways

• A counter often points to the next free array position.
• Always check bounds before storing into a fixed-size array.
• Related values must be stored in the same row so the record stays together.

Common Mistakes

• Using <= 100 instead of < 100, which allows an invalid row index.
• Incrementing NumberOfJobs before storing, which skips row 0.
• Storing the job number and priority in different rows.
• Printing Added even when the array is full.

Things to Be Careful About

• The array size is 100 rows, so the last valid insert position is row 99.
• NumberOfJobs is the count of used rows, not the last used index.
• Keep the column positions correct: 0 for job number, 1 for priority.
• In Python, remember that updating NumberOfJobs inside the procedure requires global NumberOfJobs.

Background Concept

The main program controls the sequence in which procedures are called. In a procedural program, correctness often depends on calling routines in the right order.

Here, Initialise() must run before adding jobs, otherwise the array and counter may contain old values.

Understanding the Question

You must write the main program code to:

1. call Initialise()
2. add five jobs
3. use the exact job numbers and priorities given
4. keep the exact order shown in the table

The order matters because the jobs are first stored in that sequence, and later the sort uses those stored records.

Approach

This is just a series of procedure calls:

• first clear the array
• then call AddJob() once for each row in the table

Each call passes two values:

• the job number
• the priority

Step-by-Step Reasoning

Initialise()

• Clears the array and sets NumberOfJobs to 0.

AddJob(12, 10)

• Stores job number 12 with priority 10.

AddJob(526, 9)

• Stores the next job.

AddJob(33, 8)

• Stores the third job.

AddJob(12, 9)

• Stores another job number 12; duplicate job numbers are not forbidden by the question.

AddJob(78, 1)

• Stores the final job.

Because all five calls are within the 100-job limit, each one will print Added.

Key Takeaways

• The main program often just sequences procedure calls.
• Use the exact data given in the question.
• Do not change the order unless the task explicitly says to.

Common Mistakes

• Forgetting to call Initialise() first.
• Putting the jobs in a different order.
• Swapping job number and priority in a call.
• Missing one of the five AddJob() calls.

Things to Be Careful About

• AddJob(12, 10) means job number 12, priority 10, not the other way around.
• There are two jobs with job number 12; that is allowed here.
• This part does not yet sort or print the final array. It only initialises and adds the jobs.

Background Concept

Insertion sort builds a sorted section of the array from left to right. At each step:

1. take the next item
2. compare it with items before it
3. shift larger items right
4. insert the item into the gap

In this question, each row is a record containing two linked values:

• job number
• priority

So you are not sorting single numbers. You are sorting records based on the priority field, which is in column 1. Whenever a row moves, both fields must move together.

Understanding the Question

The array must be sorted into ascending numerical order of priority:

• smaller priority number comes first
• so priority 1 is before 8, 9, or 10

The phrase “using an insertion sort” means you must code that algorithm, not use Python's built-in sorting methods.

Also, only the jobs currently stored should be sorted. The rest of the array contains unused values such as -1 and must not be included.

Approach

Use standard insertion sort over rows 0 to NumberOfJobs - 1:

• start at row 1
• save that row's job number and priority
• move left while earlier priorities are larger
• shift rows right to make space
• insert the saved row

The key comparison is Jobs[Pointer][1] > CurrentPriority because column 1 is the priority column.

Step-by-Step Reasoning

for Count in range(1, NumberOfJobs):

• The first row by itself is already considered sorted.
• So insertion sort begins at the second stored row.
• Using NumberOfJobs ensures only valid jobs are sorted.

CurrentJob = Jobs[Count][0]
CurrentPriority = Jobs[Count][1]

• Save the full record currently being inserted.
• You need both values, not just the priority.

Pointer = Count - 1

• Start comparing with the row immediately before the current one.

while Pointer >= 0 and Jobs[Pointer][1] > CurrentPriority:

• Move left while earlier priorities are larger.
• Because the sort is ascending, larger priorities must shift right.
• Using > rather than >= makes the sort stable, so equal priorities stay in their original order.

Jobs[Pointer + 1][0] = Jobs[Pointer][0]
Jobs[Pointer + 1][1] = Jobs[Pointer][1]

• Shift the whole row one place to the right.
• This is vital: the job number must stay attached to its priority.

Pointer -= 1

• Continue checking earlier rows.

After the loop ends, the correct insertion position is Pointer + 1.

Jobs[Pointer + 1][0] = CurrentJob
Jobs[Pointer + 1][1] = CurrentPriority

• Place the saved record into the gap.

Key Takeaways

• Insertion sort works by inserting one item at a time into an already sorted section.
• When sorting records, move the entire record, not just the key field.
• Limit processing to the used portion of the array with NumberOfJobs.

Common Mistakes

• Sorting all 100 rows instead of only the used rows.
• Comparing the job number instead of the priority.
• Moving only the priority and leaving the job number behind.
• Using Python's built-in sort instead of coding insertion sort.
• Getting the sort direction wrong and producing descending order.

Things to Be Careful About

• The key field is Jobs[row][1], not Jobs[row][0].
• If you include unused -1 rows in the sort, they will move to the front and corrupt the result.
• Keep CurrentJob and CurrentPriority together throughout the insertion.
• Using > rather than >= preserves the order of equal priorities, which matches the expected output here.

Background Concept

Output routines often loop through stored records and print selected fields in a required format. When an array is only partly full, the loop must stop at the current number of valid records, not at the physical size of the array.

Understanding the Question

PrintArray() must output each stored job on its own line in this form:

jobNumber priority priorityValue

For example:

123 priority 1

So the procedure must print:

• the job number from column 0
• the word priority
• the priority from column 1

for every stored job.

Approach

Use a loop from 0 to NumberOfJobs - 1 and print one formatted line per row.

Do not print all 100 rows, because most of them are unused.

Step-by-Step Reasoning

def PrintArray():

• Defines the required procedure.

for Count in range(NumberOfJobs):

• Loops over just the valid rows.
• If 5 jobs have been stored, this gives rows 0 to 4.

print(f'{Jobs[Count][0]} priority {Jobs[Count][1]}')

• Jobs[Count][0] is the job number.
• Jobs[Count][1] is the priority.
• The literal word priority is placed between them to match the required output format.

Key Takeaways

• Use the logical size of the data (NumberOfJobs), not the maximum capacity.
• Output formatting matters in Paper 4.
• Each row in the 2D array represents one complete job record.

Common Mistakes

• Looping through all 100 rows and printing unused -1 values.
• Printing the columns in the wrong order.
• Printing the Python list itself, such as [12, 10], instead of the required format.
• Omitting the word priority.

Things to Be Careful About

• The line format must match the question example closely.
• range(NumberOfJobs) is correct because Python stops before the upper bound.
• If the array has not been sorted yet, PrintArray() will print jobs in insertion order, not priority order.