Skip to content

Commit aaf78f1

Browse files
abranheabranhe
authored
Merge pull request AllAlgorithms#44 from Bharat-Reddy/master
DP and GRAPHS
2 parents 3c11a76 + 5475939 commit aaf78f1

17 files changed

Lines changed: 964 additions & 0 deletions

‎dynamic-programming/binomial_coefficient.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
# A Dynamic Programming based solution to compute nCr % p
2+
3+
# Returns nCr % p
4+
def nCrModp(n, r, p):
5+
6+
7+
C = [0 for i in range(r+1)]
8+
9+
C[0] = 1 # Top row of Pascal Triangle
10+
11+
for i in range(1, n+1):
12+
13+
for j in range(min(i, r), 0, -1):
14+
15+
# nCj = (n - 1)Cj + (n - 1)C(j - 1)
16+
C[j] = (C[j] + C[j-1]) % p
17+
18+
return C[r]
19+
20+
# Driver Program
21+
n = 10
22+
r = 2
23+
p = 13
24+
print('Value of nCr % p is', nCrModp(n, r, p))

‎dynamic-programming/coin_change.py‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
# Dynamic Programming Python implementation of Coin Change
2+
3+
def count(S, m, n):
4+
5+
# case (n = 0)
6+
table = [[0 for x in range(m)] for x in range(n+1)]
7+
8+
# Fill the entries for 0 value case (n = 0)
9+
for i in range(m):
10+
table[0][i] = 1
11+
12+
# Fill rest of the table entries in bottom up manner
13+
for i in range(1, n+1):
14+
for j in range(m):
15+
16+
# Count of solutions including S[j]
17+
x = table[i - S[j]][j] if i-S[j] >= 0 else 0
18+
19+
# Count of solutions excluding S[j]
20+
y = table[i][j-1] if j >= 1 else 0
21+
22+
# total count
23+
table[i][j] = x + y
24+
25+
return table[n][m-1]
26+
27+
# Driver program to test above function
28+
arr = [1, 2, 3]
29+
m = len(arr)
30+
n = 4
31+
print(count(arr, m, n))

‎dynamic-programming/knapsack.py‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
# A Dynamic Programming based Python Program for 0-1 Knapsack problem
2+
# Returns the maximum value that can be put in a knapsack of capacity W
3+
def knapSack(W, wt, val, n):
4+
K = [[0 for x in range(W+1)] for x in range(n+1)]
5+
6+
# Build table K[][] in bottom up manner
7+
for i in range(n+1):
8+
for w in range(W+1):
9+
if i==0 or w==0:
10+
K[i][w] = 0
11+
elif wt[i-1] <= w:
12+
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
13+
else:
14+
K[i][w] = K[i-1][w]
15+
16+
return K[n][W]
17+
18+
# Driver program to test above function
19+
val = [60, 100, 120]
20+
wt = [10, 20, 30]
21+
W = 50
22+
n = len(val)
23+
print(knapSack(W, wt, val, n))

‎dynamic-programming/lcs.py‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# Dynamic Programming implementation of LCS problem
2+
3+
def lcs(X , Y):
4+
# find the length of the strings
5+
m = len(X)
6+
n = len(Y)
7+
8+
# declaring the array for storing the dp values
9+
L = [[None]*(n+1) for i in xrange(m+1)]
10+
11+
for i in range(m+1):
12+
for j in range(n+1):
13+
if i == 0 or j == 0 :
14+
L[i][j] = 0
15+
elif X[i-1] == Y[j-1]:
16+
L[i][j] = L[i-1][j-1]+1
17+
else:
18+
L[i][j] = max(L[i-1][j] , L[i][j-1])
19+
20+
# L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
21+
return L[m][n]
22+
#end of function lcs
23+
24+
25+
# Driver program to test the above function
26+
X = "AGGTAB"
27+
Y = "GXTXAYB"
28+
print "Length of LCS is ", lcs(X, Y)

‎dynamic-programming/longest_increasing_subsequence.py‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
# Dynamic programming Python implementation of LIS problem
2+
3+
# lis returns length of the longest increasing subsequence
4+
# in arr of size n
5+
def lis(arr):
6+
n = len(arr)
7+
8+
# Declare the list (array) for LIS and initialize LIS
9+
# values for all indexes
10+
lis = [1]*n
11+
12+
# Compute optimized LIS values in bottom up manner
13+
for i in range (1 , n):
14+
for j in range(0 , i):
15+
if arr[i] > arr[j] and lis[i]< lis[j] + 1 :
16+
lis[i] = lis[j]+1
17+
18+
# Initialize maximum to 0 to get the maximum of all
19+
# LIS
20+
maximum = 0
21+
22+
# Pick maximum of all LIS values
23+
for i in range(n):
24+
maximum = max(maximum , lis[i])
25+
26+
return maximum
27+
# end of lis function
28+
29+
# Driver program to test above function
30+
arr = [10, 22, 9, 33, 21, 50, 41, 60]
31+
print "Length of lis is", lis(arr)

‎dynamic-programming/rod_cutting_problem.py‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
# A Dynamic Programming solution for Rod cutting problem
2+
3+
INT_MIN = -32767
4+
5+
def cutRod(price, n):
6+
val = [0 for x in range(n+1)]
7+
val[0] = 0
8+
9+
for i in range(1, n+1):
10+
max_val = INT_MIN
11+
for j in range(i):
12+
max_val = max(max_val, price[j] + val[i-j-1])
13+
val[i] = max_val
14+
15+
return val[n]
16+
17+
# Driver program to test above functions
18+
arr = [1, 5, 8, 9, 10, 17, 17, 20]
19+
size = len(arr)
20+
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))

‎graphs/bellman_ford.py‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
# Python program for Bellman-Ford's single source
2+
# shortest path algorithm.
3+
4+
from collections import defaultdict
5+
6+
#Class to represent a graph
7+
class Graph:
8+
9+
def __init__(self,vertices):
10+
self.V= vertices #No. of vertices
11+
self.graph = [] # default dictionary to store graph
12+
13+
# function to add an edge to graph
14+
def addEdge(self,u,v,w):
15+
self.graph.append([u, v, w])
16+
17+
# utility function used to print the solution
18+
def printArr(self, dist):
19+
print("Vertex Distance from Source")
20+
for i in range(self.V):
21+
print("%d \t\t %d" % (i, dist[i]))
22+
23+
# The main function that finds shortest distances from src to
24+
# all other vertices using Bellman-Ford algorithm. The function
25+
# also detects negative weight cycle
26+
def BellmanFord(self, src):
27+
28+
# Step 1: Initialize distances from src to all other vertices
29+
# as INFINITE
30+
dist = [float("Inf")] * self.V
31+
dist[src] = 0
32+
33+
34+
# Step 2: Relax all edges |V| - 1 times. A simple shortest
35+
# path from src to any other vertex can have at-most |V| - 1
36+
# edges
37+
for i in range(self.V - 1):
38+
# Update dist value and parent index of the adjacent vertices of
39+
# the picked vertex. Consider only those vertices which are still in
40+
# queue
41+
for u, v, w in self.graph:
42+
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
43+
dist[v] = dist[u] + w
44+
45+
# Step 3: check for negative-weight cycles. The above step
46+
# guarantees shortest distances if graph doesn't contain
47+
# negative weight cycle. If we get a shorter path, then there
48+
# is a cycle.
49+
50+
for u, v, w in self.graph:
51+
if dist[u] != float("Inf") and dist[u] + w < dist[v]:
52+
print "Graph contains negative weight cycle"
53+
return
54+
55+
# print all distance
56+
self.printArr(dist)
57+
58+
g = Graph(5)
59+
g.addEdge(0, 1, -1)
60+
g.addEdge(0, 2, 4)
61+
g.addEdge(1, 2, 3)
62+
g.addEdge(1, 3, 2)
63+
g.addEdge(1, 4, 2)
64+
g.addEdge(3, 2, 5)
65+
g.addEdge(3, 1, 1)
66+
g.addEdge(4, 3, -3)
67+
68+
#Print the solution
69+
g.BellmanFord(0)

‎graphs/bfs.py‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
# Python3 Program to print BFS traversal
2+
# from a given source vertex. BFS(int s)
3+
# traverses vertices reachable from s.
4+
from collections import defaultdict
5+
6+
# This class represents a directed graph
7+
# using adjacency list representation
8+
class Graph:
9+
10+
# Constructor
11+
def __init__(self):
12+
13+
# default dictionary to store graph
14+
self.graph = defaultdict(list)
15+
16+
# function to add an edge to graph
17+
def addEdge(self,u,v):
18+
self.graph[u].append(v)
19+
20+
# Function to print a BFS of graph
21+
def BFS(self, s):
22+
23+
# Mark all the vertices as not visited
24+
visited = [False] * (len(self.graph))
25+
26+
# Create a queue for BFS
27+
queue = []
28+
29+
# Mark the source node as
30+
# visited and enqueue it
31+
queue.append(s)
32+
visited[s] = True
33+
34+
while queue:
35+
36+
# Dequeue a vertex from
37+
# queue and print it
38+
s = queue.pop(0)
39+
print (s, end = " ")
40+
41+
# Get all adjacent vertices of the
42+
# dequeued vertex s. If a adjacent
43+
# has not been visited, then mark it
44+
# visited and enqueue it
45+
for i in self.graph[s]:
46+
if visited[i] == False:
47+
queue.append(i)
48+
visited[i] = True
49+
50+
# Driver code
51+
52+
# Create a graph given in
53+
# the above diagram
54+
g = Graph()
55+
g.addEdge(0, 1)
56+
g.addEdge(0, 2)
57+
g.addEdge(1, 2)
58+
g.addEdge(2, 0)
59+
g.addEdge(2, 3)
60+
g.addEdge(3, 3)
61+
62+
print ("Following is Breadth First Traversal"
63+
" (starting from vertex 2)")
64+
g.BFS(2)

‎graphs/cycle_in_directed.py‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
# Python program to detect cycle
2+
# in a graph
3+
4+
from collections import defaultdict
5+
6+
class Graph():
7+
def __init__(self,vertices):
8+
self.graph = defaultdict(list)
9+
self.V = vertices
10+
11+
def addEdge(self,u,v):
12+
self.graph[u].append(v)
13+
14+
def isCyclicUtil(self, v, visited, recStack):
15+
16+
# Mark current node as visited and
17+
# adds to recursion stack
18+
visited[v] = True
19+
recStack[v] = True
20+
21+
# Recur for all neighbours
22+
# if any neighbour is visited and in
23+
# recStack then graph is cyclic
24+
for neighbour in self.graph[v]:
25+
if visited[neighbour] == False:
26+
if self.isCyclicUtil(neighbour, visited, recStack) == True:
27+
return True
28+
elif recStack[neighbour] == True:
29+
return True
30+
31+
# The node needs to be poped from
32+
# recursion stack before function ends
33+
recStack[v] = False
34+
return False
35+
36+
# Returns true if graph is cyclic else false
37+
def isCyclic(self):
38+
visited = [False] * self.V
39+
recStack = [False] * self.V
40+
for node in range(self.V):
41+
if visited[node] == False:
42+
if self.isCyclicUtil(node,visited,recStack) == True:
43+
return True
44+
return False
45+
46+
g = Graph(4)
47+
g.addEdge(0, 1)
48+
g.addEdge(0, 2)
49+
g.addEdge(1, 2)
50+
g.addEdge(2, 0)
51+
g.addEdge(2, 3)
52+
g.addEdge(3, 3)
53+
if g.isCyclic() == 1:
54+
print "Graph has a cycle"
55+
else:
56+
print "Graph has no cycle"

0 commit comments

Comments
 (0)