Algorithms Flashcards
1
Q
Graph Traversal
A
- The process of visiting each vertex in a graph
- Can be performed on any connected graph
2
Q
Depth First Search
A
- A branch is fully explored before backtracking
- Uses a stack
- Used for navigating a maze
3
Q
Breadth First Search
A
- A node is fully explored before venturing onto the next node
- Uses a queue
- Used for determining the shortest path on an unweighted graph
4
Q
Tree Traversal
A
- The process of visiting each node in a tree
- The algorithm must start at the root
- Works anticlockwise
- Uses Depth First Traversal
5
Q
Pre-Order Traversal
A
- Used for copying a tree
- Can be performed on any tree
6
Q
In-Order Traversal
A
- Outputs the contents in ascending order
- Is performed on binary trees
7
Q
Post-Order Traversal
A
- Can be performed on any tree
- Used to empty the tree
- Used for infix to RPN conversions
8
Q
Reverse Polish
A
- A way of writing expressions
- Uses postfix notation (operators are placed after operands)
9
Q
Advantages of Reverse Polish
A
- It eliminates the needs for brackets, simplifying expressions
- Well suited for manipulation by a stack
10
Q
Searching Algorithm
A
Used to find a specified data item within a set of data
11
Q
Linear Search
A
- Can be conducted on any list
- Inspects every item one by one until the desired item is found
- Time complexity of O(N)
12
Q
Binary Search
A
- Only works on ordered lists
- Takes the midpoint of a list and determines if the target is higher or lower
- Time complexity of O(logN)
13
Q
Sorting Algorithms
A
Used to put elements in an array into a specific order
14
Q
Bubble Sort
A
- Swaps adjacent items in an array until the array is in order
- Has a time complexity of O(n^2)
15
Q
Merge Sort
A
- Divides an array into smaller arrays until each array contains just one element
- Arrays are then remerged into an ordered array
- Time complexity of O(nlogn)
16
Q
Optimisation Algorithms
A
Finds the best possible solution to the problem posed
17
Q
Dijkstra’s Algorithm
A
- Finds the shortest path from a starting node to every other node in a network
- Uses a priority queue rather than a standard queue
18
Q
Uses of Dijkstra’s Algorithm
A
- Satellite navigation systems
- Routers
