Fundamentals of Algorithms Flashcards
What is an algorithm?
A set of instructions which completes a task in a finite time and always terminates.
Name the two types of graph traversal.
Depth-First Search (DFS)
Breadth-First Search (BFS)
Describe a Breadth-First Search
Startssearching at a designated startnode and searches through all the adjacentnodes (neighbours) before moving on.
Uses aqueueas a supporting data structure.
Describe a Depth-First Search
Begins at the start node and then searches as far as possible down a branch of the graph until there are no more nodes along the current branch to be explored. If the target node is found along the way, the search can stop. Otherwise, the algorithm must backtrack and find another branch to explore.
Uses astackas a supporting data structure.
State an application of DFS
Can be used to determine whether there is a path between two nodes of a graph.
State an application of BFS
Shortest path between two nodes on an unweighted graph.
Name the three types of tree-traversal
Pre-order
In-order
Post-order
Name a use of postorder traversal
Convert Infix to RPN
Emptying a tree
Produces a postfix expression from an expression tree.
What is a tree
A connected, undirected graph without any cycles.
Why is RPN used?
Eliminates the need for brackets, removing ambiguity and simplifying expressions.
It is well suited to manipulation by a stack, making it a popular choice when working with computers.
Where is RPN used?
In interpreters which are based on stacks.
Convert the following infix expression to RPN: (12 - 4) * (3 + 5)
12 4 - 3 5 + *
Convert the following reverse polish expression to infix: 13 6 + 4 -
(13 + 6) - 4
What is the time complexity of a linear search algorithm?
O(n)
Which searching algorithm requires the data to be sorted before starting?
Binary search
