Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms and Data Structures (Dynamic Programming (Description (Store…
Algorithms and Data Structures
Graphs
Algorithms
Breadth First Search (BFS)
References
Python Example
Exponential time complexity
Complete
Always able to find a solution, if there is one.
Use cases
Find shortest path of
unweighted
graphs :check:
Discover all vertex reachable from an initial vertex :check:
Depth First Search (DFS)
References
Python Example
DFS video
Use cases
Compute minimum spanning tree
Detect and find cycles in a graph
Check if a graph is bipartite
Find strongly connected components
Topologically sort the nodes of a graph :check:
Find bridges and articulation points
Find augmenting paths in a flow network.
Generate mazes.
Shortest Path
Dijkstra
Single Source Shortest Path (SSSP)
Need to specify the initial node
Only works with non-negative edge weights
This allows Dijkstra to be greedy and select
the next most promising node
Time complexity of \(O(E*log(V))\)
Minimum Spanning Tree
Requirement: Undirected graph with weighted edges
It is useful to implement undirected graph using an adjacency list (A-> B and B->A)
MST is a subset of the edges in the graph which connects all vertices together (without creating cycles) while minimizing the total edge cost.
Prim's MST Algorithm
Greedy MST algorithm
Works well on dense graphs
Heap
Python Example
Big O
Python Time Complexity Table
Sorting and Searching
Linked List
Dynamic Programming
Reference
Geeks for Geeks videos
Geeks for Geeks articles
Description
Store result of sub-problems to avoid re-compute them later
DP allows reduction of time complexity from exponential to polynomial.
Is mainly an optimization over plain recursion when there are repeated calls for same input
Use cases
Examples:
Fibonacci sequence
Knapsack problem
Solving DP problems
2 - Deciding the state
. State can be defined as the set of parameters that uniquely identify a certain position in the given problem. This set of parameters should be as small as possible to reduce state space.
1 - Identify if it is a DP problem
. Problems where we need to minimize/maximize certain quantity or counting problems under certain arrangements or probabilities.
3 - Defining relation among states
Recursion
Trees
Number Theory
Bit manipulation
String / Array
Check this:
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/
Algorithm repositories
CCPS 109 CS I
Awesome hints to identify algorithm patterns
here as well
https://github.com/jwasham/coding-interview-university#the-daily-plan
https://www.topcoder.com/community/competitive-programming/tutorials/how-to-dissect-a-topcoder-problem-statement/