Complete paper 2 computer science deck

What is an AND gate?

Outputs 1 only when both inputs are 1 — if either input is 0 the output is 0

What is an OR gate?

Outputs 1 when at least one input is 1 — only outputs 0 when both inputs are 0

What is a NOT gate?

Inverts the input — if input is 1 output is 0 — if input is 0 output is 1 — also called a NOT gate or inverter

Complete the truth table for AND

A=0 B=0 → 0. A=0 B=1 → 0. A=1 B=0 → 0. A=1 B=1 → 1

Complete the truth table for OR

A=0 B=0 → 0. A=0 B=1 → 1. A=1 B=0 → 1. A=1 B=1 → 1

Complete the truth table for NOT

A=0 → 1. A=1 → 0

What is the output of A AND B when A=1 and B=0?

0 — because both inputs must be 1 for AND to output 1

What is the output of A OR B when A=0 and B=1?

1 — because at least one input is 1

What is the output of NOT A when A=1?

0 — NOT inverts the input

Complete the truth table for A AND (NOT B)

A=0 B=0 → NOT B=1 → 0 AND 1 = 0. A=0 B=1 → NOT B=0 → 0 AND 0 = 0. A=1 B=0 → NOT B=1 → 1 AND 1 = 1. A=1 B=1 → NOT B=0 → 1 AND 0 = 0

Complete the truth table for (A OR B) AND (NOT A)

A=0 B=0 → 0 AND 1 = 0. A=0 B=1 → 1 AND 1 = 1. A=1 B=0 → 1 AND 0 = 0. A=1 B=1 → 1 AND 0 = 0

How do you work out the output of a logic diagram with multiple gates?

Work from left to right — calculate the output of each gate in order — use the outputs of earlier gates as inputs to later gates — build up a truth table column by column

What is a high-level programming language?

A language that is closer to human language — easy to read and write — needs to be translated into machine code — eg Python Java C# — more portable and easier to debug

What is a low-level programming language?

A language closer to machine code — harder to read and write — closely tied to the hardware — includes assembly language and machine code — faster and more efficient but harder to program

What are the differences between high-level and low-level languages?

High-level — easy to read — portable — needs translating — slower execution. Low-level — hard to read — hardware specific — faster execution — gives more direct control over hardware

What is a translator?

Software that converts code written in one language into machine code that the computer can execute — needed because computers only understand binary machine code

What is a compiler?

A translator that converts the entire high-level source code into machine code in one go — produces a standalone executable file — the original source code is not needed to run the program

What is an interpreter?

A translator that converts and executes high-level source code one line at a time — does not produce a standalone file — source code is needed every time the program runs

What are the advantages of a compiler?

Faster execution once compiled — source code is hidden in the executable — program can run without the original source code or translator

What are the disadvantages of a compiler?

Errors are only reported after the whole program is compiled — harder to debug — compilation takes time — compiled code may not be portable across different hardware

What are the advantages of an interpreter?

Easier to debug — errors are reported line by line as they occur — useful during development — more portable across platforms

What are the disadvantages of an interpreter?

Slower execution because translation happens every time the program runs — source code must be present to run the program — less secure as source code is exposed

What is an IDE?

Integrated Development Environment — software that provides tools to help programmers write test and debug programs — all tools available in one place

What editor tools does an IDE provide?

A text editor with features like syntax highlighting — auto-completion — auto-indentation — bracket matching — makes writing code faster and reduces errors

What are error diagnostics in an IDE?

Tools that identify and highlight errors in code — syntax errors are underlined or highlighted as you type — error messages explain what went wrong and where

What is a run-time environment in an IDE?

Allows the programmer to run and test their program directly within the IDE — no need for separate software — can observe the program executing

What translator tools does an IDE provide?

Built-in compiler or interpreter — allows the programmer to translate and run their code without leaving the IDE — may allow switching between interpreter and compiler mode

How does an IDE help a programmer produce better code?

Syntax highlighting makes code readable — auto-completion speeds up writing — error diagnostics catch mistakes early — run-time environment allows immediate testing — all tools in one place reduces context switching

What is defensive design?

Writing programs that anticipate and handle misuse — ensuring the program behaves correctly even when given unexpected or invalid inputs — making programs reliable and secure

What is input validation?

Checking that data entered by a user meets specific criteria before it is processed — rejects invalid data and asks the user to re-enter — prevents errors and crashes

Write OCR ERL code that validates a user enters a number between 1 and 10

num = int(input("Enter a number 1-10")). while num < 1 OR num > 10. print("Invalid — try again"). num = int(input("Enter a number 1-10")). endwhile

What is authentication?

Confirming the identity of a user before allowing access — typically using a username and password — prevents unauthorised access

Write OCR ERL code for a simple username and password check

username = input("Username"). password = input("Password"). if username == "admin" AND password == "pass123" then. print("Access granted"). else. print("Access denied"). endif

What are naming conventions and why are they important?

Using clear descriptive names for variables and subprograms — eg totalScore instead of x — makes code easier to read and maintain — allows others to understand the code

What is indentation and why is it important?

Adding spaces or tabs to show the structure of code — makes it clear which statements are inside loops or selection statements — improves readability and maintainability

What is commenting and why is it important?

Adding notes to code using // in OCR ERL — explains what sections of code do — does not affect execution — helps others understand and maintain the code

What is the purpose of using subprograms in terms of maintainability?

Breaks code into smaller named sections — each section can be developed and tested independently — reduces repetition — makes code easier to read update and debug

What is the purpose of testing?

To ensure a program works correctly — identifies and fixes errors before the program is used — checks the program behaves as expected for all possible inputs

What is iterative testing?

Testing modules of a program during development — testing each section as it is written — allows errors to be found and fixed early before they affect other parts

What is final or terminal testing?

Testing the complete finished program at the end of development — checks the whole system works together correctly — checks it meets the original requirements

What is a syntax error and give an example?

An error that breaks the grammatical rules of the programming language — prevents the program from running — eg missing closing bracket — misspelled keyword — missing quotation mark

What is a logic error and give an example?

An error where the program runs but produces incorrect output — eg using > instead of >= causing a boundary to be missed — or an infinite loop due to the wrong condition

What is normal test data?

Data that is valid and within the expected range — should be accepted and processed correctly by the program — eg entering 5 for an input expecting a number between 1 and 10

What is boundary test data?

Data that is on the very edge of what is valid — tests the limits of the program — eg entering exactly 1 or exactly 10 for a range of 1 to 10 — should be accepted

What is invalid test data?

Data of the correct data type but outside the acceptable range — should be rejected by the program — eg entering 0 or 11 for a range of 1 to 10

What is erroneous test data?

Data of the completely wrong data type — should be rejected — eg entering "hello" for a field expecting an integer — tests type checking and validation

Create a test plan for a program that accepts ages between 0 and 120

Normal — enter 25 — expected: accepted. Boundary — enter 0 — expected: accepted. Boundary — enter 120 — expected: accepted. Invalid — enter -1 — expected: rejected. Invalid — enter 121 — expected: rejected. Erroneous — enter "hello" — expected: rejected

What is abstraction?

Removing unnecessary detail from a problem to focus only on the important parts — simplifying complexity to make a problem easier to solve

What is decomposition?

Breaking a complex problem down into smaller more manageable sub-problems — each sub-problem can then be solved individually

What is algorithmic thinking?

Creating a step by step set of instructions to solve a problem — thinking logically about the sequence of steps needed

What is a structure diagram?

A diagram that shows the structure of a problem broken into subsections — shows how subsections link to each other — used in the design stage before coding

What is pseudocode?

An informal way of describing an algorithm using plain English and programming-like structure — not tied to any specific language — used to plan programs before writing real code

What are the flowchart symbols you need to know?

Oval/rounded rectangle — terminal (start/stop). Rectangle — process. Parallelogram — input/output. Diamond — decision. Rectangle with lines on sides — sub program. Arrow — flow of control

What is a trace table?

A table used to track the values of variables at each step of an algorithm — used to manually follow and check the logic of an algorithm — helps identify errors

What is a syntax error?

An error that breaks the grammatical rules of the programming language — prevents the program from being run or translated at all — eg missing bracket or misspelled keyword

What is a logic error?

An error where the program runs without crashing but produces unexpected or incorrect output — the code is syntactically correct but the logic is wrong — eg using < instead of <=

What is nesting?

Placing one selection or iteration construct inside another — eg an IF statement inside a FOR loop — or a WHILE loop inside an IF statement

LINEAR SEARCH

What is a linear search?

Checks each element of a list one by one from the start until the target is found or the end of the list is reached — works on both sorted and unsorted lists

What are the steps of a linear search?

Step 1 — start at the first element. Step 2 — check if the current element equals the target. Step 3 — if yes — return its position. Step 4 — if no — move to the next element. Step 5 — if end of list reached without finding target — return not found

What are the advantages of linear search?

Works on unsorted lists — simple to understand and implement — no pre-conditions required

What are the disadvantages of linear search?

Slow for large lists — must check every element in the worst case — inefficient compared to binary search on sorted data

Apply a linear search to find 15 in the list 8 3 15 22 7

Check 8 — not 15. Check 3 — not 15. Check 15 — found at position 3 (index 2)

Apply a linear search to find 10 in the list 5 12 3 9 6

Check 5 — no. Check 12 — no. Check 3 — no. Check 9 — no. Check 6 — no. End of list — 10 not found

BINARY SEARCH

What is a binary search?

Divides a sorted list in half — compares the middle element to the target — searches the left half if target is smaller — searches the right half if target is larger — repeats until found or not found

What are the steps of a binary search?

Step 1 — find the middle element of the list. Step 2 — if middle equals target — found. Step 3 — if target is less than middle — repeat on left half. Step 4 — if target is greater than middle — repeat on right half. Step 5 — if list is empty — not found

What is the key pre-condition for binary search?

The list must already be sorted — binary search will not work correctly on an unsorted list

What are the advantages of binary search?

Much faster than linear search for large sorted lists — eliminates half the remaining elements each time — very efficient

What are the disadvantages of binary search?

List must be sorted first — more complex to implement than linear search — sorting has its own cost

Apply a binary search to find 23 in the list 5 10 15 20 23 27 30

Middle = 20. 23 > 20 so search right half: 23 27 30. Middle = 27. 23 < 27 so search left: 23. Middle = 23 — found

Apply a binary search to find 7 in the list 2 4 7 9 11 13 15

Middle = 9. 7 < 9 so search left: 2 4 7. Middle = 4. 7 > 4 so search right: 7. Middle = 7 — found

Apply a binary search to find 6 in the list 1 3 5 7 9

Middle = 5. 6 > 5 so search right: 7 9. Middle = 7. 6 < 7 so search left: empty — 6 not found

BUBBLE SORT

What is a bubble sort?

Repeatedly compares adjacent pairs of elements — swaps them if they are in the wrong order — larger values bubble to the end — repeats passes until no swaps occur in a full pass

What are the steps of a bubble sort?

Step 1 — start at the beginning of the list. Step 2 — compare the first and second elements — if first is greater swap them. Step 3 — move to the next pair and repeat. Step 4 — continue to the end of the list — this completes one pass. Step 5 — repeat passes until a complete pass makes no swaps — list is sorted

How do you know when bubble sort is finished?

When a complete pass through the list produces no swaps — the list must be sorted

What are the advantages of bubble sort?

Simple to understand and implement — can detect an already sorted list quickly — uses very little additional memory

What are the disadvantages of bubble sort?

Very slow for large lists — requires many comparisons and swaps — inefficient compared to merge sort

Sort the list 5 3 8 1 using bubble sort — show all passes

Pass 1 — compare 5 and 3 swap → 3 5 8 1. Compare 5 and 8 no swap. Compare 8 and 1 swap → 3 5 1 8. Pass 2 — compare 3 and 5 no swap. Compare 5 and 1 swap → 3 1 5 8. Compare 5 and 8 no swap. Pass 3 — compare 3 and 1 swap → 1 3 5 8. Compare 3 and 5 no swap. Pass 4 — no swaps — sorted: 1 3 5 8

Sort the list 4 2 6 1 3 using bubble sort — show pass 1 only

Compare 4 and 2 — swap → 2 4 6 1 3. Compare 4 and 6 — no swap. Compare 6 and 1 — swap → 2 4 1 6 3. Compare 6 and 3 — swap → 2 4 1 3 6. End of pass 1

Sort the list 9 5 2 7 using bubble sort — show all passes

Pass 1 — 5 9 2 7 → 5 2 9 7 → 5 2 7 9. Pass 2 — 2 5 7 9 → 2 5 7 9. Pass 3 — no swaps — sorted: 2 5 7 9

MERGE SORT

What is a merge sort?

A divide and conquer algorithm — repeatedly splits the list in half until each section contains only one element — then merges pairs back together in sorted order — very efficient for large lists

What are the steps of a merge sort?

Step 1 — split the list into two halves. Step 2 — recursively split each half again until you have single elements. Step 3 — compare the first elements of two lists — take the smaller one. Step 4 — repeat until both lists are merged into one sorted list. Step 5 — continue merging up until the full list is sorted

How does the merging step work in merge sort?

Take two sorted lists — compare the first element of each — take the smaller and add it to the new sorted list — repeat until one list is empty — add remaining elements — result is one sorted merged list

What are the advantages of merge sort?

Very efficient for large lists — consistent performance — good for sorting linked lists — stable sort

What are the disadvantages of merge sort?

More complex to understand and implement — requires additional memory to store split lists during merging

Sort the list 4 2 7 1 using merge sort — show all steps

Split → 4 2 and 7 1. Split → 4 and 2 and 7 and 1. Merge 4 and 2 → 2 4. Merge 7 and 1 → 1 7. Merge 2 4 and 1 7 → compare 2 and 1 take 1 → compare 2 and 7 take 2 → compare 4 and 7 take 4 → take 7. Result: 1 2 4 7

Sort the list 8 3 5 1 using merge sort — show all steps

Split → 8 3 and 5 1. Split → 8 and 3 and 5 and 1. Merge 8 and 3 → 3 8. Merge 5 and 1 → 1 5. Merge 3 8 and 1 5 → compare 3 and 1 take 1 → compare 3 and 5 take 3 → compare 8 and 5 take 5 → take 8. Result: 1 3 5 8

Sort the list 6 4 2 8 3 1 using merge sort — show splitting stage only

Split → 6 4 2 and 8 3 1. Split → 6 4 and 2 and 8 3 and 1. Split → 6 and 4 and 2 and 8 and 3 and 1. Now merge back in pairs

INSERTION SORT

What is an insertion sort and how does it work?

Insertion sort builds a sorted list one element at a time — it takes each element from the unsorted part and inserts it into the correct position in the sorted part — like sorting playing cards in your hand — you pick up each card and slot it into the right place among the cards already sorted

What are the steps of an insertion sort — explained clearly?

Step 1 — the first element is already considered sorted. Step 2 — take the next element (the key). Step 3 — compare the key to each element in the sorted portion moving right to left. Step 4 — shift each sorted element one position to the right if it is greater than the key. Step 5 — insert the key into the gap created. Step 6 — repeat steps 2 to 5 for every remaining element

How does insertion sort slot an element into the right place?

It compares the element being inserted (the key) with the sorted elements to its left — each sorted element that is bigger than the key gets moved one place to the right — this creates a gap — the key is then placed in that gap — the sorted section grows by one each time

What are the advantages of insertion sort?

Simple to implement — very efficient for small or nearly sorted lists — builds sorted list in place using very little extra memory — can sort as data arrives

What are the disadvantages of insertion sort?

Slow for large unsorted lists — many comparisons and shifts needed in the worst case

Sort the list 5 3 8 1 using insertion sort — show every step clearly

Start — sorted section: 5. Unsorted: 3 8 1. Take key = 3. Compare 3 with 5 — 5 > 3 so shift 5 right. Insert 3 in gap. List now: 3 5 8 1. Take key = 8. Compare 8 with 5 — 5 < 8 so no shift. Insert 8 here. List now: 3 5 8 1. Take key = 1. Compare 1 with 8 — shift 8 right. Compare 1 with 5 — shift 5 right. Compare 1 with 3 — shift 3 right. Insert 1 at start. Sorted: 1 3 5 8

Sort the list 7 2 9 4 using insertion sort — show every step clearly

Start — sorted: 7. Take key = 2. 7 > 2 — shift 7 right. Insert 2. List: 2 7 9 4. Take key = 9. 7 < 9 — no shift. Insert 9. List: 2 7 9 4. Take key = 4. 9 > 4 — shift 9. 7 > 4 — shift 7. 2 < 4 — stop. Insert 4. Sorted: 2 4 7 9

Sort the list 6 1 4 2 using insertion sort — show every step clearly

Start — sorted: 6. Take key = 1. 6 > 1 — shift 6. Insert 1. List: 1 6 4 2. Take key = 4. 6 > 4 — shift 6. 1 < 4 — stop. Insert 4. List: 1 4 6 2. Take key = 2. 6 > 2 — shift 6. 4 > 2 — shift 4. 1 < 2 — stop. Insert 2. Sorted: 1 2 4 6