Algorithms Flashcards
What is Breadth-First Search (BFS)
A graph traversal algorithm that explores all neighbors of a node before moving on to the next level of neighbors.
Space and Time Complexity of BFS?
O ( V + E )
O ( V ) - Each node is visited once
O ( E ) - Each edge is explored once
Key Steps of BFS
- Initialization
- Queue containing starting node
- Mark the starting node as visited - Main Loop
- While the queue is not empty..
– 1. dequeue front node of queue
– 2. process current node
– 3. for each unvisited neighbor of current node, A. mark neighbor visited, B. add neighbor to queue - Termination
- The algo ends when all reachable nodes have been visited
What is DFS ( Depth First Search ) ?
A graph traversal algorithm that explores each branch before backtracking.
DFS Space/Time complexity
O ( E + V )
Key Steps of DFS
- Start at a node ( Root or Arbitrary
- Mark Node as visited
- Explore Neighbors ( recursively, with same method )
- Backtrack, when all neighbors have been visited, explore other unexplored paths.
IE. The way water might fill a hollowed out root system. The water travels to the absolute depth first, and then begins to fill in the branches from the furthest bottom first working its way to the top.
What is Sliding Window Algorithm?
Technique used for finding a contiguous subarray (or sublist) of a fixed size in an array.
What is the Space/Time complexity of the Sliding Window Algorithm?
Time
O(n) traverses once for each shift.
Space
O(1) No additional space is required besides the initial input
Key Steps of the Sliding Window Algorithm?
Initialization :
- Setup the first window by [ performing window function ]
Sliding: Add the next element, remove the last element to keep window fixed size.
Update Result After each slide, update the result (min, max, etc. )
What is the Quick Sort Algo?
What are the Key Steps of the Quick Sort
- Picking a pivot element from the array.
- Partitioning the remaining elements into two groups: those less than the pivot and those greater than the pivot.
- Recursively sorting both groups.
- Finally, combining the sorted groups and the pivot into a single sorted array.
Space/Time complexity of Quick Sort
O(n log n) on average, but can degrade to O(n^2) if the pivot isn’t well chosen.