teamemancipation

Built-in Functions in Python

Built-in Functions in Python

Built-in Functions (20 Programs) Program 1: abs() – Absolute Value of a Number Program: def absolute_value(num): """Return the absolute value of a number.""" return abs(num) # Test the function print("Absolute value of -10:", absolute_value(-10)) print("Absolute value of 5:", absolute_value(5)) Expected Output: Absolute value of -10: 10 Absolute value of 5: 5 Program 2: all() – Check if All Elements in List are True Program: def check_all_true(values): """Check if all elements in the list are True.""" return all(values) # Test the function print("All elements True:", check_all_true([True, True, True])) print("All elements True:", check_all_true([True, False, True])) Expected Output: All elements True: True All elements True: False Program 3: any() – Check if Any Element in List is True Program: def check_any_true(values): """Check if any element in the list is True.""" return any(values) # Test the function print("Any element True:", check_any_true([False, False, True])) print("Any element True:", check_any_true([False, False, False])) Expected Output: Any element True: True Any element True: False Program 4: ascii() – Return ASCII Representation of a String Program: def get_ascii_representation(text): """Get ASCII representation of a string.""" return ascii(text) # Test the function print("ASCII representation:", get_ascii_representation("Python ©")) Expected Output: ASCII representation: ‘Python \xa9’ Program 5: bin() – Convert Integer to Binary Program: def to_binary(num): """Convert an integer to binary.""" return bin(num) # Test the function print("Binary of 10:", to_binary(10)) print("Binary of 25:", to_binary(25)) Expected Output: Binary of 10: 0b1010 Binary of 25: 0b11001 Program 6: bool() – Convert Value to Boolean Program: def to_boolean(value): """Convert a value to boolean.""" return bool(value) # Test the function print("Boolean of 0:", to_boolean(0)) print("Boolean of ‘Hello’:", to_boolean("Hello")) Expected Output: Boolean of 0: False Boolean of ‘Hello’: True Program 7: chr() – Convert Unicode Code to Character Program: def unicode_to_char(code): """Convert Unicode code to character.""" return chr(code) # Test the function print("Character for 97:", unicode_to_char(97)) print("Character for 65:", unicode_to_char(65)) Expected Output: Character for 97: a Character for 65: A Program 8: divmod() – Quotient and Remainder of Division Program: def quotient_remainder(a, b): """Get quotient and remainder of division.""" return divmod(a, b) # Test the function print("Quotient and remainder of 10 / 3:", quotient_remainder(10, 3)) print("Quotient and remainder of 20 / 6:", quotient_remainder(20, 6)) Expected Output: Quotient and remainder of 10 / 3: (3, 1) Quotient and remainder of 20 / 6: (3, 2) Program 9: enumerate() – Enumerate List Items with Index Program: def enumerate_list(items): """Enumerate items in a list with their index.""" return list(enumerate(items)) # Test the function print("Enumerated list:", enumerate_list(["apple", "banana", "cherry"])) Expected Output: Enumerated list: [(0, ‘apple’), (1, ‘banana’), (2, ‘cherry’)] Program 10: eval() – Evaluate a Python Expression Program: def evaluate_expression(expression): """Evaluate a Python expression.""" return eval(expression) # Test the function print("Evaluation of ‘3 + 5’:", evaluate_expression("3 + 5")) print("Evaluation of ‘2 * 6’:", evaluate_expression("2 * 6")) Expected Output: Evaluation of ‘3 + 5’: 8 Evaluation of ‘2 * 6’: 12 Program 11: filter() – Filter Even Numbers from a List Program: def filter_even(numbers): """Filter even numbers from a list.""" return list(filter(lambda x: x % 2 == 0, numbers)) # Test the function print("Even numbers:", filter_even([1, 2, 3, 4, 5, 6])) Expected Output: Even numbers: [2, 4, 6] Program 12: float() – Convert Value to Float Program: def to_float(value): """Convert a value to float.""" return float(value) # Test the function print("Float of 5:", to_float(5)) print("Float of ‘3.14’:", to_float("3.14")) Expected Output: Float of 5: 5.0 Float of ‘3.14’: 3.14 Program 13: format() – Format Number with 2 Decimal Places Program: def format_number(num): """Format a number to 2 decimal places.""" return format(num, ".2f") # Test the function print("Formatted number:", format_number(3.14159)) print("Formatted number:", format_number(7.88888)) Expected Output: Formatted number: 3.14 Formatted number: 7.89 Program 14: hex() – Convert Integer to Hexadecimal Program: def to_hexadecimal(num): """Convert an integer to hexadecimal.""" return hex(num) # Test the function print("Hexadecimal of 255:", to_hexadecimal(255)) print("Hexadecimal of 16:", to_hexadecimal(16)) Expected Output: Hexadecimal of 255: 0xff Hexadecimal of 16: 0x10 Program 15: input() – Take User Input (for Interactive Testing) Program: def get_user_input(): """Get input from the user.""" user_input = input("Enter a message: ") return f"You entered: {user_input}" # Run in an interactive environment to see output. Output will depend on user input. Program 16: len() – Length of a List Program: def list_length(lst): """Return the length of a list.""" return len(lst) # Test the function print("Length of list:", list_length([1, 2, 3, 4])) Expected Output: Length of list: 4 Program 17: max() – Maximum of Three Numbers Program: def find_maximum(a, b, c): """Find the maximum of three numbers.""" return max(a, b, c) # Test the function print("Maximum of (3, 7, 5):", find_maximum(3, 7, 5)) Expected Output: Maximum of (3, 7, 5): 7 Program 18: min() – Minimum of Three Numbers Program: def find_minimum(a, b, c): """Find the minimum of three numbers.""" return min(a, b, c) # Test the function print("Minimum of (3, 7, 5):", find_minimum(3, 7, 5)) Expected Output: Minimum of (3, 7, 5): 3 Program 19: round() – Round a Number to Specified Digits Program: def round_number(num, digits): """Round a number to specified digits.""" return round(num, digits) # Test the function print("Rounded number:", round_number(3.14159, 2)) Expected Output: Rounded number: 3.14 Program 20: sorted() – Sort a List in Ascending Order Program: def sort_list(lst): """Sort a list in ascending order.""" return sorted(lst) # Test the function print("Sorted list:", sort_list([3, 1, 4, 2])) Expected Output: Sorted list: [1, 2, 3, 4]

Built-in Functions in Python Read More »

Pattern Programs

Pattern Programs

The next topic is Pattern Programs. Pattern programs are a great way to demonstrate the power of loops and how they can be used to create visually interesting outputs. The concept of nested loops is often used in pattern printing, and different types of patterns help reinforce the understanding of loops, conditions, and formatting in Python. Here are 20 different Pattern Programs in Python to explore. Pattern Programs 1. Right-Angled Triangle Pattern of Stars Description: Prints a right-angled triangle of stars. # Program to print a right-angled triangle pattern using stars n = int(input("Enter the number of rows: ")) for i in range(n): for j in range(i + 1): print("*", end="") print() 2. Inverted Right-Angled Triangle Pattern of Stars Description: Prints an inverted right-angled triangle pattern of stars. # Program to print an inverted right-angled triangle pattern using stars n = int(input("Enter the number of rows: ")) for i in range(n, 0, -1): for j in range(i): print("*", end="") print() 3. Pyramid Pattern of Stars Description: Prints a pyramid pattern using stars. # Program to print a pyramid pattern of stars n = int(input("Enter the number of rows: ")) for i in range(1, n + 1): print(" " * (n – i) + "*" * (2 * i – 1)) 4. Diamond Pattern of Stars Description: Prints a diamond shape using stars. # Program to print diamond pattern of stars n = int(input("Enter the number of rows for the upper half: ")) # Upper half of the diamond for i in range(1, n + 1): print(" " * (n – i) + "*" * (2 * i – 1)) # Lower half of the diamond for i in range(n – 1, 0, -1): print(" " * (n – i) + "*" * (2 * i – 1)) 5. Number Pyramid Pattern Description: Prints a number pyramid. # Program to print number pyramid pattern n = int(input("Enter the number of rows: ")) for i in range(1, n + 1): print(" " * (n – i) + " ".join(str(j) for j in range(1, i + 1))) 6. Inverted Number Pyramid Description: Prints an inverted number pyramid. # Program to print an inverted number pyramid pattern n = int(input("Enter the number of rows: ")) for i in range(n, 0, -1): print(" " * (n – i) + " ".join(str(j) for j in range(1, i + 1))) 7. Square Pattern of Numbers Description: Prints a square pattern using numbers. # Program to print a square pattern of numbers n = int(input("Enter the size of the square: ")) for i in range(1, n + 1): for j in range(1, n + 1): print(i, end=" ") print() 8. Hollow Square Pattern Description: Prints a hollow square using stars. # Program to print a hollow square pattern n = int(input("Enter the size of the square: ")) for i in range(n): for j in range(n): if i == 0 or i == n – 1 or j == 0 or j == n – 1: print("*", end="") else: print(" ", end="") print() 9. Floyd’s Triangle Description: Prints Floyd’s Triangle with consecutive numbers. # Program to print Floyd’s Triangle n = int(input("Enter the number of rows: ")) num = 1 for i in range(1, n + 1): for j in range(1, i + 1): print(num, end=" ") num += 1 print() 10. Butterfly Pattern Description: Prints a butterfly pattern using stars. # Program to print butterfly pattern using stars n = int(input("Enter the number of rows: ")) # Upper part of the butterfly for i in range(1, n + 1): print("*" * i + " " * (2 * (n – i)) + "*" * i) # Lower part of the butterfly for i in range(n, 0, -1): print("*" * i + " " * (2 * (n – i)) + "*" * i) 11. Hollow Triangle Pattern Description: Prints a hollow triangle pattern using stars. # Program to print hollow triangle pattern n = int(input("Enter the number of rows: ")) for i in range(1, n + 1): for j in range(1, i + 1): if j == 1 or j == i or i == n: print("*", end="") else: print(" ", end="") print() 12. Zigzag Pattern Description: Prints a zigzag pattern using stars. # Program to print zigzag pattern using stars n = int(input("Enter the number of rows: ")) for i in range(n): for j in range(n): if (i + j) % 2 == 0: print("*", end="") else: print(" ", end="") print() 13. Pascal’s Triangle Description: Prints Pascal’s Triangle. # Program to print Pascal’s Triangle n = int(input("Enter the number of rows: ")) for i in range(n): num = 1 for j in range(i + 1): print(num, end=" ") num = num * (i – j) // (j + 1) print() 14. Right-Angled Triangle of Numbers Description: Prints a right-angled triangle with numbers. # Program to print a right-angled triangle of numbers n = int(input("Enter the number of rows: ")) for i in range(1, n + 1): for j in range(1, i + 1): print(j, end="") print() 15. Right-Angled Triangle of Alphabets Description: Prints a right-angled triangle with alphabets. # Program to print a right-angled triangle of alphabets n = int(input("Enter the number of rows: ")) for i in range(n): for j in range(i + 1): print(chr(65 + j), end="") print() 16. Inverted Triangle of Stars Description: Prints an inverted triangle using stars. # Program to print an inverted triangle of stars n = int(input("Enter the number of rows: ")) for i in range(n, 0, -1): print("*" * i) 17. Hollow Diamond Pattern Description: Prints a hollow diamond shape using stars. # Program to print hollow diamond pattern n = int(input("Enter the number of rows for the upper half: ")) # Upper half of the diamond for i in range(1, n + 1): print(" " * (n – i) + "*" + " " * (2 * i – 3) + "*" * (i > 1)) # Lower half of the diamond for i in range(n –

Pattern Programs Read More »

Prime Number Programs

Prime Number Programs

The next topic is Prime Number Programs, where we focus on writing programs to identify prime numbers and perform tasks related to prime numbers. We’ll start with Prime Factorization, which is finding the prime factors of a number. To meet your specific request, I will also include a program that executes a loop until the square of a prime factor. Prime Number Programs 1. Check If a Number is Prime Description: This program checks if a number is prime or not. # Program to check if a number is prime num = int(input("Enter a number: ")) if num > 1: for i in range(2, int(num / 2) + 1): if num % i == 0: print(f"{num} is not a prime number.") break else: print(f"{num} is a prime number.") else: print(f"{num} is not a prime number.") 2. Find Prime Factors of a Number Description: This program finds the prime factors of a given number. # Program to find prime factors of a number num = int(input("Enter a number: ")) i = 2 print(f"Prime factors of {num} are:") while i * i <= num: if num % i: i += 1 else: num //= i print(i, end=" ") if num > 1: print(num) 3. Loop Till the Square of the Prime Factor Description: This program loops through the prime factors and executes a loop until the square of the prime factor. # Program to loop until the square of the prime factor def prime_factors(n): factors = [] i = 2 while i * i <= n: if n % i == 0: factors.append(i) n //= i else: i += 1 if n > 1: factors.append(n) return factors def loop_until_square_of_prime_factor(n): factors = prime_factors(n) for factor in factors: print(f"\nExecuting loop for prime factor {factor}:") i = 1 # Loop until the square of the prime factor while i <= factor * factor: print(f"i = {i}") i += 1 num = int(input("Enter a number: ")) loop_until_square_of_prime_factor(num) Explanation Prime Factors Program: This program finds the prime factors of a number using a while loop. It divides the number by possible factors until we reach a prime number. Loop Until Square of Prime Factor: In this program, we first find the prime factors of the input number, and for each prime factor, we execute a loop that runs until the square of that prime factor. This fulfills your specific requirement. Let me know if you’d like to explore more prime number programs or move on to the next topic!

Prime Number Programs Read More »

Strings Program

Strings Program

The next topic is Strings in Python. Strings are one of the most commonly used data types in Python and are essential for handling textual data. In this section, we will explore various operations and methods that can be performed on strings in Python, including concatenation, slicing, formatting, and more. String Programs 1. Check If a String is a Palindrome Description: This program checks if a given string is a palindrome (reads the same backward as forward). # Program to check if a string is a palindrome string = input("Enter a string: ") if string == string[::-1]: print(f"'{string}’ is a palindrome.") else: print(f"'{string}’ is not a palindrome.") 2. Count Vowels in a String Description: This program counts the number of vowels in a given string. # Program to count vowels in a string string = input("Enter a string: ") vowels = "aeiouAEIOU" count = 0 for char in string: if char in vowels: count += 1 print(f"The number of vowels in ‘{string}’ is {count}.") 3. Reverse a String Description: This program reverses a given string. # Program to reverse a string string = input("Enter a string: ") reversed_string = string[::-1] print(f"The reversed string is: ‘{reversed_string}’") 4. Count the Frequency of Each Character in a String Description: This program counts how many times each character appears in a string. # Program to count the frequency of each character in a string string = input("Enter a string: ") frequency = {} for char in string: if char in frequency: frequency[char] += 1 else: frequency[char] = 1 print(f"Character frequency in ‘{string}’: {frequency}") 5. Convert All Characters to Uppercase Description: This program converts all characters in a string to uppercase. # Program to convert a string to uppercase string = input("Enter a string: ") uppercase_string = string.upper() print(f"The string in uppercase is: ‘{uppercase_string}’") 6. Convert All Characters to Lowercase Description: This program converts all characters in a string to lowercase. # Program to convert a string to lowercase string = input("Enter a string: ") lowercase_string = string.lower() print(f"The string in lowercase is: ‘{lowercase_string}’") 7. Find the Length of a String Description: This program finds the length of a string. # Program to find the length of a string string = input("Enter a string: ") length = len(string) print(f"The length of the string ‘{string}’ is {length}.") 8. Check if a Substring Exists in a String Description: This program checks if a given substring is present in a string. # Program to check if a substring exists in a string string = input("Enter a string: ") substring = input("Enter the substring to check: ") if substring in string: print(f"'{substring}’ exists in ‘{string}’.") else: print(f"'{substring}’ does not exist in ‘{string}’.") 9. Remove Whitespaces from a String Description: This program removes leading and trailing whitespaces from a string. # Program to remove whitespaces from a string string = input("Enter a string with spaces: ") trimmed_string = string.strip() print(f"The string without leading and trailing spaces is: ‘{trimmed_string}’") 10. Find the Position of a Substring Description: This program finds the position of the first occurrence of a substring. # Program to find the position of a substring string = input("Enter a string: ") substring = input("Enter the substring: ") position = string.find(substring) if position != -1: print(f"The substring ‘{substring}’ is found at position {position}.") else: print(f"The substring ‘{substring}’ is not found.") 11. Replace All Occurrences of a Substring in a String Description: This program replaces all occurrences of a substring with another string. # Program to replace all occurrences of a substring in a string string = input("Enter a string: ") old_substring = input("Enter the substring to replace: ") new_substring = input("Enter the new substring: ") new_string = string.replace(old_substring, new_substring) print(f"The new string is: ‘{new_string}’") 12. Check If a String Starts with a Specific Substring Description: This program checks if a string starts with a specific substring. # Program to check if a string starts with a specific substring string = input("Enter a string: ") substring = input("Enter the substring: ") if string.startswith(substring): print(f"'{string}’ starts with ‘{substring}’.") else: print(f"'{string}’ does not start with ‘{substring}’.") 13. Check If a String Ends with a Specific Substring Description: This program checks if a string ends with a specific substring. # Program to check if a string ends with a specific substring string = input("Enter a string: ") substring = input("Enter the substring: ") if string.endswith(substring): print(f"'{string}’ ends with ‘{substring}’.") else: print(f"'{string}’ does not end with ‘{substring}’.") 14. Find All Occurrences of a Substring Description: This program finds all occurrences of a substring in a string. # Program to find all occurrences of a substring in a string string = input("Enter a string: ") substring = input("Enter the substring: ") start = 0 while start < len(string): start = string.find(substring, start) if start == -1: break print(f"Found ‘{substring}’ at position {start}") start += 1 15. Join Elements of a List into a String Description: This program joins a list of strings into a single string. # Program to join elements of a list into a string list_of_strings = ["Python", "is", "great"] joined_string = " ".join(list_of_strings) print(f"The joined string is: ‘{joined_string}’") 16. Split a String into a List Description: This program splits a string into a list of words. # Program to split a string into a list string = input("Enter a string: ") split_list = string.split() print(f"The list of words is: {split_list}") 17. Check If All Characters in a String Are Digits Description: This program checks if all characters in a string are digits. # Program to check if all characters in a string are digits string = input("Enter a string: ") if string.isdigit(): print(f"'{string}’ contains only digits.") else: print(f"'{string}’ does not contain only digits.") 18. Convert a String to a List of Characters Description: This program converts a string into a list of characters. # Program to convert a string to a list of characters string = input("Enter a string: ") char_list = list(string) print(f"The list of characters is: {char_list}") 19. Find the Most Frequent Character in a String Description: This program

Strings Program Read More »

Type Casting Programs (5 Programs)

Type Casting Programs (5 Programs)

Type Casting Programs (5 Programs) Program 1: Convert String to Integer and Perform Arithmetic Operations Program: # Define a string representing an integer num_str = "25" # Convert the string to an integer num_int = int(num_str) # Perform arithmetic operations sum_value = num_int + 10 product = num_int * 3 print("Original String:", num_str) print("Converted to Integer:", num_int) print("Sum with 10:", sum_value) print("Product with 3:", product) Expected Output: Original String: 25 Converted to Integer: 25 Sum with 10: 35 Product with 3: 75 Program 2: Convert Integer to Float and Perform Division Program: # Define an integer integer_value = 15 # Convert integer to float float_value = float(integer_value) # Perform division with another float result = float_value / 4.0 print("Integer:", integer_value) print("Converted to Float:", float_value) print("Division Result (Float):", result) Expected Output: Integer: 15 Converted to Float: 15.0 Division Result (Float): 3.75 Program 3: Convert Float to String and Concatenate Program: # Define a float value float_val = 3.14159 # Convert float to string str_val = str(float_val) # Concatenate with another string concatenated = "Pi is approximately " + str_val print("Float Value:", float_val) print("Converted to String:", str_val) print("Concatenated String:", concatenated) Expected Output: Float Value: 3.14159 Converted to String: 3.14159 Concatenated String: Pi is approximately 3.14159 Program 4: Convert List to Set to Remove Duplicates Program: # Define a list with duplicate elements num_list = [1, 2, 2, 3, 4, 4, 5] # Convert list to set to remove duplicates num_set = set(num_list) print("Original List:", num_list) print("Converted to Set (Unique Values):", num_set) Expected Output: Original List: [1, 2, 2, 3, 4, 4, 5] Converted to Set (Unique Values): {1, 2, 3, 4, 5} Program 5: Convert Dictionary Keys and Values to Lists Program: # Define a dictionary with some key-value pairs student_grades = {"Alice": 88, "Bob": 92, "Charlie": 85} # Convert dictionary keys and values to separate lists keys_list = list(student_grades.keys()) values_list = list(student_grades.values()) print("Dictionary:", student_grades) print("Keys as List:", keys_list) print("Values as List:", values_list) Expected Output: Dictionary: {‘Alice’: 88, ‘Bob’: 92, ‘Charlie’: 85} Keys as List: [‘Alice’, ‘Bob’, ‘Charlie’] Values as List: [88, 92, 85]

Type Casting Programs (5 Programs) Read More »

User-Defined Functions (With Parameters)

User-Defined Functions (With Parameters)

User-Defined Functions (With Parameters) – Programs 1–10 Program 1: Calculate the Area of a Rectangle Program: def calculate_area(length, width): """Calculate and return the area of a rectangle given length and width.""" area = length * width return area # Test the function print("Area of Rectangle:", calculate_area(5, 10)) Expected Output: Area of Rectangle: 50 Program 2: Find the Square of a Number Program: def square(number): """Return the square of a number.""" return number ** 2 # Test the function print("Square of 7:", square(7)) Expected Output: Square of 7: 49 Program 3: Convert Celsius to Fahrenheit Program: def celsius_to_fahrenheit(celsius): """Convert Celsius to Fahrenheit.""" fahrenheit = (celsius * 9/5) + 32 return fahrenheit # Test the function print("Temperature in Fahrenheit:", celsius_to_fahrenheit(25)) Expected Output: Temperature in Fahrenheit: 77.0 Program 4: Check if a Number is Even or Odd Program: def is_even(number): """Check if a number is even or odd.""" return "Even" if number % 2 == 0 else "Odd" # Test the function print("Number 15 is:", is_even(15)) Expected Output: Number 15 is: Odd Program 5: Calculate Simple Interest Program: def simple_interest(principal, rate, time): """Calculate simple interest.""" interest = (principal * rate * time) / 100 return interest # Test the function print("Simple Interest:", simple_interest(1000, 5, 2)) Expected Output: Simple Interest: 100.0 Program 6: Calculate Factorial of a Number Program: def factorial(n): """Calculate the factorial of a number.""" result = 1 for i in range(1, n + 1): result *= i return result # Test the function print("Factorial of 5:", factorial(5)) Expected Output: Factorial of 5: 120 Program 7: Find Maximum of Three Numbers Program: def max_of_three(a, b, c): """Return the maximum of three numbers.""" return max(a, b, c) # Test the function print("Maximum of (3, 7, 5):", max_of_three(3, 7, 5)) Expected Output: Maximum of (3, 7, 5): 7 Program 8: Count Vowels in a String Program: def count_vowels(s): """Count the number of vowels in a string.""" vowels = "aeiouAEIOU" count = sum(1 for char in s if char in vowels) return count # Test the function print("Number of Vowels:", count_vowels("Hello World")) Expected Output: Number of Vowels: 3 Program 9: Calculate the Power of a Number Program: def power(base, exponent): """Calculate the power of a number.""" return base ** exponent # Test the function print("2 raised to the power 3:", power(2, 3)) Expected Output: 2 raised to the power 3: 8 Program 10: Convert Kilometers to Miles Program: def km_to_miles(km): """Convert kilometers to miles.""" miles = km * 0.621371 return miles # Test the function print("5 km in miles:", km_to_miles(5)) Expected Output: 5 km in miles: 3.106855 User-Defined Functions (With Parameters) – Programs 11–20 Program 11: Calculate Compound Interest Program: def compound_interest(principal, rate, time): """Calculate compound interest.""" amount = principal * (1 + rate / 100) ** time interest = amount – principal return interest # Test the function print("Compound Interest:", compound_interest(1000, 5, 2)) Expected Output: Compound Interest: 102.5 Program 12: Check if a Number is Prime Program: def is_prime(n): """Check if a number is prime.""" if n < 2: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True # Test the function print("Is 7 prime?", is_prime(7)) Expected Output: Is 7 prime? True Program 13: Calculate the Length of a String Program: def string_length(s): """Calculate the length of a string.""" return len(s) # Test the function print("Length of ‘Python’:", string_length("Python")) Expected Output: Length of ‘Python’: 6 Program 14: Find the Minimum Value in a List Program: def find_minimum(numbers): """Find the minimum value in a list of numbers.""" return min(numbers) # Test the function print("Minimum in [5, 3, 9, 1]:", find_minimum([5, 3, 9, 1])) Expected Output: Minimum in [5, 3, 9, 1]: 1 Program 15: Calculate the Area of a Circle Program: def area_of_circle(radius): """Calculate the area of a circle given the radius.""" pi = 3.14159 return pi * radius ** 2 # Test the function print("Area of Circle with radius 3:", area_of_circle(3)) Expected Output: Area of Circle with radius 3: 28.27431 Program 16: Reverse a List Program: def reverse_list(lst): """Reverse the elements of a list.""" return lst[::-1] # Test the function print("Reversed list [1, 2, 3, 4]:", reverse_list([1, 2, 3, 4])) Expected Output: Reversed list [1, 2, 3, 4]: [4, 3, 2, 1] Program 17: Find the GCD of Two Numbers Program: def gcd(a, b): """Find the greatest common divisor (GCD) of two numbers.""" while b: a, b = b, a % b return a # Test the function print("GCD of 48 and 18:", gcd(48, 18)) Expected Output: GCD of 48 and 18: 6 Program 18: Count Words in a Sentence Program: def count_words(sentence): """Count the number of words in a sentence.""" words = sentence.split() return len(words) # Test the function print("Number of words in ‘Hello world program’:", count_words("Hello world program")) Expected Output: Number of words in ‘Hello world program’: 3 Program 19: Check if a Year is a Leap Year Program: def is_leap_year(year): """Check if a year is a leap year.""" return year % 4 == 0 and (year % 100 != 0 or year % 400 == 0) # Test the function print("Is 2024 a leap year?", is_leap_year(2024)) Expected Output: Is 2024 a leap year? True Program 20: Concatenate Two Strings Program: def concatenate_strings(s1, s2): """Concatenate two strings.""" return s1 + s2 # Test the function print("Concatenated String:", concatenate_strings("Hello, ", "World!")) Expected Output: Concatenated String: Hello, World!

User-Defined Functions (With Parameters) Read More »

Types of Functions Based on Arguments

Types of Functions Based on Arguments

Program 1: Simple Addition of Two Numbers Program: def add(a, b): """Add two numbers using positional arguments.""" return a + b # Test the function print("Sum of 5 and 7:", add(5, 7)) Expected Output: Sum of 5 and 7: 12 Program 2: Calculate the Difference Between Two Numbers Program: def subtract(a, b): """Subtract the second number from the first using positional arguments.""" return a – b # Test the function print("Difference between 10 and 3:", subtract(10, 3)) Expected Output: Difference between 10 and 3: 7 Program 3: Multiply Two Numbers Program: def multiply(a, b): """Multiply two numbers using positional arguments.""" return a * b # Test the function print("Product of 4 and 6:", multiply(4, 6)) Expected Output: Product of 4 and 6: 24 Program 4: Divide Two Numbers Program: def divide(a, b): """Divide the first number by the second using positional arguments.""" if b != 0: return a / b else: return "Error: Division by zero" # Test the function print("Division of 20 by 4:", divide(20, 4)) Expected Output: Division of 20 by 4: 5.0 Program 5: Calculate Power of a Number Program: def power(base, exponent): """Calculate the power of a number using positional arguments.""" return base ** exponent # Test the function print("2 raised to the power of 3:", power(2, 3)) Expected Output: 2 raised to the power of 3: 8 Program 6: Swap Two Numbers Program: def swap(a, b): """Swap two numbers using positional arguments.""" return b, a # Test the function x, y = swap(10, 20) print("After swapping: x =", x, ", y =", y) Expected Output: After swapping: x = 20 , y = 10 Program 7: Calculate Average of Two Numbers Program: def average(a, b): """Calculate the average of two numbers using positional arguments.""" return (a + b) / 2 # Test the function print("Average of 5 and 9:", average(5, 9)) Expected Output: Average of 5 and 9: 7.0 Program 8: Check if Two Numbers Are Equal Program: def are_equal(a, b): """Check if two numbers are equal using positional arguments.""" return a == b # Test the function print("Are 10 and 10 equal?", are_equal(10, 10)) Expected Output: Are 10 and 10 equal? True Program 9: Find Maximum of Two Numbers Program: def maximum(a, b): """Return the maximum of two numbers using positional arguments.""" return max(a, b) # Test the function print("Maximum of 15 and 20:", maximum(15, 20)) Expected Output: Maximum of 15 and 20: 20 Program 10: Find Minimum of Two Numbers Program: def minimum(a, b): """Return the minimum of two numbers using positional arguments.""" return min(a, b) # Test the function print("Minimum of 30 and 25:", minimum(30, 25)) Expected Output: Minimum of 30 and 25: 25 Default Arguments (10 Programs) Program 1: Greet with Default Name Program: def greet(name="User"): """Greet a person, with a default name if none is provided.""" return f"Hello, {name}!" # Test the function print(greet()) # Using default argument print(greet("Alice")) # Using custom argument Expected Output: Hello, User! Hello, Alice! Program 2: Calculate the Price After Discount (with Default Discount) Program: def calculate_price(original_price, discount=10): """Calculate price after applying a discount. Default discount is 10%.""" discounted_price = original_price * (1 – discount / 100) return discounted_price # Test the function print("Price after discount (default 10%):", calculate_price(100)) print("Price after discount (20%):", calculate_price(100, 20)) Expected Output: Price after discount (default 10%): 90.0 Price after discount (20%): 80.0 Program 3: Get Discounted Price with Default Tax Program: def calculate_total_price(price, discount=5, tax=8): """Calculate total price after discount and tax (default tax is 8%).""" discounted_price = price – (price * discount / 100) total_price = discounted_price + (discounted_price * tax / 100) return total_price # Test the function print("Total price with default discount and tax:", calculate_total_price(200)) print("Total price with custom discount and tax:", calculate_total_price(200, 10, 12)) Expected Output: Total price with default discount and tax: 199.04 Total price with custom discount and tax: 198.0 Program 4: Calculate Rectangle Area with Default Width Program: def calculate_area(length, width=5): """Calculate area of a rectangle, with default width 5.""" return length * width # Test the function print("Area with default width:", calculate_area(10)) print("Area with custom width:", calculate_area(10, 8)) Expected Output: Area with default width: 50 Area with custom width: 80 Program 5: Display Full Name (with Default Middle Name) Program: def display_name(first_name, last_name, middle_name=""): """Display full name, with an optional middle name.""" if middle_name: return f"{first_name} {middle_name} {last_name}" else: return f"{first_name} {last_name}" # Test the function print(display_name("John", "Doe")) # Without middle name print(display_name("John", "Doe", "Michael")) # With middle name Expected Output: John Doe John Michael Doe Program 6: Find the Total Price (with Default Tax) Program: def find_total_price(price, tax_rate=5): """Find total price including tax. Default tax rate is 5%.""" total_price = price + (price * tax_rate / 100) return total_price # Test the function print("Total price (default 5% tax):", find_total_price(200)) print("Total price (10% tax):", find_total_price(200, 10)) Expected Output: Total price (default 5% tax): 210.0 Total price (10% tax): 220.0 Program 7: Calculate Circle Circumference (with Default Pi) Program: def calculate_circumference(radius, pi=3.14159): """Calculate the circumference of a circle, with default value of pi.""" return 2 * pi * radius # Test the function print("Circumference (default pi):", calculate_circumference(7)) print("Circumference (custom pi):", calculate_circumference(7, 3.14)) Expected Output: Circumference (default pi): 43.98226 Circumference (custom pi): 43.96 Program 8: Calculate Compound Interest (with Default Rate) Program: def compound_interest(principal, rate=5, time=1): """Calculate compound interest with default rate 5% and time 1 year.""" amount = principal * (1 + rate / 100) ** time return amount – principal # Test the function print("Compound interest (default rate and time):", compound_interest(1000)) print("Compound interest (custom rate and time):", compound_interest(1000, 7, 2)) Expected Output: Compound interest (default rate and time): 50.0 Compound interest (custom rate and time): 140.0 Program 9: Get Greeting Message (with Default Language) Program: def greet(language="English"): """Return a greeting message in the specified language.""" greetings = { "English": "Hello!", "Spanish": "¡Hola!", "French": "Bonjour!", "German": "Hallo!" } return greetings.get(language, "Hello!") # Test the function print(greet()) # Default English print(greet("Spanish")) # Custom Spanish Expected Output: Hello! ¡Hola! Program 10: Calculate Perimeter of a Square (with Default Side Length) Program: def calculate_perimeter(side_length=4):

Types of Functions Based on Arguments Read More »

Chapter 23 - Advanced Data Structures

Chapter 23 – Advanced Data Structures

Chapter 23: Advanced Data Structures Advanced data structures are crucial for solving complex computational problems efficiently. They allow us to manage data in a way that reduces the time complexity of operations such as searching, updating, and querying large datasets. In this chapter, we will focus on three key advanced data structures: Hash Tables Tries Segment Trees and Fenwick Trees Each of these structures is designed to address different computational challenges and is widely used in competitive programming and real-world applications. Let’s explore these structures in detail. 23.1 Hash Tables A Hash Table is a data structure that provides an efficient way to store and retrieve data. It uses a hash function to map keys to values, enabling constant time average complexity for operations such as insertion, deletion, and search. 23.1.1 The Structure of Hash Tables A hash table consists of an array, where each position corresponds to an index produced by a hash function. The hash function converts a key (usually a string or an integer) into an index that maps to the array position where the associated value is stored. Hash Function: A function that converts a key into an index. Collisions: When two different keys produce the same index, a collision occurs. Hash tables handle collisions using two primary methods: Chaining: Multiple key-value pairs are stored in a list at the same index. Open Addressing: The hash table searches for the next available index. 23.1.2 Operations in Hash Tables Insert(key, value): Insert a key-value pair into the hash table. Search(key): Retrieve the value associated with the key. Delete(key): Remove the key-value pair from the hash table. Example Implementation of a Hash Table Here’s a simple implementation of a hash table using chaining in C. #include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 10 struct Node { int key; int value; struct Node* next; }; struct Node* hashTable[TABLE_SIZE]; int hashFunction(int key) { return key % TABLE_SIZE; } void insert(int key, int value) { int hashIndex = hashFunction(key); struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); newNode->key = key; newNode->value = value; newNode->next = hashTable[hashIndex]; hashTable[hashIndex] = newNode; } int search(int key) { int hashIndex = hashFunction(key); struct Node* node = hashTable[hashIndex]; while (node != NULL) { if (node->key == key) { return node->value; } node = node->next; } return -1; } void delete(int key) { int hashIndex = hashFunction(key); struct Node* node = hashTable[hashIndex]; struct Node* prev = NULL; while (node != NULL && node->key != key) { prev = node; node = node->next; } if (node == NULL) return; if (prev == NULL) { hashTable[hashIndex] = node->next; } else { prev->next = node->next; } free(node); } 23.2 Tries (Prefix Trees) A Trie (pronounced “try”) is a tree-like data structure that is used for storing strings efficiently. It is especially useful for scenarios where we need to quickly search for strings or prefixes of strings, such as in dictionary implementations and autocomplete systems. 23.2.1 Structure of a Trie A Trie stores strings character by character. Each node in the Trie represents a character, and a path from the root to a node represents a string or a prefix. The Trie allows us to check whether a string exists, whether a prefix exists, and retrieve all strings that start with a given prefix. Each node of a Trie has: Children: References to its child nodes, representing the next characters. End of Word Marker: A boolean value indicating if the node represents the end of a word. 23.2.2 Trie Operations Insert(word): Inserts a word into the Trie. Search(word): Checks if the word is present in the Trie. Prefix Search(prefix): Checks if there is any word in the Trie that starts with the given prefix. Example Implementation of a Trie #include <stdio.h> #include <stdlib.h> #include <string.h> #define ALPHABET_SIZE 26 struct TrieNode { struct TrieNode* children[ALPHABET_SIZE]; int isEndOfWord; }; struct TrieNode* getNode() { struct TrieNode* node = (struct TrieNode*) malloc(sizeof(struct TrieNode)); node->isEndOfWord = 0; for (int i = 0; i < ALPHABET_SIZE; i++) { node->children[i] = NULL; } return node; } void insert(struct TrieNode* root, const char* key) { struct TrieNode* current = root; for (int i = 0; i < strlen(key); i++) { int index = key[i] – ‘a’; if (!current->children[index]) { current->children[index] = getNode(); } current = current->children[index]; } current->isEndOfWord = 1; } int search(struct TrieNode* root, const char* key) { struct TrieNode* current = root; for (int i = 0; i < strlen(key); i++) { int index = key[i] – ‘a’; if (!current->children[index]) { return 0; } current = current->children[index]; } return current->isEndOfWord; } 23.3 Segment Trees and Fenwick Trees 23.3.1 Segment Trees A Segment Tree is a data structure used for efficiently performing range queries and updates on an array. For example, if we want to calculate the sum, minimum, or maximum of elements in a range of an array and frequently update the array values, a segment tree provides a more efficient solution compared to a simple array. A segment tree divides the array into segments, and each node in the tree stores information about a specific range. It allows range queries and point updates in O(log n) time. Operations on Segment Tree Build Tree: Construct the segment tree from an array. Range Query: Query a range for sum, minimum, maximum, etc. Update: Update an element in the array and reflect the changes in the segment tree. Example Implementation of a Segment Tree #include <stdio.h> int segmentTree[1000]; void buildTree(int arr[], int start, int end, int node) { if (start == end) { segmentTree[node] = arr[start]; } else { int mid = (start + end) / 2; buildTree(arr, start, mid, 2 * node + 1); buildTree(arr, mid + 1, end, 2 * node + 2); segmentTree[node] = segmentTree[2 * node + 1] + segmentTree[2 * node + 2]; } } int rangeQuery(int start, int end, int l, int r, int node) { if (l > end || r < start) { return 0; } if (l <= start && r >= end) { return segmentTree[node]; } int

Chapter 23 – Advanced Data Structures Read More »

Chapter 22 - Advanced Graph Algorithms

Chapter 22 – Advanced Graph Algorithms

Chapter 22: Advanced Graph Algorithms In this chapter, we delve deeper into Advanced Graph Algorithms that are essential for solving complex problems related to graph traversal, connectivity, and more. These algorithms are foundational in many computer science applications, from navigating networks to solving puzzles and finding connected components. We will explore the following topics: Depth-First Search (DFS) Breadth-First Search (BFS) Topological Sorting Strongly Connected Components (Kosaraju’s Algorithm) 22.1 Depth-First Search (DFS) Depth-First Search (DFS) is a fundamental algorithm used to explore all the vertices and edges of a graph. DFS explores as far as possible along each branch before backtracking, which makes it useful for tasks like detecting cycles or solving maze-like problems. Problem Definition: Given a graph, perform DFS traversal from a starting vertex, visiting each vertex once. DFS Algorithm Steps: Start at a given vertex and mark it as visited. For each unvisited neighbor, recursively perform DFS. If all neighbors are visited, backtrack to the previous vertex. DFS Algorithm (in C): #include <stdio.h> #include <stdbool.h> #define V 5 void DFSUtil(int graph[V][V], int v, bool visited[]) { visited[v] = true; printf("%d ", v); for (int i = 0; i < V; i++) { if (graph[v][i] == 1 && !visited[i]) { DFSUtil(graph, i, visited); } } } void DFS(int graph[V][V], int startVertex) { bool visited[V] = {false}; DFSUtil(graph, startVertex, visited); } int main() { int graph[V][V] = { {0, 1, 0, 0, 1}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 1, 0} }; printf("DFS starting from vertex 0:\n"); DFS(graph, 0); return 0; } Explanation: The graph is represented as an adjacency matrix. The DFSUtil() function recursively visits each vertex and its adjacent vertices. visited[] keeps track of the vertices that have already been explored to avoid revisiting. Time Complexity: The time complexity of DFS is O(V²) for an adjacency matrix representation and O(V + E) for an adjacency list, where V is the number of vertices and E is the number of edges. 22.2 Breadth-First Search (BFS) Breadth-First Search (BFS) is another fundamental graph traversal algorithm that explores the vertices level by level. BFS is often used to find the shortest path in unweighted graphs and in applications such as solving puzzles or network broadcasting. BFS Algorithm Steps: Start from a given vertex and mark it as visited. Visit all the adjacent vertices of the current vertex. Repeat for each vertex, visiting the vertices in a breadth-first manner. BFS Algorithm (in C): #include <stdio.h> #include <stdbool.h> #define V 5 void BFS(int graph[V][V], int startVertex) { bool visited[V] = {false}; int queue[V], front = 0, rear = 0; visited[startVertex] = true; queue[rear++] = startVertex; while (front != rear) { int currentVertex = queue[front++]; printf("%d ", currentVertex); for (int i = 0; i < V; i++) { if (graph[currentVertex][i] == 1 && !visited[i]) { visited[i] = true; queue[rear++] = i; } } } } int main() { int graph[V][V] = { {0, 1, 0, 0, 1}, {1, 0, 1, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 1, 0} }; printf("BFS starting from vertex 0:\n"); BFS(graph, 0); return 0; } Explanation: The graph is represented as an adjacency matrix. The queue[] is used to maintain the vertices that need to be explored. The visited[] array keeps track of the visited vertices. Time Complexity: The time complexity of BFS is O(V²) for an adjacency matrix representation and O(V + E) for an adjacency list. 22.3 Topological Sorting Topological Sorting is an ordering of vertices in a Directed Acyclic Graph (DAG) where, for every directed edge (u, v), vertex u comes before vertex v. It is widely used in scheduling problems where some tasks must precede others. Topological Sort Algorithm (DFS-based): Perform DFS on the graph. Push the vertices onto a stack when DFS finishes visiting all vertices from that vertex. Pop all vertices from the stack to get the topological order. Topological Sort Algorithm (in C): #include <stdio.h> #include <stdbool.h> #define V 6 void topologicalSortUtil(int graph[V][V], int v, bool visited[], int stack[], int *index) { visited[v] = true; for (int i = 0; i < V; i++) { if (graph[v][i] == 1 && !visited[i]) { topologicalSortUtil(graph, i, visited, stack, index); } } stack[(*index)–] = v; } void topologicalSort(int graph[V][V]) { bool visited[V] = {false}; int stack[V], index = V – 1; for (int i = 0; i < V; i++) { if (!visited[i]) { topologicalSortUtil(graph, i, visited, stack, &index); } } printf("Topological Sort:\n"); for (int i = 0; i < V; i++) { printf("%d ", stack[i]); } printf("\n"); } int main() { int graph[V][V] = { {0, 1, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0} }; topologicalSort(graph); return 0; } Explanation: The graph is represented as an adjacency matrix. The vertices are stored in the stack in a topologically sorted order. The algorithm makes use of DFS to ensure that all dependencies are visited before the vertex itself. Time Complexity: The time complexity of Topological Sort is O(V²) for an adjacency matrix and O(V + E) for an adjacency list. 22.4 Strongly Connected Components (Kosaraju’s Algorithm) In directed graphs, a Strongly Connected Component (SCC) is a maximal subgraph where every vertex is reachable from every other vertex in the subgraph. Kosaraju’s Algorithm is an efficient method to find SCCs in a directed graph. Kosaraju’s Algorithm Steps: Perform DFS on the original graph and push the vertices onto a stack based on their finish times. Reverse the graph. Perform DFS again, using the vertices in the order defined by the stack. Kosaraju’s Algorithm (in C): #include <stdio.h> #include <stdbool.h> #define V 5 void DFSUtil(int graph[V][V], int v, bool visited[]) { visited[v] = true; printf("%d ", v); for (int i = 0; i < V; i++) { if (graph[v][i] == 1 && !visited[i]) { DFSUtil(graph, i, visited); } }

Chapter 22 – Advanced Graph Algorithms Read More »

Chapter 21 - Graph Algorithms

Chapter 21 – Graph Algorithms

Chapter 21: Graph Algorithms Welcome back! In this chapter, we’ll explore Graph Algorithms, which are crucial in solving problems related to networks, connections, and paths. These algorithms help us navigate through graphs and solve problems like finding the shortest path, traversing graphs, and much more. We’ll focus on two widely-used algorithms for solving problems involving graphs: Shortest Path Algorithms Minimum Spanning Tree (MST) Algorithms Let’s dive right in! 21.1 Shortest Path Algorithms In many real-world applications like GPS navigation, computer networks, and transportation systems, we are often asked to find the shortest path from one point to another in a graph. 21.1.1 Dijkstra’s Algorithm Dijkstra’s Algorithm is used to find the shortest path from a source node to all other nodes in a graph with non-negative edge weights. Problem Definition: Given a graph and a source node, find the shortest path from the source to all other nodes. Algorithm Steps: Create a set of all nodes in the graph. Assign a tentative distance value to every node: 0 for the source node and infinity for all other nodes. While there are unvisited nodes: Pick the unvisited node with the smallest tentative distance. Update the tentative distances of its neighboring nodes. Mark the node as visited. Dijkstra’s Algorithm (in C): #include <stdio.h> #include <limits.h> #include <stdbool.h> #define V 9 int minDistance(int dist[], bool sptSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } void printSolution(int dist[]) { printf("Vertex \t Distance from Source\n"); for (int i = 0; i < V; i++) printf("%d \t %d\n", i, dist[i]); } void dijkstra(int graph[V][V], int src) { int dist[V]; bool sptSet[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; dist[src] = 0; for (int count = 0; count < V – 1; count++) { int u = minDistance(dist, sptSet); sptSet[u] = true; for (int v = 0; v < V; v++) if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } printSolution(dist); } int main() { int graph[V][V] = { {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} }; dijkstra(graph, 0); return 0; } Explanation: The graph is represented by an adjacency matrix where graph[i][j] represents the weight of the edge between vertices i and j. If there is no edge, the value is 0. We maintain an array dist[] where dist[i] holds the shortest distance from the source to vertex i. sptSet[] keeps track of vertices for which we have finalized the shortest distance. Time Complexity: The time complexity of this implementation is O(V²), where V is the number of vertices. 21.2 Minimum Spanning Tree (MST) Algorithms Next up, we’ll look at Minimum Spanning Trees (MST). This is a fundamental problem in network design. Problem Definition: Given a connected, undirected graph, a Minimum Spanning Tree is a subset of the edges that connects all the vertices together without any cycles and with the minimum possible total edge weight. Two well-known algorithms to find MSTs: Prim’s Algorithm Kruskal’s Algorithm 21.2.1 Prim’s Algorithm Prim’s Algorithm finds a minimum spanning tree by starting from a single vertex and growing the tree one edge at a time, always choosing the smallest edge that connects a new vertex to the tree. Algorithm Steps: Initialize the minimum spanning tree (MST) with a single vertex. Repeatedly add the smallest edge that connects a vertex inside the MST to one outside it. Stop when all vertices are in the MST. Prim’s Algorithm (in C): #include <stdio.h> #include <limits.h> #include <stdbool.h> #define V 5 int minKey(int key[], bool mstSet[]) { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (mstSet[v] == false && key[v] < min) min = key[v], min_index = v; return min_index; } void printMST(int parent[], int graph[V][V]) { printf("Edge \tWeight\n"); for (int i = 1; i < V; i++) printf("%d – %d \t%d \n", parent[i], i, graph[i][parent[i]]); } void primMST(int graph[V][V]) { int parent[V]; int key[V]; bool mstSet[V]; for (int i = 0; i < V; i++) key[i] = INT_MAX, mstSet[i] = false; key[0] = 0; parent[0] = -1; for (int count = 0; count < V – 1; count++) { int u = minKey(key, mstSet); mstSet[u] = true; for (int v = 0; v < V; v++) if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) parent[v] = u, key[v] = graph[u][v]; } printMST(parent, graph); } int main() { int graph[V][V] = { {0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0} }; primMST(graph); return 0; } Explanation: We represent the graph using an adjacency matrix. graph[i][j] contains the weight of the edge between vertex i and j. key[] keeps track of the minimum edge weights that connect vertices to the MST. parent[] stores the constructed MST. Time Complexity: The time complexity of Prim’s algorithm is O(V²). 21.2.2 Kruskal’s Algorithm Kruskal’s Algorithm works by sorting all the edges of the graph in non-decreasing order of their weight. It then repeatedly adds the smallest edge to the MST unless doing so would form a cycle. Algorithm Steps: Sort all edges in non-decreasing order of their weight. Pick the smallest edge. If it doesn’t form a cycle, add it to the MST. Repeat until there are exactly V-1 edges in the MST. Kruskal’s Algorithm (in C): #include <stdio.h> #include <stdlib.h> #define V 4 #define

Chapter 21 – Graph Algorithms Read More »

Scroll to Top
Contact Form Demo