cl1p.net - The internet clipboard

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

cl1p.net/server/index.jsp

This cl1p will be deleted in in 12 days.

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)