cl1p.net - The internet clipboard

cl1p.net - The internet clipboard CL1P.NET V4. Info

cl1p.net/xbmc_log

This cl1p will be deleted in in 14 days.

EXERCISE 1
1.	Write a program to find GCD of two numbers using different algorithms Euclid’s Algorithm and Consecutive Integer Checking Algorithm
def gcde(m,n): if m< n:
(m,n) = (n,m) while n!=0:
r=m % n m=n n=r
return m

def gcdc(m,n): t=min(m, n) while t > 0:
if m % t == 0 and n % t == 0: return t
t =t - 1

print("Program to find the GCD of 2 numbers using:") print("1: Euclid's Algorithm")
m = int(input("enter first number: "))
n = int(input("enter second number: ")) print(gcde(m,n))
print("2: Consecutive Integer Checking Algorithm")
m = int(input("enter first number: "))
n = int(input("enter second number: ")) print(gcdc(m,n))
 
Output: 
Program to find the GCD of 2 numbers using: 1: Euclid's Algorithm

enter first number: 5

enter second number: 10 5
2: Consecutive Integer Checking Algorithm enter first number: 5
enter second number: 10 5

1.b) Write a program to Implement Sieve of Eratosthenes to generate Prime Numbers Between Given Range

def SieveOfEratosthenes(n):

prime = [True for i in range(n + 1)] p = 2
while (p * p <= n):

if (prime[p] == True):

for i in range(p * 2, n + 1, p): prime[i] = False
p += 1
prime[0]= False prime[1]= False
for p in range(n + 1): if prime[p]:
print p,

if		name ==' main ': n = 30
print "Following are the prime numbers " SieveOfEratosthenes(n)

Output: 
enter the value of n10
Following are the prime numbers
[True, True, True, True, True, True, True, True, True, True, True] 4 False
6 False
8 False
10 False
6 False
9 False
2 True
3 True
5 True
7 True

........................................................................................................................................................................................................................................................................................................................................................................................................................

EXERCISE 2
2.	Develop a program to perform string matching using the Rabin-Karp algorithm
# Rabin-Karp algorithm in python d = 10
def search(pattern, text, q):
m = len(pattern)
n = len(text) p = 0
t = 0
h = 1
i = 0
j = 0

for i in range(m-1): h = (h*d) % q

# Calculate hash value for pattern and text for i in range(m):
p = (d*p + ord(pattern[i])) % q t = (d*t + ord(text[i])) % q
# Find the match
for i in range(n-m+1): if p == t:
for j in range(m):
if text[i+j] != pattern[j]: break

j += 1
if j == m:
print("Pattern is found at position: " + str(i+1))
if i < n-m:
t = (d*(t-ord(text[i])*h) + ord(text[i+m])) % q

if t < 0:
t = t+q

text = "ABCCDDAEFG"
pattern = "CDD" q = 13
search(pattern, text, q)

OUTPUT :

Pattern is found at position: 4
........................................................................................................................................................................................................................................................................................................................................................................................................................
EXERCISE 3

3.	Examine the time complexity of Merge Sort through the application of the divide and conquer technique

def merge_sort(alist, start, end):
'''Sorts the list from indexes start to end - 1 inclusive.''' if end - start > 1:
mid = (start + end)//2 merge_sort(alist, start, mid) merge_sort(alist, mid, end) merge_list(alist, start, mid, end)
def merge_list(alist, start, mid, end): left = alist[start:mid]
right = alist[mid:end] k = start
i = 0
j = 0
while (start + i < mid and mid + j < end): if (left[i] <= right[j]):
alist[k] = left[i] i = i + 1
else:
alist[k] = right[j]
j = j + 1
k = k + 1
if start + i < mid: while k < end:
alist[k] = left[i] i = i + 1
k = k + 1
else:
while k < end: alist[k] = right[j]
j = j + 1
k = k + 1
alist = input('Enter the list of numbers: ').split() print(alist)
alist = [int(x) for x in alist] merge_sort(alist, 0, len(alist)) print('Sorted list: ', end='') print(alist)

OUTPUT:
Enter the list of numbers: 10 3 4 5 76
['10', '3', '4', '5', '76']
Sorted list: [3, 4, 5, 10, 76]

EXERCISE 4
4.	Examine the time complexity of Quick Sort employing the divide and conquer technique
def quicksort(alist, start, end):
'''Sorts the list from indexes start to end - 1 inclusive.''' if end - start > 1:
p = partition(alist, start, end) quicksort(alist, start, p) quicksort(alist, p + 1, end)
def partition(alist, start, end): pivot = alist[start]
i = start + 1
j = end - 1 while True:
while (i <= j and alist[i] <= pivot): i = i + 1
while (i <= j and alist[j] >= pivot): j = j - 1
if i <= j:
alist[i], alist[j] = alist[j], alist[i] else:
alist[start], alist[j] = alist[j], alist[start] return j
alist = input('Enter the list of numbers: ').split() alist = [int(x) for x in alist]
quicksort(alist, 0, len(alist)) print('Sorted list: ', end='') print(alist)

OUTPUT:

Enter the list of numbers: 20 3 1 56 43
Sorted list: [1, 3, 20, 43, 56]

EXERCISE 5

a)	Create a program for executing Breadth-First Search (BFS) on aspecified graph
b)	Develop a program to execute Depth-First Search (DFS) on aprovided graph.

a)	BFS
graph = { '5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = [] # List for visited nodes. queue = []	#Initialize a queue
def bfs(visited, graph, node): #function for BFS visited.append(node)
queue.append(node)
while queue:	# Creating loop to visit each node m = queue.pop(0)
print (m, end = " ")

for neighbour in graph[m]:
if neighbour not in visited: visited.append(neighbour) queue.append(neighbour)
# Driver Code
print("Following is the Breadth-First Search") bfs(visited, graph, '5')	# function calling

OUTPUT:
Following is the Breadth-First Search 5 3 7 2 4 8
 
b)	DFS
graph = { '5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node): #function for dfs if node not in visited:
print (node) visited.add(node)
for neighbour in graph[node]: dfs(visited, graph, neighbour)

# Driver Code
print("Following is the Depth-First Search") dfs(visited, graph, '5')

OUTPUT :
Following is the Depth-First Search 5
3
2
4
8
7
........................................................................................................................................................................................................................................................................................................................................................................................................................

EXERCISE 6

6.	Develop a program that implements the Topological Sorting algorithm, allowing the systematic arrangement of elements in a directed acyclic graph (DAG) based on their dependencies and order of execution.
from collections import defaultdict class Graph:
def   init (self,vertices):
self.graph = defaultdict(list) #dictionary containing adjacency List self.V = vertices #No. of vertices
def addEdge(self,u,v): self.graph[u].append(v)
def topologicalSortUtil(self,v,visited,stack): visited[v] = True
for i in self.graph[v]:
if visited[i] == False: self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
def topologicalSort(self): visited = [False]*self.V stack =[]
for i in range(self.V):
if visited[i] == False: self.topologicalSortUtil(i,visited,stack)
print stack

g= Graph(6) g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);

print "Following is a Topological Sort of the given graph" g.topologicalSort()

OUTPUT:
The Topological Sort Of The Graph Is: [False, False, False, False, False]
[] 0
[True, False, False, False, False] [True, True, False, False, False] [True, True, True, False, False] [True, True, True, True, False] [True, True, True, True, True] [0, 1, 2, 3, 4]

............................................................................................................................................................................................................
............................................................................................................................................................................................................
EXERCISE 7

7.	Design a program that utilizes Prim's Algorithm to determine the minimum cost-spanning tree within a given graph. This algorithm systematically selects edges while ensuring that the resulting tree remains connected and has the lowest possible total edge weight.

INF = 9999999
# number of vertices in graph V = 5
# create a 2d array of size 5x5
# for adjacency matrix to represent graph G = [[0, 9, 75, 0, 0],
[9, 0, 95, 19, 42],
[75, 95, 0, 51, 66],
[0, 19, 51, 0, 31],
[0, 42, 66, 31, 0]]
# create a array to track selected vertex
# selected will become true otherwise false selected = [0, 0, 0, 0, 0]
# set number of edge to 0 no_edge = 0
# the number of egde in minimum spanning tree will be
# always less than(V - 1), where V is number of vertices in # graph
# choose 0th vertex and make it true selected[0] = True
# print for edge and weight print("Edge : Weight\n") while (no_edge < V - 1):
# For every vertex in the set S, find the all adjacent vertices #, calculate the distance from the vertex selected at step 1. # if the vertex is already in the set S, discard it otherwise
# choose another vertex nearest to selected vertex at step 1. minimum = INF
x = 0
y = 0
for i in range(V): if selected[i]:
for j in range(V):
if ((not selected[j]) and G[i][j]):
# not in selected and there is an edge if minimum > G[i][j]:
minimum = G[i][j] x = i
y = j
print(str(x) + "-" + str(y) + ":" + str(G[x][y])) selected[y] = True
no_edge += 1
 
OUTPUT:
Edge : Weight
0-1:9
1-3:19
3-4:31
3-2:51
........................................................................................................................................................................................................................................................................................................................................................................................................................

EXERCISE 8

8.	Create a comprehensive program that utilizes Dijkstra's Algorithm to determine the shortest path between nodes in a given graph. This algorithm systematically explores and updates the distances from a selected source node to all other nodes, ensuring an efficient and accurate path calculation
import sys class Graph():
def   init (self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)] for row in range(vertices)]
def printSolution(self, dist): print("Vertex tDistance from Source") for node in range(self.V):
print(node, "t", dist[node])
def minDistance(self, dist, sptSet): min = sys.maxsize
for v in range(self.V):
if dist[v] < min and sptSet[v] == False: min = dist[v]
min_index = v return min_index
def dijkstra(self, src):
dist = [sys.maxsize] * self.V dist[src] = 0
sptSet = [False] * self.V for cout in range(self.V):
u = self.minDistance(dist, sptSet) sptSet[u] = True
for v in range(self.V):
if self.graph[u][v] > 0 and sptSet[v] == False and
dist[v] > dist[u] + self.graph[u][v]: dist[v] = dist[u] + self.graph[u][v]
self.printSolution(dist)

g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]

g.dijkstra(0)
 OUTPUT:
4
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

entere the source: 0 0
Measuring the Distance of the Vertex from Source distance from 0 to 0 is 0
distance from 0 to 1 is 2
distance from 0 to 2 is 5
distance from 0 to 3 is 3
........................................................................................................................................................................................................................................................................................................................................................................................................................

EXERCISE 9

9.	Design a program that calculates the Binomial Coefficient, often denoted as C(n, r), representing the number of ways to choose 'r'items from a set of 'n' items without regard to the order of selection. This program should provide an efficient and accurate method fordetermining this combinatorial value
def binomialCoef(n, k):
C = [[0 for x in range(k+1)] for x in range(n+1)] for i in range(n+1):
for j in range(min(i, k)+1): # Base Cases
if j == 0 or j == i:
C[i][j] = 1
else:
C[i][j] = C[i-1][j-1] + C[i-1][j]
return C[n][k]
n = 5
k = 2
print("Value of C[" + str(n) + "][" + str(k) + "] is " + str(binomialCoef(n, k)))

OUTPUT:
[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
Value of C[5][2] is 10
........................................................................................................................................................................................................................................................................................................................................................................................................................

EXERCISE 10

10.	Develop a comprehensive program that employs the Backtracking technique to solve the N Queens problem. This classic problem involvesplacing 'N' chess queens on an 'N x N' chessboard in such a way that no two queens threaten each other, ensuring that no queen can attack any other queen horizontally, vertically, or diagonally.
# Taking number of queens as input from user print ("Enter the number of queens")
N = int(input())
# here we create a chessboard
# NxN matrix with all elements set to 0 board = [[0]*N for _ in range(N)]
def attack(i, j):
#checking vertically and horizontally for k in range(0,N):
if board[i][k]==1 or board[k][j]==1: return True
#checking diagonally for k in range(0,N):
for l in range(0,N):
if (k+l==i+j) or (k-l==i-j): if board[k][l]==1:
return True return False
def N_queens(n): if n==0:
return True
for i in range(0,N): for j in range(0,N):
if (not(attack(i,j))) and (board[i][j]!=1): board[i][j] = 1
if N_queens(n-1)==True: return True
board[i][j] = 0 return False
N_queens(N) for i in board: print (i)

OUTPUT:
Enter the number of queens

4
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
chat gpt

ex:1:
def euclid_gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def consecutive_integer_gcd(a, b):
    smaller = min(a, b)
    gcd = 1
    for i in range(1, smaller + 1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

# Example usage:
num1 = 36
num2 = 24

# Using Euclid's algorithm
gcd_euclid = euclid_gcd(num1, num2)
print("GCD using Euclid's algorithm:", gcd_euclid)

# Using consecutive integer checking algorithm
gcd_consecutive = consecutive_integer_gcd(num1, num2)
print("GCD using consecutive integer checking algorithm:", gcd_consecutive)

ex:1(B):def sieve_of_eratosthenes(start, end):
    primes = []
    sieve = [True] * (end + 1)
    sieve[0] = sieve[1] = False

for num in range(2, int(end ** 0.5) + 1):
        if sieve[num]:
            for multiple in range(num * num, end + 1, num):
                sieve[multiple] = False

for num in range(max(2, start), end + 1):
        if sieve[num]:
            primes.append(num)

return primes

# Example usage:
start_range = 10
end_range = 50

prime_numbers = sieve_of_eratosthenes(start_range, end_range)
print("Prime numbers between", start_range, "and", end_range, "are:", prime_numbers)
........................................................................................................................................................................................................................................................................................................................................................................................................................
EX:2:
def rabin_karp(text, pattern):
    if not text or not pattern:
        return -1

text_len = len(text)
    pattern_len = len(pattern)

# Calculate the hash of the pattern
    pattern_hash = 0
    text_hash = 0
    prime = 101
    radix = 256

for i in range(pattern_len):
        pattern_hash = (radix * pattern_hash + ord(pattern[i])) % prime
        text_hash = (radix * text_hash + ord(text[i])) % prime

for i in range(text_len - pattern_len + 1):
        if pattern_hash == text_hash:
            if text[i:i + pattern_len] == pattern:
                return i

# Rolling hash calculation
        if i < text_len - pattern_len:
            text_hash = (radix * (text_hash - ord(text[i]) * (radix ** (pattern_len - 1))) + ord(text[i + pattern_len])) % prime
            if text_hash < 0:
                text_hash += prime

return -1

# Example usage:
text = "ababcabcabababd"
pattern = "ababd"
index = rabin_karp(text, pattern)
if index != -1:
    print("Pattern found at index:", index)
else:
    print("Pattern not found in the text.")
........................................................................................................................................................................................................................................................................................................................................................................................................................

EX:3:
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

# Recursively sort the two halves
        merge_sort(left_half)
        merge_sort(right_half)

# Merge the sorted halves
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Sorted array:", arr)
 
EX:4:
def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Example usage:
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("Sorted array:", arr)
 ........................................................................................................................................................................................................................................................................................................................................................................................................................EX:5:(a)
from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

def add_edge(self, u, v):
        self.graph[u].append(v)

def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)

while queue:
            vertex = queue.popleft()
            print(vertex, end=' ')

for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

# Example usage:
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("BFS Traversal starting from vertex 2:")
g.bfs(2)

EX:5(b)
from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

def add_edge(self, u, v):
        self.graph[u].append(v)

def dfs_util(self, vertex, visited):
        visited.add(vertex)
        print(vertex, end=' ')

for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                self.dfs_util(neighbor, visited)

def dfs(self, start):
        visited = set()
        self.dfs_util(start, visited)

# Example usage:
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("DFS Traversal starting from vertex 2:")
g.dfs(2)
........................................................................................................................................................................................................................................................................................................................................................................................................................EX:6:
from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

def add_edge(self, u, v):
        self.graph[u].append(v)

def topological_sort_util(self, vertex, visited, stack):
        visited.add(vertex)

for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                self.topological_sort_util(neighbor, visited, stack)

stack.append(vertex)

def topological_sort(self):
        visited = set()
        stack = []

for vertex in list(self.graph):
            if vertex not in visited:
                self.topological_sort_util(vertex, visited, stack)

return stack[::-1]

# Example usage:
g = Graph()
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

print("Topological Sorting of the given graph:")
print(g.topological_sort())
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
EX:7:
import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

def add_edge(self, u, v, weight):
        self.graph[u][v] = weight
        self.graph[v][u] = weight  # Graph is undirected

def min_key(self, key, mst_set):
        min_val = sys.maxsize
        min_index = -1

for v in range(self.V):
            if key[v] < min_val and not mst_set[v]:
                min_val = key[v]
                min_index = v

return min_index

def prim_mst(self):
        parent = [-1] * self.V
        key = [sys.maxsize] * self.V
        mst_set = [False] * self.V

key[0] = 0  # Start from the first vertex

for _ in range(self.V - 1):
            u = self.min_key(key, mst_set)
            mst_set[u] = True

for v in range(self.V):
                if self.graph[u][v] > 0 and not mst_set[v] and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

# Print the minimum spanning tree
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

# Example usage:
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 8)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)

g.prim_mst()
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
EX:8:
import sys

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]

def add_edge(self, u, v, weight):
        self.graph[u][v] = weight
        self.graph[v][u] = weight  # Graph is undirected

def min_distance(self, dist, spt_set):
        min_val = sys.maxsize
        min_index = -1

for v in range(self.V):
            if dist[v] < min_val and not spt_set[v]:
                min_val = dist[v]
                min_index = v

return min_index

def dijkstra(self, src):
        dist = [sys.maxsize] * self.V
        dist[src] = 0
        spt_set = [False] * self.V

for _ in range(self.V):
            u = self.min_distance(dist, spt_set)
            spt_set[u] = True

for v in range(self.V):
                if self.graph[u][v] > 0 and not spt_set[v] and dist[v] > dist[u] + self.graph[u][v]:
                    dist[v] = dist[u] + self.graph[u][v]

self.print_solution(dist)

def print_solution(self, dist):
        print("Vertex \tDistance from Source")
        for i in range(self.V):
            print(i, "\t", dist[i])

# Example usage:
g = Graph(9)
g.add_edge(0, 1, 4)
g.add_edge(0, 7, 8)
g.add_edge(1, 2, 8)
g.add_edge(1, 7, 11)
g.add_edge(2, 3, 7)
g.add_edge(2, 8, 2)
g.add_edge(2, 5, 4)
g.add_edge(3, 4, 9)
g.add_edge(3, 5, 14)
g.add_edge(4, 5, 10)
g.add_edge(5, 6, 2)
g.add_edge(6, 7, 1)
g.add_edge(6, 8, 6)
g.add_edge(7, 8, 7)

g.dijkstra(0)
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
EX:9:
def binomial_coefficient(n, r):
    # Create a 2D table to store the binomial coefficients
    dp = [[0] * (r + 1) for _ in range(n + 1)]

# Base cases: C(n, 0) = 1 and C(n, n) = 1
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, r + 1):
        dp[i][i] = 1

# Fill the table using the recurrence relation: C(n, r) = C(n-1, r-1) + C(n-1, r)
    for i in range(1, n + 1):
        for j in range(1, min(i, r) + 1):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

return dp[n][r]

# Example usage:
n = 5
r = 2
result = binomial_coefficient(n, r)
print("Binomial Coefficient C({},{}) = {}".format(n, r, result))
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
EX:10:
def is_safe(board, row, col, N):
    # Check if there's a queen in the same column
    for i in range(row):
        if board[i][col] == 1:
            return False

# Check upper left diagonal
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

# Check upper right diagonal
    for i, j in zip(range(row, -1, -1), range(col, N)):
        if board[i][j] == 1:
            return False

return True

def solve_n_queens_util(board, row, N, result):
    if row == N:
        result.append([row[:] for row in board])
        return

for col in range(N):
        if is_safe(board, row, col, N):
            board[row][col] = 1
            solve_n_queens_util(board, row + 1, N, result)
            board[row][col] = 0

def solve_n_queens(N):
    board = [[0] * N for _ in range(N)]
    result = []
    solve_n_queens_util(board, 0, N, result)
    return result

def print_board(board):
    for row in board:
        print(" ".join(map(str, row)))
    print()

# Example usage:
N = 4
solutions = solve_n_queens(N)
print("Number of solutions for N =", N, ":", len(solutions))
for idx, solution in enumerate(solutions, start=1):
    print("Solution", idx, ":")
    print_board(solution)