| No. | Algorithm |
|---|---|
| 1 | Brute Force |
| 2 | Backtracking |
| 3 | Kadane's Algorithm |
| 4 | Depth First Search (DFS) |
| 5 | Breadth First Search (BFS) |
| 6 | Sliding Window |
| 7 | Dijkstra Algorithm |
| 8 | Floyd Warshall Algoithm |
| 9 | Bellman Ford Algorithm |
| 10 | Binary Search Algorithm |
| 11 | Floyd's Cycle Detection Algorithm (Hare-Tortoise Algorithm) |
| 12 | Union-Find |
It goes through all possible choices until the solution is found
For each element in the array
if element equal target value then
print success message
return its index
if element is not found
print Value not found message
return -1
Return all choices
For each element in the searchList
if element equal target value then
Add its index to a list of occurrences
if the list of occurrences is empty
raise ValueError
otherwise
return the list occurrences
Backtracking is used when searching for every possible combinations. It's check the subsequences/combinations/permutations of some group of letters/numbers. Based on Recursion.
Conceptually, one can imagine the procedure of backtracking as the tree traversal. Starting from the root node, one sets out to search for solutions that are located at the leaf nodes. Each intermediate node represents a partial candidate solution that could potentially lead us to a final valid solution. At each node, we would fan out to move one step further to the final solution, i.e. we iterate the child nodes of the current node. Once we can determine if a certain node cannot possibly lead to a valid solution, we abandon the current node and backtrack to its parent node to explore other possibilities.
def backtrack(candidate):
if find_solution(candidate):
output(candidate)
return
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)
- NQueens (Number of solutions).cpp
- Palindrome Partitioning (Number of palindrome).cpp
- Palindrome Partitioning (Number of palindrome).py
The DFS algorithm works as follows:
- Start by putting any one of the graph's vertices on top of a stack.
- Take the top item of the stack and add it to the visited list.
- Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.
- Keep repeating steps 2 and 3 until the stack is empty.
Note: A graph can have more than one DFS traversal.
Initialize an empty stack for storage of nodes, S.
For each vertex u, define u.visited to be false.
Push the root (first node to be visited) onto S.
While S is not empty:
Pop the first element in S, u.
If u.visited = false, then:
U.visited = true
for each unvisited neighbor w of u:
Push w into S.
End process when all nodes have been visited.
DFS is used for traverse or searsh in a tree or graph. Starting from the root node (level 0) then visiting all the nodes at the next level (level 1) before moving to the next level (level 2)
BFS(graph, source_node):
Define a Queue q
q.enqueue(source_node) # inserting s in queue until all its neighbour vertices are marked.
mark source_node as visited.
while (q is not empty)
# removing that vertex from queue, whose neighbour will be visited now
node = q.dequeue( )
# processing all the neighbours of the node
for all neighbours neighbour of node in graph
if neighbour is not visited
q.enqueue(neighbour) # Stores w in Q to further visit its neighbour
mark neighbour as visited.
It's used for optimizing loops.
- Maximum Number of Vowels in a Substring of Given Length(cpp)
- Maximum Number of Vowels in a Substring of Given Length(py)
An algorithm that is used to find the shortest path between two edges/nodes having non-negative edge values.
function dijkstra(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
If V != S, add V to Priority Queue Q
distance[S] <- 0
while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[]
It's used to search for an element in a sorted array
Ex1
Ex2
- Iteration Method
binarySearch(arr, x, low, high)
repeat till low = high
mid = (low + high)/2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
- Recursive Method (Divide and Conquer approach)
binarySearch(arr, x, low, high)
if low > high
return False
else
mid = (low + high) / 2
if x == arr[mid]
return mid
else if x > arr[mid] // x is on the right side
return binarySearch(arr, x, mid + 1, high)
else // x is on the left side
return binarySearch(arr, x, low, mid - 1)
Using two pointers(Hare & Tortoise) to traverse the sequence(Linked List) at differernt speeds
- Hare will reach the tail of the linked list(null), which means that there is no cycle in it.
- Hare will meet tortoise, which means that there is a cycle
- Initialize two-pointers and start traversing the linked list.
- Move the slow pointer by one position.
- Move the fast pointer by two positions.
- If both pointers meet at some point then a loop exists and if the fast pointer meets the end position then no loop exists.
It's used to Find subsets of elements and Union similar subsets together.
Initially create a parent[] array to keep track of the subsets.
Traverse through all the edges:
Check to which subset each of the nodes belong to by finding the parent[] array till the node and the parent are the same.
If the two nodes belong to the same subset then they belong to a cycle.
Otherwise, perform union operation on those two subsets.
If no cycle is found, return false.
func find( var element )
while ( element is not the root ) element = element's parent
return element
end func
func union( var setA, var setB )
var rootA = find( setA ), rootB = find( setB )
if ( rootA is equal to rootB ) return
else
set rootB as rootA's parent
end func