4.3 Fundamentals of algorithms Flashcards
(15 cards)
what are the types of graph traversals and the typical applications
breadth-first - shortest path for an unweighted graph
depth-first - navigating a maze
what are the types of tree traversals and the typical applications
pre-order - copying a tree
in-order - binary search tree, outputting the contents of a binary search tree in ascending order
post-order - infix to reverse polish notation conversions, producing a postfix expression, emptying a tree
why and where is reverse polish notation used
used for efficient expression evaluation in calculators and computers. It eliminates the need for brackets and operator precedence, making it ideal for stack-based evaluation and embedded systems.
what is the time complexity of a linear search
time complexity is O(n)
what is the time complexity of a binary search algorithm
time complexity is O(log n)
what is the time complexity of a binary tree search algorithm
time complexity is O(log n)
what is the time complexity of a bubble sort
time complexity is O(n^2) - considered inefficient sorting algorithm
what is the time complexity of a merge sort
time complexity is O(nlogn)
what is a linear search
A linear search checks each item in a list one by one until it finds the target or reaches the end. It works on both sorted and unsorted lists.
What is a binary search
Binary search is an efficient algorithm that finds a target value in a sorted list by repeatedly dividing the search interval in half. It compares the target to the middle element and eliminates half of the list each time.
What is a binary tree search
A binary tree search is a method used to find a value in a binary search tree. It starts at the root node and compares the target value to the current node. If the target is smaller, it moves to the left child; if larger, it moves to the right child. This process repeats until the value is found or there are no more nodes to check.
what is a bubble sort
Bubble sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. This process repeats until the list is sorted.
what is merge sort
Merge sort is a divide and conquer algorithm that splits a list into halves, recursively sorts each half, and then merges the sorted halves back together. It requires additional memory for the merging process.
What is Dijkstra’s shortest path algorithm
Dijkstra’s algorithm finds the shortest path from a starting node to all other nodes in a weighted graph with non-negative edges. It works by repeatedly selecting the node with the smallest known distance, updating the distances to its neighbors, and marking nodes as visited. It continues until all nodes have the shortest known distances from the start.
What are the applications of the shortest path algorithm
The shortest path algorithm is used in GPS navigation to find optimal routes, in network routing to send data efficiently and in social networks to find user connections
