Programming, Data Structures And Algorithms Using Python - Week 2 Programming Assignment | NPTEL | Jan 2023

Programming, Data Structures And Algorithms Using Python - Week 2 Programming Assignment | NPTEL Jan 2023 | Answer with Explanation

Q.1:
A positive integer m can be partitioned as primes if it can be written as p + q where p > 0, q > 0 and both p and q are prime numbers.
Write a Python function primepartition(m) that takes an integer m as input and returns True if m can be partitioned as primes and False otherwise. (If m is not positive, your function should return False.)

Here are some examples of how your function should work.

>>> primepartition(7)
True

>>> primepartition(185)
False

>>> primepartition(3432)
True

Answer

 def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def primepartition(m):
    if m  <= 1:
        return False
    for i in range(2, m):
        if is_prime(i) and is_prime(m - i):
            return True
    return False

Explanation for is_prime(n):
The code defines a function is_prime that takes an integer n as an input and returns a Boolean value indicating whether n is a prime number or not.

The function first checks if n is less than or equal to 1. If it is, it returns False since 1 is not a prime number.

Next, it uses a for loop to check if n is divisible by any integer in the range 2 to int(n ** 0.5) + 1. The range is chosen to improve the performance of the code since any integer larger than the square root of n can never divide n.

If the loop finds a number that divides n evenly, the function returns False, as n is not a prime number. If the loop completes without finding a number that divides n evenly, the function returns True, as n is a prime number.

Explanation for primepartition(m):
This is a function primepartition(m) that checks if a given number m can be expressed as the sum of two prime numbers.

The function first checks if m is less than or equal to 1, in which case it returns False since no sum of two primes can result in a value less than or equal to 1.

Otherwise, the function iterates over a range of integers starting from 2 and ending at m-1. For each integer i in the range, it checks if both i and m-i are prime numbers by calling the is_prime(i) function. If both i and m-i are prime, the function returns True.
If the loop completes without finding two prime numbers that add up to m, the function returns False, indicating that m cannot be expressed as the sum of two prime numbers.

Q.2:
Write a function matched(s) that takes as input a string s and checks if the brackets "(" and ")" in s are matched: that is, every "(" has a matching ")" after it and every ")" has a matching "(" before it. Your function should ignore all other symbols that appear in s. Your function should return True if s has matched brackets and False if it does not.
Here are some examples to show how your function should work.

>>> matched("zb%78")
True

>>> matched("(7)(a")
False

>>> matched("a)*(?")
False

>>> matched("((jkl)78(A)&l(8(dd(FJI:),):)?)")
True

Answer

def matched(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    return not stack

Explanation:
The function uses a stack data structure to keep track of the open brackets.
When an open bracket ( is encountered, it is pushed onto the stack.
When a close bracket ) is encountered, it is compared to the top element of the stack. If the stack is empty, it means there's a close bracket without a matching open bracket, so the function returns False. If the stack is not empty, the top element (open bracket) is popped from the stack.
Finally, if the stack is not empty at the end of the loop, it means there are open brackets without matching close brackets, so the function returns False.
Otherwise, it returns True.

Q.3:
A list rotation consists of taking the first element and moving it to the end. For instance, if we rotate the list [1,2,3,4,5], we get [2,3,4,5,1]. If we rotate it again, we get [3,4,5,1,2].

Write a Python function rotatelist(l,k) that takes a list l and a positive integer k and returns the list l after k rotations. If k is not positive, your function should return l unchanged. Note that your function should not change l itself, and should return the rotated list.
Here are some examples to show how your function should work.

>>> rotatelist([1,2,3,4,5],1)
[2, 3, 4, 5, 1]

>>> rotatelist([1,2,3,4,5],3)
[4, 5, 1, 2, 3]

>>> rotatelist([1,2,3,4,5],12)
[3, 4, 5, 1, 2]

Answer

 def rotatelist(l, k):
    if k <= 0:
        return l
    k = k % len(l)
    return l[k:] + l[:k]

Explanation:
This is a Python function that rotates the elements of a list l by k positions to the right. The rotation is performed by concatenating two slices of the list: the k elements starting from the end of the list, and the rest of the elements. The final result is a new list with the rotated elements.
If k is less than or equal to 0, the function returns the original list l without performing any rotation.
The rotation step also handles the case when k is greater than the length of the list l by using the modulo operator % to ensure that k is always less than the length of the list. This makes the rotation a cyclic shift, meaning that the elements that fall off one end of the list reappear at the other end.