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?
Divide and conquer algorithm with a random pivot
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.
What is Dijkstra’s Formula?
Dijkstra’s algorithm is a greedy algorithm used to find the shortest path from a starting node to all other nodes in a graph, particularly when edge weights are non-negative. It’s widely used in networking, routing, and GPS applications.
What is the Space/Time of Dijkstra’s Formula?
Time: O((V + E) log V)
- Using min-heap
- With min_by? it’s O(V^2) because we iterate through the queue..
Space: O(V + E)
- V is the number of vertices (for storing distances and the priority queue).
- E is the number of edges (for storing the graph’s adjacency list).
What are the key steps of Dijkstra’s Formula?
Initialization:
distances = Hash.new(Float::Infinity)
distances[start_node] = 0
priority_queue = [[start_node, 0]] # or min-heap
visited = Set.new
Processing Nodes:
Get the node with the smallest distance
current_node, distance = priority_queue.min_by{|node, dist| dist}
priority_queue.delete([current_node, distance])
# Skip if the node is already visited
next if visited[current_node]
# Mark the current node as visited visited[current_node] = true
Further Optional Node Processing Here..
Iterate through the neighbors
If a shorter path is found, update and push to the priority queue
if new_distance < distances[neighbor]
distances[neighbor] = new_distance
priority_queue «_space;[neighbor, new_distance]
Termination:
Once all nodes are processed, the shortest distances from the start node to all other nodes are finalized.
