DSA Midterm PDF

Introduction to Data Structures and Algorithms Data Structures: Ways to organize and store data in a computer so it can be used efficiently. Think of them like containers for your data. Examples: lists, dictionaries, trees. Algorithms: Step-by-step procedures or formulas for solving problems or...

Introduction to Data Structures and Algorithms Data Structures: Ways to organize and store data in a computer so it can be used efficiently. Think of them like containers for your data. Examples: lists, dictionaries, trees. Algorithms: Step-by-step procedures or formulas for solving problems or performing tasks using data. Like recipes for manipulating data. Examples: searching, sorting. Why they matter: A way to organize and manipulate data effectively. Using the right data structure and algorithm can make your code faster, more efficient, and easier to manage. keyboard_arrow_down Overview of Data Structures Different data structures excel at different tasks. 1. Linear Data Structures: Arrays: A contiguous block of memory storing elements of the same data type. Accessing elements is fast using their index.  Linked Lists: Elements are stored in nodes, where each node points to the next. Useful for dynamic data where insertions and deletions are frequent. Stacks: Follows the LIFO (Last-In, First-Out) principle. Think of a stack of plates. Queues: Follows the FIFO (First-In, First-Out) principle. Think of a line of people waiting. 2. Non-linear Data Structures: Trees: Hierarchical structures with a root node and branches. Used for representing hierarchical data. Binary Trees: Each node has at most two children. Binary Search Trees: A type of binary tree where the left subtree contains smaller values and the right subtree contains larger values. Heaps: A special type of tree used for priority queues. Tries: Tree-like structures used for efficient string prefix searching. Graphs: A collection of nodes (vertices) connected by edges. Useful for representing networks and relationships. Directed Graphs: Edges have a direction. Undirected Graphs: Edges have no direction. Hash Tables: Use a hash function to map keys to indices in an array. Allows for fast data retrieval. keyboard_arrow_down Big O notation A way to describe the efficiency of an algorithm. It focuses on how the runtime or space usage of an algorithm grows as the input size increases. It provides an upper bound on the growth rate, meaning it describes the worst-case scenario. It's expressed using "O" followed by a function that represents the growth rate (e.g., O(n), O(n^2)). Big O notation primarily expresses the upper bound of an algorithm’s runtime or space complexity, which is typically used to describe the worst-case performance as the input size increases. It doesn't provide exact execution time or account for average or best-case scenarios. Why is it Important? Helps compare the efficiency of different algorithms. Allows us to predict how an algorithm will perform with larger datasets. Essential for designing scalable and optimized code. Common Big O Notations: O(1): Constant time. The algorithm takes the same amount of time regardless of the input size. O(log n): Logarithmic time. The runtime grows slowly as the input size increases. Common in algorithms that divide the problem in half repeatedly (e.g., binary search). O(n): Linear time. The runtime grows proportionally with the input size. Common in algorithms that iterate through each element of the input (e.g., linear search). O(n log n): Linearithmic time. A combination of linear and logarithmic growth. Common in efficient sorting algorithms like merge sort. O(n^2): Quadratic time. The runtime grows proportionally to the square of the input size. Common in algorithms with nested loops that iterate over the input multiple times (e.g., bubble sort). O(2^n): Exponential time. The runtime doubles with each increase in input size. These algorithms can become very slow for large inputs.  O(n!): Factorial time. The runtime grows extremely quickly with the input size. These algorithms are generally impractical for large inputs. keyboard_arrow_down Python Programming Fundamentals Python is a versatile and beginner-friendly programming language known for its readability and extensive libraries. Its interpreted nature and dynamic typing make it easy to learn and use, while its object-oriented features and large community support its use in a wide range of applications, from web development to data science and machine learning. Though it may have slower execution compared to compiled languages, its overall ease of use and versatility make it a popular choice for both novice and experienced programmers. History Late 1980s: Guido van Rossum begins work on Python at the National Research Institute for Mathematics and Computer Science in the Netherlands. February 1991: The first version of Python (0.9.0) is released. It's influenced by languages like ABC, Modula-3, and C. 1994: Python 1.0 is released with features like lambda, map, filter, and reduce. 2000: Python 2.0 is released with list comprehensions and a garbage collection system.  2008: Python 3.0 is released, a major revision that's not fully compatible with Python 2. 2010s: Python gains immense popularity in data science, machine learning, and web development. 2020: Python 2 reaches its end of life, with support officially discontinued. Present: Python continues to evolve with new features and improvements, remaining one of the most widely used programming languages worldwide. # ---------------------------- # Data Types # ---------------------------- # Integer: Represents whole numbers age = 30 print(f"Age (int): {age}") # Float: Represents decimal numbers price = 19.99 print(f"Price (float): {price}") # String: Represents text enclosed in quotes name = "Alice" print(f"Name (str): {name}") # Boolean: Represents True or False values is_student = True print(f"Is Student (bool): {is_student}") # List: An ordered, mutable collection grades = [85, 90, 95] print(f"Grades (list): {grades}") # Tuple: An ordered, immutable collection coordinates = (10, 20) print(f"Coordinates (tuple): {coordinates}") # Dictionary: A collection of key-value pairs person = {'name': 'Bob', 'age': 25} print(f"Person (dict): {person}") # Set: An unordered collection of unique items unique_numbers = {1, 2, 3} print(f"Unique Numbers (set): {unique_numbers}") Age (int): 30 Price (float): 19.99 Name (str): Alice Is Student (bool): True Grades (list): [85, 90, 95] Coordinates (tuple): (10, 20)  Person (dict): {'name': 'Bob', 'age': 25} Unique Numbers (set): {1, 2, 3} # ---------------------------- # Control Structures # ---------------------------- # Conditional Statement (if-else) if age >= 18: print("You are an adult.") else: print("You are a minor.") # Membership Check using 'in' names = ["Alice", "Bob", "Charlie"] if "Alice" in names: print("Alice is in the list.") else: print("Alice is not in the list.") You are an adult. Alice is in the list. # ---------------------------- # Loops # ---------------------------- # For Loop using range(start, stop, step) print("For loop with range(0, 10, 2):") for i in range(0, 10, 2): print(i) print("\nWhile Loop with condition price > 10:") # While Loop with a condition while price > 10: price -= 1 # Decrement price by 1 in each iteration print(f"Decremented Price: {price}") For loop with range(0, 10, 2): 0 2 4 6 8 While Loop with condition price > 10: Decremented Price: 18.99 Decremented Price: 17.99 Decremented Price: 16.99 Decremented Price: 15.989999999999998 Decremented Price: 14.989999999999998  Decremented Price: 13.989999999999998 Decremented Price: 12.989999999999998 Decremented Price: 11.989999999999998 Decremented Price: 10.989999999999998 Decremented Price: 9.989999999999998 # ---------------------------- # Functions # ---------------------------- def greet(name: str) -> None: """ Greets the person with the given name. Parameters: name (str): The name of the person to greet. """ print(f"Hello, {name}!") def calculate_average(grades_list: list) -> float: """ Calculates the average of a list of grades. Parameters: grades_list (list): A list of numerical grades. Returns: float: The average grade. """ if not grades_list: return 0.0 return sum(grades_list) / len(grades_list) # Calling functions greet("Alice") average_grade = calculate_average(grades) print(f"Average Grade: {average_grade}") Hello, Alice! Average Grade: 90.0 keyboard_arrow_down Arrays and Linked Lists Arrays are contiguous blocks of memory that store elements of the same data type. They provide fast access to elements using their index (position). However, inserting or deleting elements in the middle of an array can be inefficient as it requires shifting other elements. # Array (list) example array = [10, 20, 30, 40] # An array of integers # Accessing elements print("First element:", array) # Output: 10 # Adding an element array.append(50) # Removing an element array.remove(20) # Iterating over array elements for element in array: print(element) First element: 10 10 30 40 50 Linked lists are data structures where elements are stored in nodes. Each node contains data and a pointer to the next node in the sequence. Linked lists are dynamic, meaning their size can change easily during runtime. Insertions and deletions are efficient as they only require updating pointers # Node class for the linked list class Node:  def __init__(self, data): self.data = data # Node data self.next = None # Pointer to the next node # LinkedList class class LinkedList: def __init__(self): self.head = None # Initialize the linked list with a head node # Add a new node at the end def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node else: current = self.head while current.next: # Traverse to the end of the list current = current.next current.next = new_node # Print all elements in the linked list def print_list(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") # Creating a linked list linked_list = LinkedList() linked_list.append(10) linked_list.append(20) linked_list.append(30) # Printing the linked list linked_list.print_list() 10 -> 20 -> 30 -> None keyboard_arrow_down Stack and Queues Stacks are linear data structures that follow the LIFO (Last-In, First-Out) principle. Think of a stack of plates – the last plate placed on top is the first one removed. Basic Operations: push(item): Adds an item to the top of the stack.  pop(): Removes and returns the item from the top of the stack. peek(): Returns the item at the top without removing it. isEmpty(): Checks if the stack is empty. # Stack stack = [] stack.append(1) # push(1) stack.append(2) # push(2) stack.append(3) # push(3) print(stack.pop()) # Output: 3 (pop()) print(stack) # Output: [1, 2] 3 [1, 2] Queues are linear data structures that follow the FIFO (First-In, First-Out) principle. Think of a line of people waiting – the first person in line is the first one served. Basic Operations: enqueue(item): Adds an item to the rear of the queue.  dequeue(): Removes and returns the item from the front of the queue. front(): Returns the item at the front without removing it. isEmpty(): Checks if the queue is empty. # Queue (using list as a simple queue - not ideal for large queues) queue = [] queue.append(1) # enqueue(1) queue.append(2) # enqueue(2) queue.append(3) # enqueue(3) print(queue.pop(0)) # Output: 1 (dequeue() - inefficient with list) print(queue) # Output: [2, 3] 1 [2, 3] keyboard_arrow_down Recursion Recursion is a technique where a function calls itself within its definition.  It involves breaking down a problem into smaller, self-similar subproblems. Recursion occurs when a function calls itself either directly or indirectly, and it must have a base condition to prevent infinite calls. Base Case: A condition that stops the recursion, preventing infinite loops. Recursive Case: The part where the function calls itself with a modified input. def factorial(n): if n == 0: # Base case return 1 else: return n * factorial(n - 1) # Recursive case print(factorial(5)) 120 Benefits of Recursion: Can simplify the solution to complex problems. Naturally suited for working with recursive data structures. Drawbacks: Can be less efficient than iterative solutions in some cases. Potential for stack overflow errors if recursion depth is too high. keyboard_arrow_down Iteration Iteration is a method of solving problems using loops (such as for or while) to repeat a block of code until a condition is met. Key Characteristics: Looping: It continues executing until a specific condition is satisfied.  State Management: It maintains state through loop variables. def factorial(n): result = 1 for i in range(1, n + 1): result *= i return result # Test the iterative factorial function print(factorial(5)) 120 keyboard_arrow_down Trees and Binary Search Tree A tree is a hierarchical data structure consisting of nodes connected by edges. It resembles an inverted tree structure, where the top node is called the root, and the nodes below are called children. Each node can have zero or more children, and nodes with the same parent are called siblings. Key Characteristics of Trees: Node: The fundamental part of a tree that contains data and may link to other nodes. Root: The top node of the tree. Leaf Node: A node that has no children. Height: The length of the longest path from the root to a leaf node. Depth: The length of the path from the root to a given node. Basic Terminology: Subtree: A tree consisting of a node and its descendants. Degree: The number of children a node has. Binary Search Trees (BSTs) are a special type of tree where each node has at most two children (left and right). A BST maintains a strict order where the left subtree contains smaller elements and the right subtree contains larger elements. In contrast, a heap (min-heap or max-heap) only maintains a priority structure, not a sorted order. They follow a specific property: The left subtree of a node contains values smaller than the node's value.  The right subtree of a node contains values greater than the node's value. Tree Traversals are algorithms for visiting all nodes in a tree in a specific order. Common types: Postorder: Visit the left subtree, then the right subtree, then the current node. Inorder: Visit the left subtree, then the current node, then the right subtree. Preorder: Visit the current node, then the left subtree, then the right subtree. Start coding or generate with AI. from collections import deque class TreeNode: def __init__(self, key): self.left = None self.right = None self.value = key class BinarySearchTree: def __init__(self): self.root = None def insert(self, key): if self.root is None: self.root = TreeNode(key) else: self._insert_recursive(self.root, key) def _insert_recursive(self, node, key): if key < node.value: if node.left is None: node.left = TreeNode(key) else: self._insert_recursive(node.left, key) else: # key >= node.value  if node.right is None: node.right = TreeNode(key) else: self._insert_recursive(node.right, key) def print_tree(self, node, level=0, prefix="Root: "): if node is not None: print(" " * (level * 4) + prefix + str(node.value)) self.print_tree(node.left, level + 1, "L--- ") self.print_tree(node.right, level + 1, "R--- ") def in_order_traversal(self, node): if node: self.in_order_traversal(node.left) print(node.value, end=" ") self.in_order_traversal(node.right) def pre_order_traversal(self, node): if node: print(node.value, end=" ") self.pre_order_traversal(node.left) self.pre_order_traversal(node.right) def post_order_traversal(self, node): if node: self.post_order_traversal(node.left) self.post_order_traversal(node.right) print(node.value, end=" ") def level_order_traversal(self, root): if not root: return queue = deque([root]) while queue: node = queue.popleft() print(node.value, end=" ") if node.left: queue.append(node.left) if node.right: queue.append(node.right) # Example Usage bst = BinarySearchTree() # Inserting values into the BST values = [10, 5, 15, 3, 7, 12, 18] for value in values: bst.insert(value) print("Binary Search Tree:") bst.print_tree(bst.root)  Binary Search Tree: Root: 10 L--- 5 L--- 3 R--- 7 R--- 15 L--- 12 R--- 18 print("In-Order Traversal: ", end="") bst.in_order_traversal(bst.root) print() In-Order Traversal: 3 5 7 10 12 15 18 print("Pre-Order Traversal: ", end="") bst.pre_order_traversal(bst.root) print() Pre-Order Traversal: 10 5 3 7 15 12 18 print("Post-Order Traversal: ", end="") bst.post_order_traversal(bst.root) print() Post-Order Traversal: 3 7 5 12 18 15 10 print("Level Order Traversal: ", end="") bst.level_order_traversal(bst.root) print() Level Order Traversal: 10 5 15 3 7 12 18 keyboard_arrow_down Heaps A heap is a specialized tree-based data structure that satisfies the heap property. A heap allows efficient retrieval of the highest-priority node. There are two types of heaps: Max Heap: In a max heap, for any given node, the value of that node is greater than or equal to the values of its children. The highest value is at the root of the tree. Min Heap: In a min heap, for any given node, the value of that node is less than or equal to the values of its children. The lowest value is at the root of the tree. Heaps are typically implemented as binary trees, where the shape of the tree is a complete binary tree. This property allows for efficient insertion and deletion operations. A priority queue is an abstract data type that operates similar to a regular queue but with an added feature that each element has a priority. Elements with higher priorities are served before elements with lower priorities. Operations Insertion: Add an element to the heap while maintaining the heap property. Deletion (Extract Max/Min): Remove the root element (max or min) and reorganize the heap to maintain the heap property. Peek (Get Max/Min): Retrieve the root element without removing it. Heapify: Rearrange a collection of elements into a valid heap. class Heap: def __init__(self, is_min_heap=True): """Initialize a heap. Set is_min_heap to True for Min Heap, False for Max He self.heap = [] self.is_min_heap = is_min_heap def insert(self, value): """Insert a new value into the heap and restore the heap property.""" self.heap.append(value) self._bubble_up(len(self.heap) - 1) def extract(self): """Remove and return the root value (min or max) from the heap.""" if len(self.heap) == 0: return None if len(self.heap) == 1: return self.heap.pop() root_value = self.heap self.heap = self.heap.pop() self._bubble_down(0) return root_value def peek(self): """Return the root value without removing it from the heap.""" return self.heap if self.heap else None def _bubble_up(self, index): """Restore the heap property by bubbling the value at index up.""" parent_index = (index - 1) // 2 if index > 0 and self._compare(self.heap[index], self.heap[parent_index]): self.heap[index], self.heap[parent_index] = self.heap[parent_index], sel self._bubble_up(parent_index) def _bubble_down(self, index): """Restore the heap property by bubbling the value at index down.""" child_index = self._get_preferred_child_index(index) if child_index is not None: self.heap[index], self.heap[child_index] = self.heap[child_index], self. self._bubble_down(child_index) def _compare(self, child, parent): """Compare two values based on heap type (min or max).""" return child < parent if self.is_min_heap else child > parent def _get_preferred_child_index(self, index): """Determine the preferred child index for bubbling down.""" left_child = 2 * index + 1 right_child = 2 * index + 2 preferred_index = None if left_child < len(self.heap) and (preferred_index is None or self._compare preferred_index = left_child if right_child < len(self.heap) and self._compare(self.heap[right_child], se preferred_index = right_child return preferred_index def print_heap(self, index=0, level=0, prefix="Root: "): """Print the structure of the heap visually.""" if index < len(self.heap): print(" " * (level * 4) + prefix + str(self.heap[index]))  self.print_heap(2 * index + 1, level + 1, "L--- ") self.print_heap(2 * index + 2, level + 1, "R--- ") # Example Usage min_heap = Heap(is_min_heap=True) # Inserting elements into the min heap min_elements = [10, 10, 2, 5, 7, 1, 4] for element in min_elements: min_heap.insert(element) # Printing the Min Heap structure print("Min Heap:") min_heap.print_heap() Min Heap: Root: 1 L--- 5 L--- 10 R--- 7 R--- 2 L--- 10 R--- 4 # Example Usage max_heap = Heap(is_min_heap=False) # Inserting elements into the max heap max_elements = [7, 15, 13, 17, 0, 5, 1] for element in max_elements: max_heap.insert(element) # Printing the Max Heap structure print("\nMax Heap:") max_heap.print_heap() Max Heap: Root: 17 L--- 15 L--- 7 R--- 0 R--- 13 L--- 5 R--- 1 keyboard_arrow_down Bubble Sort  is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted. def bubble_sort_ascending(arr): n = len(arr) for i in range(n): swapped = False for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True