GCSE Computer Science - Topic 1

What is Decomposition?

Breaking down a complex problem into smaller, more manageable parts that are easier to solve.

What is Abstraction?

Removing or hiding unnecessary detail from a problem to focus on the essential points.

Give an example of Abstraction.

1. A tube map, which hides roads and buildings to only show stations and lines. 2. A subprogram (like print(), which hides the complex code needed to make it work.

What is a Subprogram?

A self-contained block of code that performs a specific task (e.g., print(), random.randint()).

What are the benefits of using subprograms?

• Breaks down complex problems also known as Decomposition.

• Makes code clearer and easier to maintain.

• Allows code to be reused in different parts of the program or in other programs.

• Enables teams of programmers to work on different parts in parallel.

What is the difference between a Function and a Procedure?

• A Function returns one or more results (a value) to the calling code.

• A Procedure does not return a result. (Note: In Python, all subprograms are technically functions, but you must know this distinction).

What is an Algorithm?

A set of precise, step-by-step instructions needed to solve a problem.

What are the 3 basic programming constructs?

1. Sequence: Instructions are executed in the correct order, one after another. 2. Selection: Used to make a choice between two or more options (e.g., if, elif, else). 3. Iteration: Repeating a set of instructions (looping).

What are the two types of iteration (loops)?

1. Count-controlled: Runs a fixed number of times (e.g., a for loop).

2. Condition-controlled: Runs until a specific condition is met (e.g., a while loop).

What are the 6 main flowchart symbols?

• Terminal (Oval): Start/End.

• Process (Rectangle): An action or calculation (e.g., SET count TO 0).

• Input/Output (Parallelogram): Data being input or output.

• Decision (Diamond): A Yes/No question (used for selection/iteration).

• Subprogram (Rectangle with side lines): Calls a separate function/procedure.

• Line (Arrow): Shows the flow and direction of the algorithm.

What is a Variable?

A named location in memory that stores a value which can change during program execution.

What is a Constant?

A named location in memory that stores a value that does not change during program execution.

What is an Array?

A data structure that stores multiple items of data (of the same data type) under one name. Items are accessed using an index (e.g., myList[0]).

What is a 2D Array?

A data structure that stores multiple arrays (an "array of arrays"). It's used to represent tables or grids and is accessed with two indexes (e.g., grid[row][col]).

What is the difference between an Array and a Record?

• An Array stores items of the same data type (homogeneous).

• A Record stores items of different data types (heterogeneous), which are called fields.

What is an Element in an array?

A single item of data stored at a particular index in an array.

What is an Index in an array?

The position of an element in an array. In Python, indexing starts at 0.

What are the 3 types of operators?

1. Arithmetic: For calculations (e.g., +, -, *, /, %, //, **). 2. Relational: For comparisons (e.g., ==, !=, >, <, >=, <=). 3. Logical: For combining Boolean expressions (e.g., AND, OR, NOT).

What does % (Modulus) do?

Returns the remainder after a division (e.g., 10 % 3 is 1).

What does // (Integer Division) do?

Returns the whole number part of a division, discarding the remainder (e.g., 10 // 3 is 3).

What is the order of precedence for logical operators?

1. NOT 2. AND 3. OR (Brackets can be used to override this order).

What is a Trace Table used for?

To perform a "dry run" of an algorithm. It tracks the value of each variable, input, and output line by line to understand the algorithm's flow and find logic errors.

What is a Syntax Error?

An error where the rules of the programming language are broken (e.g., spelling mistake, missing bracket, incorrect indentation). It prevents the program from running.

What is a Runtime Error?

An error that occurs during program execution when it's asked to do an impossible operation (e.g., dividing by zero, opening a file that doesn't exist).

What is a Logic Error?

An error in the program's logic. The program runs but produces an incorrect or unexpected result (e.g., using > instead of <, or adding when you should be subtracting).

How does a Linear Search work?

• It starts at the beginning of a list.

• It checks each item one by one (sequentially) until the target is found or the end of the list is reached.

• It is a "brute force" method and works on unsorted lists

How does a Binary Search work?

• It requires a SORTED list.

• It checks the median (middle) item.

• If the target is higher, it discards the lower half of the list.

• If the target is lower, it discards the upper half of the list.

• It repeats this "divide and conquer" process on the remaining sub-list until the item is found.

Compare the efficiency of Linear vs. Binary search.

• Binary: Much more efficient (faster) for large lists.

• Linear: Very inefficient for large lists as it might have to check every item. Its best case is finding the item at index 0.

How does a Bubble Sort work?

• It repeatedly passes through the list.

• It compares adjacent (side-by-side) items.

• It swaps them if they are in the wrong order.

• It continues making passes until a full pass is completed with no swaps.

• It is a "brute force" method.

How does a Merge Sort work?

1. Divide: Recursively splits the list into sub-lists until each contains only one item. 2. Conquer (Merge): Merges the sub-lists back together, comparing the first item of each list and placing them in the correct order in a new list.

• It is a "divide and conquer" method.

Compare the efficiency of Bubble vs. Merge sort.

• Merge Sort: Much more efficient (faster) for large lists. It is an "out of place" sort and requires extra memory to store sub lists.

• Bubble Sort: Very slow for large lists. It is an "in place" sort and simple to code, but inefficient.

When is A AND B True?

Only when both A and B are True.

When is A OR B True?

When at least one of A or B is True (it is only False if both A and B are False).

What does NOT A do?

It inverts (flips) the truth value.

• NOT True becomes False.

• NOT False becomes True.