Unit 3 Flashcards
(15 cards)
breath-first traversal
fastest path, uses queue, adjacent vertices on same level first
-not discovered
-visited
-fully discovered
depth-first
navigating a maze, uses stack, follows row until fully read, destacks and checks next option, critical path
dijstra’s algorithm
shortest/least expensive fight
tree traversal
pre-order and in-order and post-order
subroutine tree traversal
SUBROUTINE order (tree_node)
OUTPUT (tree_node.value) = pre-order
IF tree_node.left != NULL THEN
order (tree_node.left)
ENDIF
OUTPUT (tree_node.value) = in-order
IF tree_node.right!= NULL THEN
order (tree_node.right)
ENDIF
OUTPUT (tree_node.value) = post-order
END SUBROUTINE
binary tree search
-O(logn)
-to insert: go left if smaller, right if larger and insert appropriately
-to find: same procedure
reverse polish
suitable to use stack to evaluate, unambiguous and eliminates need of brackets, uses post fix notation
using tree to convert arithmetics
in order, in fix = normal
post order, post fix = reverse polish
pre-order, pre fix = polish
using stack with reverse polish
convert expression into RPN, push items onto stack
if item is an operator a. pop last two items off and apply operator b. push result onto stack
repeat til done
linear search
goes through every item in linear fashion
-stored as array
binary search
list has to be sorted, looks at middle item and then splits up list
binary and linear search speed comaprison
up to size of roughly 17, linear faster, after binary faster
bubble sort
very time INefficient sorting algorithm, time efficiency O(n2) time efficiency O(1), compares adjacent values and swaps around until sorted
merge sort
time complexity of O(nlogn) space complexity O(n), splits up list until pairs of two and then puts it back together
complexities
