Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit aaf78f1

Browse filesBrowse files
abranheabranhe
authored
Merge pull request AllAlgorithms#44 from Bharat-Reddy/master
DP and GRAPHS
2 parents 3c11a76 + 5475939 commit aaf78f1
Copy full SHA for aaf78f1
Expand file treeCollapse file tree

17 files changed

+964
-0
lines changed

‎dynamic-programming/binomial_coefficient.py

Copy file name to clipboard
+24Lines 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

Copy file name to clipboard
+31Lines 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

Copy file name to clipboard
+23Lines 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

Copy file name to clipboard
+28Lines 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

Copy file name to clipboard
+31Lines 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

Copy file name to clipboard
+20Lines 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

Copy file name to clipboard
+69Lines 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

Copy file name to clipboard
+64Lines 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

Copy file name to clipboard
+56Lines 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 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.