Fundamentals of algorithms flashcards

Topic 3: Fundamentals of algorithms

How does a breadth-first traversal of a graph work?

Visit all the neighbours of the start vertex first, then their neighbours, and so on, using a queue. Finds the shortest path in an unweighted graph.

How does a depth-first traversal of a graph work?

Go as far as possible along one branch before backtracking, using a stack (or recursion). Used for navigating a maze.

What are the pre-order, in-order and post-order traversals of a binary tree?

Pre-order: node, left, right (copying a tree). In-order: left, node, right (outputs a binary search tree in order). Post-order: left, right, node (emptying a tree; producing Reverse Polish).

What is Reverse Polish notation and why is it used?

Postfix notation: the operator follows its operands, e.g. 3 4 + for 3 + 4. No brackets are needed, and it is easily evaluated with a stack.

What are the time complexities of linear search, binary search and binary tree search?

Linear search: O(n). Binary search: O(log n). Binary tree search: O(log n) for a balanced tree.

How does a merge sort work, and what is its time complexity?

Split the list into single items, then repeatedly merge pairs of sorted sublists into larger sorted lists. O(n log n).

What is the time complexity of bubble sort?

O(n²): each pass compares adjacent pairs, and up to n passes may be needed.

What does Dijkstra’s algorithm do?

Finds the shortest path from a start vertex to every other vertex in a weighted graph (with no negative weights), using a priority queue.