Algorithms and Concepts - Explained
Simply
1. Traffic Signal Algorithm
Definition:
Controls vehicle movement at intersections using signal lights (Red, Yellow, Green).
Algorithm Steps:
1. 1. Start the system.
2. 2. Turn GREEN → allow vehicles to move for 30 seconds.
3. 3. Turn YELLOW → show warning for 5 seconds.
4. 4. Turn RED → stop vehicles for 30 seconds.
5. 5. Repeat steps 2 to 4 continuously.
Example:
Example: Green = Go (30 sec), Yellow = Get Ready (5 sec), Red = Stop (30 sec).
Extra Concepts/Data:
Like process scheduling (e.g., one process runs, others wait). Data structure: Queue, Timer.
2. InVideo Algorithm
Definition:
Used in online video tools to edit videos automatically (scraping, trimming, sequencing).
Algorithm Steps:
6. 1. Accept video input.
7. 2. Scrape the video: extract frames and audio.
8. 3. Identify useful scenes and trim unnecessary parts.
9. 4. Sequence the remaining scenes in correct order.
10. 5. Apply transitions and effects.
11. 6. Generate final video output.
Example:
Input: Raw 5-minute lecture → Output: 3-minute highlights with cuts and transitions.
3. Shortest Path Algorithm (Dijkstra’s)
Definition:
Finds the shortest path between a source node and all other nodes in a graph.
Algorithm Steps:
12. 1. Set all node distances to ∞ except the start node (set to 0).
13. 2. Add all nodes to an unvisited set.
14. 3. Select the unvisited node with the smallest distance.
15. 4. For each neighbor of that node: calculate distance through current node; if new
distance < known distance, update it.
16. 5. Mark the current node as visited (remove from set).
17. 6. Repeat steps 3-5 until all nodes are visited.
Example:
Shortest path A → C = A → B → C = 7 in a weighted graph.
4. Transaction Management Algorithm
Definition:
Used in databases to manage safe execution of transactions (e.g., money transfer).
Algorithm Steps:
18. 1. Begin transaction.
19. 2. Lock required resources (e.g., accounts).
20. 3. Perform operation (e.g., withdraw from A, deposit in B).
21. 4. Check if all steps completed successfully.
22. 5. If yes → Commit changes; If no → Rollback changes.
23. 6. Release locks.
Example:
Example: Transfer Rs. 1000 from A to B → COMMIT. If any failure → ROLLBACK.
5. Bisection Algorithm
Definition:
Finds root of a function where f(a) and f(b) have opposite signs.
Algorithm Steps:
24. 1. Choose two values a and b such that f(a) * f(b) < 0.
25. 2. Calculate midpoint c = (a + b)/2.
26. 3. If f(c) is close to 0 (or within tolerance), return c as root.
27. 4. If f(a) × f(c) < 0, then root lies between a and c → set b = c.
28. 5. Else → root lies between c and b → set a = c.
29. 6. Repeat steps 2-5 until desired accuracy.
Example:
Example: f(x) = x² - 4, interval [1, 3], root = 2.
6. Graph Types and Definitions
Definition:
Explains dense/sparse graphs and tree structures used in graph algorithms.
Algorithm Steps:
30. 1. Start at a selected node.
31. 2. Mark the node as visited.
32. 3. Visit all unvisited neighbors recursively.
33. 4. Repeat until all reachable nodes are visited.
Example:
Tree Example: A → B, A → C (no cycles).
Extra Concepts/Data:
Dense = many edges; Sparse = few edges; Tree = no cycles and N-1 edges.
7. Randomization Algorithm
Definition:
Algorithm that uses random values during execution (e.g., picking random pivot).
Algorithm Steps:
34. 1. If array has 1 or 0 elements → return.
35. 2. Pick a random pivot from the array.
36. 3. Divide array into: Left < pivot, Right > pivot.
37. 4. Recursively apply steps on left and right parts.
38. 5. Combine left + pivot + right to get sorted array.
Example:
Array = [4, 1, 3, 2]; Random pivot = 3; Sorted = [1, 2, 3, 4].
Extra Concepts/Data:
Based on Probability, useful in AI, Simulations, Game Theory.