Fundamentals of algorithm Flashcards
Paper 1
What is a graph-traversal?
Graph-traversal is the process of visiting each vertex in a graph.
The two algorithms section are called Depth-First graph-traversal and Breadth-First graph-traversal.
What does a Depth-First Traversal do?
In a Depth-first search, a branch is fully explored before backtracking.
- Depth-first traversal uses a stack.
What does a Breath-First Traversal do?
In a breadth-first search a node is fully explored before venturing on to the next node.
- Breadth-first traversal uses a queue.
What is a Tree-Traversal?
It is the process of visiting/updating/outputting each product in a tree.
They must start at the root of the tree.
What are the three types of tree traversal?
- Pre-Order tree traversal => A tree traversal method where you visit: Root node, Left subtree,Right subtree.
- In-Order tree traversal => A tree traversal method where you visit: Left subtree, Root node, Right subtree.
- Post-Order traversal => A tree traversal method where you visit: Left subtree, Right subtree, Root node.
What is infix notation?
An expression where the operator is between operands.
Example: A + B
What is postfix notation (Reverse Polish Notation)?
An expression where the operator comes after the operands.
Example: A B +
Why is postorder traversal used for converting infix to postfix?
Because it visits operands before the operator, matching the postfix format: Left → Right → Root
How do you convert infix to postfix using a tree?
- Build an expression tree from the infix expression
- Perform a postorder traversal
- The output is the postfix expression
Describe how a single stack could be used to evaluate an RPN expression
- Read the expression from left to right.
- If the token is a number, push it onto the stack.
- If the token is an operator, pop the top two values, apply the operator, and push the result back.
- After processing all tokens, the final result is the only value left on the stack.
What is an algorithm?
An algorithm is a set of instructions which completes a task in a finite time and always terminates.
What is a linear search?
Linear search is a simple search algorithm that checks each element in a list one by one until the target value is found or the end of the list is reached.
- It has a tme complexity of O(N)
- A linear search can be conducted on any unordered list.
What is a binary search?
Binary search is a search algorithm that repeatedly divides a sorted list in half to find a target value.
- The time complexity is O(logN) because the list is halved each search.
- A binary search can be used on any ordered list.
What is a binary tree search?
A binary tree search is the same as a binary search,
except it is conducted on a binary tree
Like a binary search, a binary tree search has a time complexity of O(logN).
What is a sorting algorithm?
A sorting algorithm is a method used to arrange elements in a list or array into a specific order, usually ascending or descending.
What is a bubble sort algorithm?
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order
- It has a time complexity of O(n²) so it is very inefficient.
What is a merge sort?
A merge sort orders arrays by splitting them into smaller lists, and then reforming them - the ‘divide and conquer’ method.
It is quicker than a bubble sort; it has a time complexity of O(nlogn).
What is an optimisation algorithm?
An optimisation algorithm finds the best possible solution to the problem posed.
What is Dijkstra’s Alogrithm?
Dijkstra’s algorithm is used to find the shortest path between two nodes in a graph.
What are the applications of Dijkstra’s algorithm?
- Used to calculate the shortest path between two points
- Common in satellite navigation systems (e.g., GPS)
- Helps find the fastest route from start to destination
- Used by routers to efficiently route data packets through networks
How does Dijkstra’s Algorithm find the shortest path?
- Start at the source node; set its distance to 0, others to ∞
- Visit each neighbor of the current node
- For each neighbor, calculate:
current distance + edge weight - If this value is less than the neighbor’s known distance, update it
- Mark the current node as visited
- Choose the unvisited node with the smallest distance as the next current node
- Repeat until all nodes are visited or the destination is reached
