fundamentals of algorithms
No description yet. This curated deck is ready for daily study.
Card preview (24)
what are the two types of ways to traverse a graph
depth first breadth first
what is a graph
an abstract data type used to represent complex non linear relationships between objects using unordered set of nodes connected by edges -
describe depth first traversal
starts at root and follows one branch as far as it can go -used to navigate mazes
describe breadth first traversal
start at the root node and scan every connect node from left to right -finds the shortest path of an unweighted graph
what are the steps of depth first traversal
Visit the root node and push it onto the stack. Traverse on of the sub tree Visit each unvisited node in the sub tree and push them onto the stack When you get to a node with no other connections pop it of the stack If needed continue popping of nodes until you get to one connected to unvisited nodes When all the nodes are visited the visited array will show the order of traversal
what are the steps of breadth first traversal
Visit root node queue connected nodes Visited= [A] Queue=[B, D, E] From right to left visit connected nodes Dequeue each node as you visit its connected nodes Enqueue connected nodes Visited= [A,B] Queue=[D, E,C] Visited= [A,B,D] Queue=[E,C ,F]
what abstract data type is used for depth traversal
a stack
what abstract data type is used for breadth traversal
a queue
what are searching algorithms for
they are used to search for specific items in a data set
what are 3 types of searching algorithms
linear search algorithm binary search algorithm binary tree search algorithm
what is the time complexity of the linear search algorithm
O(n)
what is the time complexity of binary search algorithm
O(logn)
what is the time complexity of the binary tree search algorithm
O(logn)
how does the linear search algorithm work
-Linear search works by inspecting every item in a list one by one until the desired item (the target) is found. -If the target does not exist in the list, the algorithm will check every single item in the list before finishing
how does the binary search algorithm work
-The first step is to take the middle piece of data -To find the midpoint of the data, add the highest position and the lowest position of the array being considered, and divide by 2.
what search algorithm is used for ordered lists
binary search algorithms
what search algorithm is used for unordered lists
linear search algorithms
how does the binary tree search algorithm work
they function the same as binary search algorithms but are just applied to trees
what are sorting algorithms for
they are used to sort elements of an array into a specific order.
what are the two types of sorting algorithms
bubble sort merge sort
what is the time complexity of the merge sort
O( n log n )
what is the time complexity of the bubble sort
O(n^2)
how does the bubble sort work
bubble sorts makes passes through the data and swaps adjacent items until no swaps can be performed
how does the merge sort work
merge sorts split arrays into smaller lists and reform them using the divide and conquer method