4.3 Fundamentals of Algorithms AQA Comp Sci

A-Level

What is graph traversal?

Graph traversal is the process of visiting all the nodes in a graph systematically.

What is Breadth-First Search (BFS)?

A graph traversal method that explores all neighbouring nodes before going deeper.

Which data structure does BFS use?

Queue (FIFO - First In, First Out).

What is BFS used for?

Used to find the shortest path in an unweighted graph.

What is Depth-First Search (DFS)?

A graph traversal method that explores as far down a path as possible before backtracking.

Which data structure does DFS use?

Stack (LIFO - Last In, First Out).

What is DFS used for?

Used in maze navigation and pathfinding.

What is tree traversal?

The process of visiting all the nodes in a tree.

What are the three types of tree traversal?

Pre-Order, In-Order, and Post-Order.

What is Pre-Order traversal?

Root -> Left -> Right; used for copying a tree.

What is In-Order traversal?

Left -> Root -> Right; used to retrieve elements in a sorted order for BSTs.

What is Post-Order traversal?

Left -> Right -> Root; used for expression evaluation (Reverse Polish Notation).

What is Reverse Polish Notation (RPN)?

A mathematical notation where operators follow their operands.

What does RPN eliminate?

The need for brackets in mathematical expressions.

What data structure is used in RPN evaluation?

Stack.

Where is RPN used?

In compilers, calculators, and interpreters.

How does RPN relate to tree traversal?

If a binary tree uses in-fix notation, RPN can be derived using DFS.

What is a linear search?

A search that checks each element of a list for the target value.

What is the time complexity of a linear search?

O(n).

What does a linear search return if the target is not found?

-1

What is a binary search?

A search algorithm that divides the search space in half to locate the target value.

What condition must be met for binary search to work?

The list must be sorted.

What is the time complexity of a binary search?

O(log n).

What is the first step in binary search?

Find the middle element.

What happens if the middle element matches the target?

Return the index.

What happens if the target is smaller than the middle element?

Search the left half.

What happens if the target is greater than the middle element?

Search the right half.

What is a binary search tree (BST)?

A tree where each node has at most two children; left subtree < root, right subtree > root.

What traversal gives sorted order in BST?

In-Order Traversal.

How does a binary tree search work?

Start at root, compare target to root, recurse left or right depending on comparison.

What is the time complexity of binary tree search?

O(log n).

What is Bubble Sort?

A sorting algorithm that swaps adjacent elements if they are in the wrong order.

How does Bubble Sort work?

Compare adjacent elements and swap if needed; repeat until sorted.

What is the time complexity of Bubble Sort?

O(n^2).

What is Merge Sort?

A divide-and-conquer algorithm that recursively splits, sorts, and merges subarrays.

How does Merge Sort work?

Split array recursively, sort subarrays, merge them back together.

What is the time complexity of Merge Sort?

O(n log n).

Why is Merge Sort faster than Bubble Sort?

It uses divide and conquer, reducing comparisons.

What is a drawback of Merge Sort?

Uses more memory due to recursion.

What is Dijkstra's Algorithm?

An optimization algorithm for finding the shortest path from a start node to all other nodes in a weighted graph.

Where can Dijkstra's Algorithm be used?

Circuit board design, route planning, game strategy, project management.

What type of algorithm is Dijkstra's?

Greedy and dynamic.

How does Dijkstra's Algorithm start?

Assigns a temporary distance of 0 to the start node and ∞ to others.

Which data structure does Dijkstra's use?

Priority Queue.

How is Dijkstra’s similar to BFS?

Both explore neighbouring nodes, but Dijkstra considers weights.

What is graph traversal? (Detailed)

Graph traversal is the process of visiting all the nodes in a graph systematically. This is an extended explanation.