Programming: algorithms Flashcards
describe the process of graph traversal
visiting each vertex in a graph
what are the two algorithms used for graph traversal?
depth first and breadth first
describe the concept of a depth first traversal
a branch is fully explored before back tracking
describe the concept of a breadth first algorithm
each adjacent node is fully explored before moving to the next node
describe the process of depth first traversal
a stack is used
what is the root node in graph traversal
the node from which the traversal starts
if the root node were F, with two child nodes being B and G, which child node would be discovered first?
B
what is a breadth first algorithm used for?
finding the shortest path on an unweighted graph
for depth and breadth graph traversal, which uses a stack and which uses a queue?
depth first traversal uses a stack and a breadth first traversal uses a queue.
describe the use of a pre order tree traversal algorithm
can be used to copy a tree
describe the use of an in order tree traversal algorithm
outputting the contents of a binary search tree in ascending order
describe a purpose of a post order tree traversal algorithm
converting from Infix to reverse polish notation or emptying a tree
describe a tree traversal
the process of visiting/updating/outputting each node in a tree.
what is the difference between graph and tree traversals?
-tree traversals are unique to trees
-tree traversals must start at the root node
where can an in order traversal be used?
only with binary trees
what is a binary tree
a rooted, ordered tree in which each parent node has no more than 2 child nodes
what is the purpose of reverse polish notation
-it removes the need for brackets
-eliminates confusion over the order of execution
describe reverse polish notation
the opcode is written after the operand
what is infix and postfix?
infix is a sum written as a human would write it, postfix is a sum written in reverse polish notation form
how is a stack used to evaluate postfix equations?
an algorithms goes along an array (containing the postfix expression) and operands are pushed onto a stack. Once an opcode is identified, two items of the stack are popped and the operation is performed.
describe a linear search
the list is iterated through and each value in the list is checked until the desired item is found
what is the time complexity of a linear search?
O(N)
when can a binary search be used?
when the list is sorted. If it is not, it must be sorted before a binary search can be carried out
how does a binary search work?
the midpoint of the list is compared to the desired value and depending on if it is higher or lower than it, a half of the list is discounted as it will not contain the desired value. The midpoint of what’s left of the list is then found, and so on.
