Algorithms Flashcards
What are the two ways of traversing a graph?
Breadth first and depth first
Whats the difference between depth first and breadth first
depth first - start at a node and go as far along the node before backtracking
breadth first - explore nodes that are the closest at first then moving onto nodes that are further away
What ways can you traverse a binary tree?
Pre-order, in-order and post-order
How do you do pre-order, in-order, and post-order
pre-order - visit a root, travel up the left subtree, then travel up the right subtree
in-order - traverse a tree by visiting the left subtree, the root and then the right subtree
post-order - travel up the left subtree, the right subtree and then the root
What is a binary search
split data n half repeatedly until data item is found
What is a binary tree search and how can you do it?
Binary tree search - traversing a binary tree until the item is found
What is reverse polish notation
it is postfix notation, where the operators are written after the operands.
What is the point of pre fix or postfix notation
it removes the need for using brackets
how can you evaluate RPN expressions
put everything on a stack
How do you get different __fix notations from a binary tree?
To get infix traverse the binary tree in order
to get postfix, traverse the tree in post order
to get prefix, traverse the binary tree using pre order
What is a bubble sort?
a sort method that works by repeatedly stepping through an array by comparing adjacent elements and swapping them if necessary.
What is a merge sort?
a sort where you split lists into single elements and merge them back together