Fundamentals of algorithms

What is an algorithm?

A sequence of steps designed to complete a task

How is an algorithm different from a program?

An algorithm is the plan; a program is the coded implementation

What is decomposition?

Breaking a problem down into sub-problems, each with an identifiable task

What is abstraction?

Removing unnecessary details from a problem to focus on essentials

Why use decomposition in programming?

Makes complex problems easier to solve and maintain

What are the main ways to represent an algorithm?

Pseudocode, flowcharts, program code

What is pseudocode?

A simple way to write algorithms using code-like instructions, not language-specific

What is a flowchart?

A diagram showing the steps of an algorithm using symbols

What is program code?

Instructions written in a programming language (like Python, Java)

When might you be asked to use pseudocode or flowchart in an exam?

When indicated in AQA exam, according to standard formats

How do you identify inputs in an algorithm?

Inputs are values or data provided to start the algorithm

How do you identify outputs in an algorithm?

Outputs are results produced by the algorithm

What is 'processing' in an algorithm?

Steps/manipulation that transform inputs into outputs

What is a trace table?

Table used to track variable values step by step as an algorithm runs

How can you use a trace table?

Visualise how a simple algorithm works as each step/iteration is made

How do you determine the purpose of an algorithm?

Look at how inputs are transformed into outputs, and overall flow

Can different algorithms solve the same problem?

Yes, multiple algorithms can be designed for a single task

What does 'algorithm efficiency' mean?

How quickly (in time/steps) an algorithm solves a problem

What is meant by time efficiency in algorithms?

How long an algorithm takes to find the solution

Is formal comparison of efficiency required for GCSE?

No, only time efficiency in simple explanations

What is a linear search algorithm?

Checks each item in a list, one at a time, until the target is found or list ends

What is a binary search algorithm?

Repeatedly divides a sorted list in half, checking the middle each time

What is required for binary search to work?

List must be sorted

How does linear search work mechanically?

Starts from first item, compares each, moves forward until match or end

How does binary search work mechanically?

Finds middle item, compares target; if not match, chooses half to search next; repeat

Give an advantage of linear search.

Works on unsorted lists, simple to code

Give a disadvantage of linear search.

Slower for large lists; must check every item in worst case

Give an advantage of binary search.

Faster for large sorted lists (cuts search space in half each time)

Give a disadvantage of binary search.

Needs sorted data; more complex logic

How do you compare linear and binary search?

Both find items; binary usually faster but needs sorted data, linear requires no sorting

What is a bubble sort algorithm?

Repeatedly passes through list, swapping adjacent items if needed until sorted

How does bubble sort work?

Compares pairs, swaps as needed; multiple passes until no swaps needed

What are the advantages of bubble sort?

Simple to understand and code

What are the disadvantages of bubble sort?

Slow on large lists, inefficient (many passes/tests)

What is a merge sort algorithm?

Divides list into halves, sorts each half, merges sorted halves together

How does merge sort work mechanically?

Recursively splits list, sorts sublists, merges back into sorted order

What are the advantages of merge sort?

Fast for large lists, efficient, reliable

What are the disadvantages of merge sort?

Uses more memory for temporary lists/recursion

How do you compare bubble sort and merge sort?

Bubble is simple and good for small lists; merge is efficient for large lists but uses more memory

Why is understanding inputs, outputs, processing important in algorithms?

Clarifies what the algorithm needs, what it does, and what it produces for successful design

Define the term 'algorithm representation'.

How algorithms are shown (e.g. pseudocode, flowchart, program code)

Why use systematic approaches to algorithm creation?

Ensures steps are clear, logical, and efficient

What does it mean to use "visual inspection" for algorithms?

Step through and check each line/box to figure out the algorithm’s purpose

How might you be asked about algorithms using pseudocode in an exam?

Shown standard AQA pseudocode and required to interpret or write it in that format

What are standard symbols used in flowcharts?

Oval: Start/End, Parallelogram: Input/Output, Rectangle: Process, Diamond: Decision

How do you identify algorithms with trace tables?

Fill in table for each line/step, updating values as the algorithm runs

Why can multiple algorithms solve the same problem in programming?

Different methods may have different advantages (e.g., speed, simplicity)

What is meant by an 'efficient' algorithm in GCSE exams?

Quick to complete (time-wise), may use fewer steps

What does "exam will only refer to time efficiency" mean?

Questions will ask which algorithm is faster, not about memory or other resources

How do you explain the mechanics of linear search?

Step through each list item in order, check for match until found or finished

How do you explain the mechanics of binary search?

Divide sorted list, select middle, decide which half to search next; repeat

How do you explain the mechanics of merge sort?

Split list into halves, keep splitting until single items, then merge up in sorted order

How do you explain the mechanics of bubble sort?

Iterate list, swap adjacent out-of-order items, repeat passes until sorted

What is the key difference between linear and binary search?

Linear is stepwise; binary divides and skips over lots of items (only works on sorted lists)

What is the key difference between bubble and merge sort?

Bubble sorts by swapping adjacent pairs; merge divides and conquers then merges

Why is abstraction used when designing algorithms?

Focuses only on important information, ignoring irrelevant details

Why is decomposition critical for solving complex problems?

Makes tasks more manageable, allows teamwork, supports debugging

What is a systematic approach to problem solving in computing?

Following set steps to break down and solve problems logically

When might you use a flowchart instead of pseudocode?

When visual representation helps clarify the process/logic

What is a decision point in a flowchart?

Diamond shape for "yes/no", "true/false" branching

Why do algorithms need to be clear and well-represented?

Ensures they can be implemented correctly by a programmer

How do you determine algorithm purpose with visual inspection?

Look at overall flow, see what output is produced from the inputs

What is pseudo code in AQA GCSE exams?

A set of clear, English-like instructions using standard format for Python-style code

Why is it important to understand the mechanics of search/sort algorithms?

To select the right method for different problems and data sizes

Give a sample pseudocode for linear search.

FOR each item in list: IF item == target THEN OUTPUT index; END IF; NEXT

Give a sample pseudocode for binary search.

Set left/right pointers; WHILE left <= right: Set mid = (left + right)/2; IF list[mid] == target THEN OUTPUT mid; ELSE IF target < list[mid] THEN right = mid -1; ELSE left = mid +1; END WHILE

Give sample pseudocode for bubble sort.

FOR i = 0 TO n-1: FOR j = 0 TO n-i-2: IF list[j] > list[j+1] THEN swap; END FOR; END FOR

Give sample pseudocode for merge sort.

If list size > 1 THEN split into halves; recursively sort left and right; merge halves

How do you check efficiency in practice?

Time how long each algorithm takes to finish on same problem

Why might merge sort use more memory than bubble sort?

Requires temporary arrays for splitting and merging

When is bubble sort acceptable to use?

Small datasets, simple programs, teaching concepts

Why is merge sort preferred for large datasets?

Less passes, more efficient sorting

What is the output of a trace table?

Clarified flow of data—shows each step’s values for variables

Why are sort and search algorithms important?

Used universally in computing to handle data in lists/arrays

What is an advantage of writing algorithms in pseudo code?

Language-free, easy for multiple programmers to understand