(V SEM) THEORY EXAMINATION 2022-23 PROGRAMMING, DATA STRUCTURES AND ALGORITHMS USING PYTHON

SECTION A (2 × 10 = 20 Marks)

Attempt all questions in brief
 

(a) Characteristics of Python
Python is a high-level, interpreted programming language that is easy to learn and use. It supports object-oriented as well as procedural programming. Python is platform independent, which means the same code can run on different operating systems without modification. It uses dynamic typing, so variables do not need to be declared explicitly. Python has a large standard library that helps in rapid application development.
 

(b) Syntax of range() method
The range() function in Python is used to generate a sequence of numbers. Its syntax is range(start, stop, step). The start value indicates where the sequence begins, the stop value specifies where it ends (excluding that value), and the step value defines the difference between consecutive numbers. It is commonly used in loops for iteration.
 

(c) Tuple data structure
A tuple is an ordered collection of elements in Python that is immutable in nature. Once a tuple is created, its elements cannot be modified. Tuples are written using parentheses and are faster than lists. For example, a tuple can be created as t = (10, 20, 30). Tuples are mainly used when data should not be changed accidentally.
 

(d) Big O notation
Big O notation is used to describe the time complexity of an algorithm. It tells how the execution time of an algorithm increases with the size of input data. For example, a linear search algorithm has a time complexity of O(n), while a binary search algorithm has a time complexity of O(log n). Big O helps in comparing algorithm efficiency.
 

(e) Value of Y
Given X = “I love India” and Y = X[:9:2], Python slicing starts from index 0 up to index 8 and skips every second character. The resulting value of Y is “Ilv ni”.
 

(f) Variable length argument
Variable length arguments allow a function to accept any number of arguments. This is useful when the number of inputs is not fixed. In Python, this is achieved using *args. Inside the function, args behaves like a tuple and can be processed using loops or functions.
 

(g) Comparison between list and tuple
A list is mutable, which means its elements can be changed after creation, while a tuple is immutable. Lists use square brackets, whereas tuples use parentheses. Lists require more memory compared to tuples. Tuples are generally used for fixed data, while lists are used when data needs to be updated frequently.
 

(h) Importance of memoization
Memoization is a technique used to store the results of expensive function calls and reuse them when the same inputs occur again. It improves program efficiency, especially in recursive algorithms like Fibonacci or dynamic programming problems, by avoiding repeated calculations.
 

(i) Hashing and collision techniques
Hashing is a technique used to map keys to values using a hash function. A collision occurs when two keys generate the same hash value. To resolve collisions, techniques such as chaining, linear probing, quadratic probing, and double hashing are used.
 

(j) Abstract Data Type (ADT)
An abstract data type defines a data structure by specifying the operations that can be performed on it without specifying the implementation. Examples of ADTs include stack, queue, and list. ADTs help in separating data representation from data usage.
 

SECTION B (10 × 3 = 30 Marks)
 

(a) List comprehension and matrix multiplication
List comprehension is a concise way to create lists in Python using a single line of code. It improves code readability and efficiency. In matrix multiplication, list comprehension can be used to compute the product of two matrices by multiplying rows of the first matrix with columns of the second matrix and summing the results. This approach avoids nested loops and produces compact code.
 

(b) filter(), map(), and reduce() functions
The filter() function is used to select elements from a sequence based on a condition. The map() function applies a given function to each element of a sequence and returns a new sequence. The reduce() function, available in the functools module, reduces a sequence to a single value by repeatedly applying a function. These functions support functional programming in Python.
 

(c) Exception handling in Python
Exception handling is used to manage runtime errors and prevent program termination. Python uses try, except, and finally blocks to handle exceptions. For example, dividing a number by zero raises a ZeroDivisionError. Using exception handling ensures that the program continues to run smoothly even when errors occur.
 

(e) Binary search algorithm
Binary search is an efficient searching technique used on sorted lists. It works by repeatedly dividing the search interval into two halves. If the target value is less than the middle element, the search continues in the left half; otherwise, it continues in the right half. The time complexity of binary search is O(log n), which makes it faster than linear search.
 

SECTION C
 

Q3 (a) Queue data structure

A queue is a linear data structure that follows the First In First Out (FIFO) principle. The element that is inserted first is removed first. Basic operations performed on a queue are enqueue, dequeue, and peek. In Python, a queue can be implemented using a list where elements are added at the end and removed from the front.
 

Q4 (b) Loop control statements

Loop control statements are used to control the execution of loops. The break statement terminates the loop immediately. The continue statement skips the current iteration and moves to the next one. The pass statement acts as a placeholder and does nothing but avoids syntax errors when a statement is required.
 

Q5 (a) Merge sort

Merge sort is a divide and conquer algorithm that divides the list into smaller sublists until each sublist contains one element. Then, these sublists are merged in a sorted manner. Merge sort has a time complexity of O(n log n) and is suitable for sorting large datasets efficiently.
 

Q6 (a) Longest Common Subsequence (LCS)

The longest common subsequence problem involves finding the longest sequence that appears in the same order in two sequences. It is solved using dynamic programming. For X = (B, A, C, D, B) and Y = (B, D, C, B), the longest common subsequence is BCB.
 

Q7 (a) Binary Search Tree (BST)

A binary search tree is a hierarchical data structure where the left subtree contains elements smaller than the root and the right subtree contains elements larger than the root. Insertion is done by comparing values and placing them accordingly. Deletion of nodes such as 21 and 25 involves finding a suitable replacement, usually the inorder successor, to maintain the BST property.