(P1) Fundamentals of Algorithms
No description yet. This curated deck is ready for daily study.
Card preview (24)
What is graph traversal?
The process of visiting each vertex in a graph.
What are the two graph traversals?
Depth-first and breadth-first.
Describe depth-first traversal.
A branch is fully explored before backtracking. Uses a stack and is used navigating mazes.
Describe breadth-first traversal.
A node is fully explored before venturing on the next node. Uses a queue. Used for determining the shortest path on an unweighted graph.
What is an algorithm?
A set of instructions which completes a task in a finite time and always terminates.
What is a tree?
A connected acyclic graph.
Describe tree traversal.
Process of visiting each node in a tree. Unique to trees and must start at the root.
Where should the dot be drawn for a pre-order traversal?
Left.
Where should the dot be drawn for a in-order traversal?
Bottom.
Where should the dot be drawn for a post-order traversal?
Right.
What can pre-order traversal be used for?
Copying trees.
What can an in-order traversal be used for?
Used in binary trees to outputs the contents of a binary tree in ascending order.
What can post-order traversals be used for?
Infix to RPN conversions. Producing a postfix expression from an expression tree. Emptying a tree.
How are Infix to RPN and binary trees related?
Infix to RPN involve the making and traversing of a binary tree.
What is an opcode?
An operator.
What is an operand?
Data which is applied to the operator.
When creating an expression tree, what should always be the parent node and the child nodes?
Parents should be the opcode. Children should be the operands.
What is produced from performing an in-order traversal on an expression tree?
Infix expression.
What is produced from performing an post-order traversal on an expression tree?
Postfix expression.
How do you work out a postfix expression?
Perform the calculation of the opcode and only the two preceding operands and put back into expression. Repeat.
What notation do humans use?
Infix notation.
What does RPN stand for?
Reverse Polish Notation.
What is RPN?
A postfix way of writing expressions. Eliminates need for brackets and any confusion of the order of execution. Opcode is written after the operands.
What data structure can be used to evaluate postfix equations?
Stacks.