1. Explain the concept of a 2D array with an example in Python.
A 2D array, also known as a two-dimensional array or a matrix, is a data structure that stores data in a grid-like format, consisting of rows and columns. Each element in a 2D array can be accessed using two indices: one for the row and one for the column. In Python, you can create a 2D array using a list of lists. Here’s an example: matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] print(matrix[1][2]) # Output: 6 (2nd row, 3rd column)
2. How can arrays be used to represent matrices? Write a code to
perform matrix addition. Arrays are ideal for representing matrices because they can store data in a structured way, with each row representing a different set of values. In Python, you can use nested lists (lists of lists) to represent matrices and perform operations like matrix addition. You can add two matrices (2D arrays) by summing their corresponding elements. def add_matrices(a, b): return [[a[i][j] + b[i][j] for j in range(len(a[0]))] for i in range(len(a))]
matrix_a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
matrix_b = [[9, 8, 7], [6, 5, 4], [3, 2, 1]] result = add_matrices(matrix_a, matrix_b) print(result) # Output: [[10, 10, 10], [10, 10, 10], [10, 10, 10]] 3. What are sparse matrices? Describe an application where sparse matrices are useful. Sparse matrices are matrices in which most of the elements are zero. sparse matrices typically have a significant number of zero entries. This property allows for more efficient storage and computation, as only the non-zero elements need to be stored, often using data structures like compressed sparse row (CSR) or compressed sparse column (CSC). Application of Sparse Matrices: One prominent application of sparse matrices is in graph theory, particularly in representing graphs for algorithms like Dijkstra's or PageRank. Social Networks: When representing users and their connections, most users will not be friends with every other user, leading to a sparse adjacency matrix. Web Page Link Analysis: Most pages link to only a small subset of other pages, resulting in a sparse matrix representation.
4. Write a program to search for an element in an array using linear
search. def linear_search(arr, target): for i, val in enumerate(arr): if val == target: return i return -1 # Example usage arr = [5, 3, 7, 2, 8] print(linear_search(arr, 7)) # Output: 2 Unit 2: Linked Lists 5. Differentiate between singly and doubly linked lists with diagrams. Singly Linked List Definition: A singly linked list is a data structure where each node contains a value and a pointer (or reference) to the next node in the sequence. It allows traversal in one direction only—from the head to the end of the list. Doubly Linked List Definition: A doubly linked list is a data structure where each node contains a value, a pointer to the next node, and a pointer to the previous node. This allows traversal in both directions—forward and backward.
Key Differences
Feature Singly Linked List Doubly Linked List
Direction of Two ways (forward and One way (forward only) Traversal backward)
Less memory (2 More memory (3
Memory Usage pointers/node) pointers/node)
Easier at the head/tail, but Easier at any point (can
Insertion/Deletion harder in the middle access both directions) Complexity of More complex due to extra Generally simpler Operations pointers
6. Write a Python program to insert a node at the beginning of a
singly linked list.
class Node: def __init__(self, data): self.data = data # Assign data to the node self.next = None # Initialize next as None class SinglyLinkedList: def __init__(self): self.head = None # Initialize head to None
def insert_at_beginning(self, data):
new_node = Node(data) # Create a new node new_node.next = self.head # Point the new node to the current head self.head = new_node # Update the head to the new node
def print_list(self): current = self.head # Start from the head while current: # Traverse the list print(current.data, end=" -> ") current = current.next print("None") # Indicate the end of the list
7. What is a circular linked list? List its applications
A circular linked list is a variation of a linked list in which the last node points back to the first node, creating a circular structure. This means that there is no null reference at the end of the list; instead, you can traverse the list starting from any node and return to that node after visiting all the nodes.
Applications of Circular Linked Lists:
1. Round Robin Scheduling:
o Used in operating systems for process scheduling. Each process is assigned a time slice in a circular manner, allowing fair time sharing among processes. 2. Circular Buffers: o Used in data buffering systems where the data is continuously written and read in a circular manner, helping manage memory efficiently. 3. Music Playlists: o In media players, circular linked lists can be used to create playlists where the last song points back to the first, allowing continuous playback. 4. Game Development: o In games, circular linked lists can be used to manage player turns in multiplayer games, cycling through players in a loop. 5. Network Data Management: o Used in network protocols for managing connections in a circular manner, facilitating easy traversal of nodes.
8. Explain how memory is allocated for linked lists.
Linked lists use dynamic memory allocation, allowing efficient use of memory and easy insertion or deletion of nodes without resizing.
Memory Allocation Process:
1. Node Structure: Each node contains:
o Data: The value stored in the node. o Pointer: A reference to the next node. 2. Dynamic Allocation: o In C/C++, memory is allocated using malloc:
struct Node* newNode = (struct
Node*)malloc(sizeof(struct Node));
o In Python, nodes are created using class instances, with memory
management handled automatically:
class Node: def __init__(self, data): self.data = data self.next = None
3. Linking Nodes: After creating a node, it is linked by setting the next
pointer of the previous node to the new node. 4. Deallocation: o In C/C++, memory is freed using free(). o In Python, garbage collection manages memory automatically.
9. Describe a scenario where a doubly linked list is preferred over a
singly linked list. A doubly linked list is often preferred over a singly linked list in scenarios where bidirectional traversal is needed.
Scenario: Implementing a Music Playlist
Imagine you're creating a music player that allows users to navigate through a playlist of songs. Users want the ability to:
1. Move to the next song:This requires moving forward in the list.
2. Go back to the previous song:This requires moving backward in the list.
In this case, a doubly linked list would be ideal because each node contains references (pointers) to both the next and the previous nodes. This allows:
- Efficient navigation to the next song with a simple pointer to the next node.
- Easy backward traversal to the previous song without needing to traverse the entire list from the start.
Using a singly linked list would complicate backward navigation, requiring
additional logic to traverse the list from the head each time a user wants to go back, resulting in decreased performance and increased complexity.
Thus, for applications requiring frequent bidirectional access, a doubly linked list provides a clear advantage.
10. Implement a function to reverse a singly linked list.
class Node: def __init__(self, data): self.data = data self.next = None def reverse_linked_list(head): previous, current = None, head while current:
current.next, previous, current = previous, current, current.next
