fundamentals of algorithms - topic 3

What is a sorting algorithm?

A method of arranging data in a particular order, usually ascending or descending.

Describe how Bubble Sort works.

Repeatedly compares adjacent pairs of elements and swaps them if they are in the wrong order; continues until no swaps needed.

What is the time complexity of Bubble Sort?

O(n²) — inefficient for large datasets.

When is Insertion Sort useful?

For small or nearly sorted lists because it is simple and efficient for these cases.

Describe how Insertion Sort works.

It builds the sorted array one item at a time by inserting elements into their correct position.

What is the time complexity of Insertion Sort?

O(n²)

Explain how Merge Sort works.

A divide-and-conquer algorithm that splits the list into halves, sorts each half recursively, and then merges them.

What is the time complexity of Merge Sort?

O(n log n) — efficient for large lists.

What is Linear Search?

A search algorithm that checks each element in the list sequentially until the target is found.

What is the time complexity of Linear Search?

O(n)

What is Binary Search?

A search algorithm that repeatedly divides a sorted list in half to locate a target value.

What is the prerequisite for Binary Search?

The list must be sorted.

What is the time complexity of Binary Search?

O(log n)

What is Depth-First Search (DFS)?

A graph traversal method that explores as far as possible along each branch before backtracking.

What data structure does DFS commonly use?

A stack or recursion.

What is Breadth-First Search (BFS)?

A graph traversal method that explores all neighbours at the current depth before moving to the next level.

What data structure does BFS commonly use?

A queue.

Name two common graph representations.

Adjacency matrix and adjacency list.

What is Dijkstra’s Algorithm used for?

Finding the shortest path from a starting node to all other nodes in a weighted graph.

What is a priority queue's role in Dijkstra’s Algorithm?

To efficiently select the next closest unvisited node.

Define Big-O notation.

A mathematical notation that describes the worst-case time or space complexity of an algorithm.

What is O(1) complexity?

Constant time; the operation takes the same amount of time regardless of input size.

What is O(n) complexity?

Linear time; time grows directly with input size.

What is O(log n) complexity?

Logarithmic time; time grows in proportion to the logarithm of input size.

What is O(n²) complexity?

Quadratic time; time grows proportional to the square of the input size.

What does time complexity measure?

The amount of time an algorithm takes relative to the size of input data.

What does space complexity measure?

The amount of memory an algorithm uses relative to input size.

How do you compare two sorting algorithms?

Compare their time complexities, space usage, and suitability for different input sizes or types.

What is the main difference between Bubble Sort and Merge Sort?

Bubble Sort swaps adjacent elements repeatedly and is inefficient; Merge Sort uses divide-and-conquer and is more efficient.

What is a graph?

A collection of nodes (vertices) connected by edges.

What is the difference between weighted and unweighted graphs?

Weighted graphs assign a cost to edges; unweighted do not.

What are the key steps in the Merge Sort algorithm?

Split list into halves → sort each half recursively → merge sorted halves.

What is meant by 'divide and conquer' in algorithms?

Breaking a problem into smaller subproblems, solving each recursively, then combining results.