Subtopic Notes
19.1 Algorithms
19. Computational thinking and Problem-solving
Chapter 19 - Computational thinking and Problem-solving
From this part of the book onward, only python will be used as program code. In the syllabus python, java and visual basic are all allowed but I am using python as it is the easiest.
Algorithm Performance
- Different algorithms can perform the same task, but may vary in efficiency
- Criteria for comparison
- Time complexity: How long an algorithm takes to complete a task.
- Space complexity: How much memory an algorithm uses while running.
Big O Notation
- A mathematical notation used to describe the upper bound of an algorithm’s running time or memory usage as input size grows.
- Focuses on the worst-case scenario.
- Common Big O examples:
- O(1): Constant time - execution time does not depend on input size.
- O(n): Linear time - execution time grows linearly with input size.
- O(n²): Quadratic time - execution time grows with the square of input size.
- O(log n): Logarithmic time - execution time grows slowly as input increases.
Searching Algorithms
Linear Search
Simple searching algorithm that checks each element in a list or array sequentially until it finds the desired value.
Time Complexity: O(n)
Space Complexity: O(1)
numbers = [0, 6, 7, 96, 6, 5, 6, 0, 6, 4, 95, 2, 3] target = 95 #Number to search foundIndex = -1 for index in range(len(numbers)): if numbers[index] == target: foundIndex = index break if foundIndex == -1: print("Not Found") else: print("Found at index:" , foundIndex) |
|---|
Binary Search
- It works by repeatedly dividing the search range in half until the item is found or the range becomes empty.
- Instead of checking every item, binary search quickly narrows down where the item could be.
- Necessary Condition: The data must be sorted
- As more items are added, the time increases, but since the data is halved each time, it grows more slowly and eventually becomes almost constant
- Time Complexity:
- Best Case: O(1) - The target is found at the middle element
- Worst/Average Case: O(log₂ n)
- Space Complexity: O(1)
def binary_search(arr, target): # Set the starting and ending indexes low = 0 high = len(arr) - 1 # Continue searching while there is a range to check while low <= high: # Find the middle index mid = (low + high) // 2 # Check if the middle element is the target if arr[mid] == target: return mid # Target found, return its position # If target is smaller, ignore the right half elif arr[mid] > target: high = mid - 1 # If target is larger, ignore the left half else: low = mid + 1 return -1 # Target not found |
|---|
Sorting Algorithms
Insertion Sort
Insertion sort builds a sorted list one element at a time by inserting each item into its correct position.
- Time Complexity:
- Best case: O(n) (already sorted)
- Worst case: O(n²) (reverse order)
- Space Complexity: O(1)
numbers = [0, 6, 7, 96, 6, 5, 6, 0, 6, 4, 95, 2, 3] print("Before sorting:", numbers) # Start from the second element for i in range(1, len(numbers)): key = numbers[i] # Current element to insert j = i - 1 # Move elements greater than key one position to the right while j >= 0 and numbers[j] > key: numbers[j + 1] = numbers[j] j -= 1 # Insert key into the correct position numbers[j + 1] = key print("After sorting:", numbers) |
|---|
Bubble Sort
Sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order and iterates until the list is sorted.
Time Complexity:
- Best case: O(n) (optimized version, already sorted)
- Worst case: O(n²) (reverse order)
Space Complexity: O(1)
numbers = [0, 6, 7, 96, 6, 5, 6, 0, 6, 4, 95, 2, 3] # Outer loop to iterate through the list n times for i in range(len(numbers) - 1, 0, -1): swapped = False # Inner loop to compare adjacent elements for j in range(i): if numbers[j] > numbers[j + 1]: #Swapping elements temp = numbers[j] numbers [j] = numbers[j + 1] numbers[j + 1] = temp swapped = True # If no swaps occurred, the list is already sorted if not swapped: break print(numbers) #Shows the sorted array |
|---|
Abstract Data Types
Defines a data structure by its behavior from the user's perspective, rather than its concrete implementation
Stack
- A list operating on the Last In First Out principle (LIFO).
- Push: Adding item to stack
- Pop: Removing item from the stack
- isEmpty: Checks if stack is empty
- The first item added to the stack is the last item that can be removed
- Implementing stack using array
- Declare an array to store the contents of stack
- Declare a stack pointer pointing to the index of last element added (Value -1 if stack is empty)
- Uses: Managing function calls, Syntax parsing in compilers, Recursion, 'Undo' functions, System memory architecture, Browsing history, Expression parsing (Reverse Polish Notation)
- Advantage: Simple, Efficient, Limited Memory, LIFO
- Disadvantage: Limited access, Random access not possible, Limited capacity leading to overflow
class Stack: def __init__(self, maxSize): self.items = [""] * maxSize self.pointer = -1 def push(self, data): if self.pointer >= len(self.items) - 1: print("Stack Overflow") else: self.pointer += 1 self.items[self.pointer] = data def pop(self): if self.pointer == - 1: print("Stack Underflow") else: item = self.items[self.pointer] self.items[self.pointer] = "" self.pointer -= 1 return item #Printing items of the stack def Display(self): if self.Ptr == -1: print("Stack is empty") else: print("Stack elements:") for i in range(self.Ptr, -1, -1): print(self.items[i]) |
|---|
Queue
- A list operating on the First In First Out principle (FIFO)
- The first item added is the first item to be removed
- Data is added from the rear end by using the EndPointer/TailPointer and removed from the front by using the StartPointer/HeadPointer
- Enqueue: Add an element to the back of the queue.
- Dequeue: Remove the element at the front of the queue.
- isEmpty: Check if the queue is empty.
- Applications: Task Scheduling in OS and printer, Handling request in web server, streaming, call centers, handling packets, messaging or ordering services, video or mp3 players, traffic management, physical queues like supermarket
- Linear Queue: Normal queue following simple FIFO queue; cannot reuse freed spaces
- Circular Queue: Last position is connected back to the first position to form a circle, it reuses empty spaces in the list
- Advantages: Large data managed efficiency, multi user services
- Disadvantages: Operations on middle elements are hard, maximum size defined before implementation
Code for linear queue
class Queue: def __init__(self, max_size=8): # Maximum no. of item queue can hold self.max_size = max_size # The queue is stored in a list (array) self.queue = [""] * max_size # Front (or head) points to the position of the first item self.front = 0 # Rear/Tail points to the position where the last item was added self.rear = -1 # Insert item into the queue (Enqueue) def enqueue(self, data): # Check if queue is full (rear is at last position) if self.rear >= self.max_size - 1: print("Queue overflow") else: # Move rear (tail) forward and add new item self.rear += 1 self.queue[self.rear] = data print(data, "added to the queue") # Delete item from the queue (Dequeue) def dequeue(self): # Check if queue is empty (no items left) if self.front > self.rear: print("Queue underflow") # Nothing to remove return None else: # Get the item from the front (head) item = self.queue[self.front] # Move front (head) one step forward self.front += 1 print(item, "removed from the queue") return item # Example usage q = Queue() # Create a new queue # Add items q.enqueue("Apple") q.enqueue("Banana") q.enqueue("Cherry") # Remove items q.dequeue() q.dequeue() q.dequeue() q.dequeue() # Will show underflow |
|---|
Code for Circular Queue
class CircularQueue: def __init__(self, max_size=8): # Maximum number of items the queue can hold self.max_size = max_size # The queue is stored in a list (array) self.queue = [""] * max_size # Front (or head) points to the first item to be removed # Rear (or tail) points to the last item added self.front = -1 self.rear = -1 # Insert an item into the queue (Enqueue) def enqueue(self, data): # Check if queue is full: # If moving rear forward would make it equal to front, # that means the queue has wrapped around and is now full if (self.rear + 1) % self.max_size == self.front: print("Queue overflow") else: # If queue is currently empty (no items), # set both front and rear to 0 (starting position) if self.front == -1: self.front = 0 # Move rear forward in a circular manner # (wraps around to 0 when it reaches the end) self.rear = (self.rear + 1) % self.max_size # Store the new item at the rear position self.queue[self.rear] = data print(data, "added to the queue") # Remove an item from the queue (Dequeue) def dequeue(self): # Check if queue is empty (no items left) if self.front == -1: print("Queue underflow") return None else: # Get the item from the front (head) item = self.queue[self.front] # If there was only one element, # reset both front and rear to -1 (queue becomes empty) if self.front == self.rear: self.front = -1 self.rear = -1 else: # Move front forward in a circular manner self.front = (self.front + 1) % self.max_size print(item, "removed from the queue") return item # Example usage q = CircularQueue() # Create a circular queue # Add items q.enqueue("Apple") q.enqueue("Banana") q.enqueue("Cherry") # Remove one item q.dequeue() # Add another item (will reuse the freed space) q.enqueue("Mango") |
|---|
Linked List
- Nodes: Basic data structure which contains data and one or more links/pointers to other nodes. Nodes can be used to represent a tree structure or a linked list.
- Node’s successor is the next node
- Node's predecessor is the previous node
- Pointers: Variable that stores the memory address of another variable as its value
- A linked list is a data structure used to store a collection of items where each item is linked to the next one using pointers.
- Traverse a linked list: Start at the first node and then go from node to node, following each node’s pointer to find the next node.
- Two types depending on how data is sorted: ordered and unordered.
- Linked List can be implemented using 2D Arrays (Singly)
- The arrays are for data and the other for pointers
- Uses:
- Image viewer, Pages in Web browser, Music/Video Player, GPS, Task Scheduling, Symbol Table in Compilers, Undo and Redo
- Advantage: Fast insertion and deletion
- Disadvantage: Slow Search
Code for Linked List
class Node: #Repesents each element def __init__(self, data): self.data = data # Store the actual value of the node self.next = None # Pointer to the next node in the list (None if last node) class LinkedList: def __init__(self): self.head = None # Head points to the first node in the list, None if list is empty # Insert item at the end of the linked list def insert(self, data): new_node = Node(data) # Create a new node with given data if self.head == None: # If list is empty self.head = new_node # Make new node the head print(data, "inserted as head") return # Otherwise, traverse to the last node current = self.head while current.next != None: # While there is a next node current = current.next # Move to the next node current.next = new_node # Link the last node to the new node print(data, "inserted at the end") # Find an item in the linked list def find(self, key): current = self.head # Start from the head while current != None: # Traverse until the end if current.data == key: # If the data matches the key print(key, "found in the list") return True # Return True if found current = current.next # Move to next node print(key, "not found in the list") # Key was not found return False # Delete an item from the linked list def delete(self, key): current = self.head prev = None # To keep track of the previous node # Case 1: If head itself holds the key if current != None and current.data == key: self.head = current.next # Update head to next node print(key, "deleted from the list") return # Case 2: Search for the key in the list while current != None and current.data != key: prev = current # Keep track of previous node current = current.next # Move to next node # Key not found in the list if current == None: print(key, "not found in the list") return # Key found somewhere other than head prev.next = current.next # Bypass the node to delete it print(key, "deleted from the list") # Display all items in the linked list def display(self): current = self.head if current == None: # List is empty print("List is empty") return # Traverse the list and print each node's data while current != None: print(current.data, end=" -> ") current = current.next print("None") # End of list # Example usage ll = LinkedList() # Create a linked list # Insert nodes ll.insert(10) # Insert first node ll.insert(20) # Insert at end ll.insert(30) # Insert at end ll.display() # Display list: 10 -> 20 -> 30 -> None # Find nodes ll.find(20) # Should print found ll.find(40) # Should print not found # Delete nodes ll.delete(20) # Delete middle node ll.display() # Display list: 10 -> 30 -> None ll.delete(10) # Delete head node ll.display() # Display list: 30 -> None ll.delete(50) # Try to delete non-existent node |
|---|
Binary Tree
- Data structure in which each node has at most two children, referred to as the left child and the right child.
- The nodes are arranged in a hierarchical structure, with a root node at the top and the leaves at the bottom
- Traversing a tree
- Preorder: Root → Left → Right (1 → 2 → 4 →8 → 9 → 5 → 10 → 3 → 6 → 7)
- Inorder: Left → Root → Right (8 → 4 → 9 → 2 → 10 → 5 → 1 → 6 → 7 → 3)
- Postorder: Left → Right → Root (8 → 9 → 4 → 10 → 5 → 2 → 6 → 7 → 3 → 1)
Binary Search Tree
A binary search tree (BST) is a binary tree in which each node has a value greater than all the values in its left subtree and less than all the values in its right subtree.
Advantage: Fast Search, insertion and deletion
Traversing in Binary Search Tree
- Inorder
- Left → Root → Right
- 1 → 3 → 2 → 4 → 5 → 6 → 8 → 9 → 10 → 11
- Preorder
- Root → Left → Right
- 8 → 4 → 3 → 1 → 2 → 6 → 5 → 10 → 9 → 11
- Post Order
- Left → Right → Root
- 1 → 2 → 3 → 5 → 6 → 4 → 9 → 11 → 10 → 8
- Searching for a particular data
- Start at the root node and keep comparing
- If search value smaller than current node, go left
- If search value bigger than current node, go right
- Finding Minimum Value
- Go to the leftmost child (One with no left-child)
- Finding Maximum Value
- Go to the rightmost child (One with no right-child)
- Adding/Inserting a Value
- Start at the root and compare the value you want to insert.
- Move left or right:
- If the value is smaller than the current node, go to the left child.
- If the value is larger than the current node, go to the right child.
- Find the correct position:
- If the tree is empty, insert the value at the root.
- Otherwise, traverse until you find a leaf node (a node with no child in the required direction).
- Insert the new node:
- If the new value is smaller than the parent, make it the left child.
- If the new value is larger than the parent, make it the right child.
- For duplicate values, it is safest to avoid insertion, or optionally, insert as the right child of the duplicate
Code for Binary Tree
class BinaryTreeArray: def __init__(self, max_size=20): # Each node: [value, left_index, right_index] self.tree = [[None, -1, -1] for _ in range(max_size)] self.root_index = -1 # Index of root node self.next_free = 0 # Next free position in the array self.max_size = max_size # Insert a new value into the tree def insert(self, value): if self.next_free >= self.max_size: print("Tree full, cannot insert", value) return # Create new node at next free index node_index = self.next_free self.tree[node_index][0] = value self.tree[node_index][1] = -1 self.tree[node_index][2] = -1 self.next_free += 1 # If tree is empty, make new node root if self.root_index == -1: self.root_index = node_index print(value, "inserted as root") return # Otherwise, find correct parent current = self.root_index while True: if value < self.tree[current][0]: if self.tree[current][1] == -1: self.tree[current][1] = node_index print(value, "inserted as left child of", self.tree[current][0]) break else: current = self.tree[current][1] elif value > self.tree[current][0]: if self.tree[current][2] == -1: self.tree[current][2] = node_index print(value, "inserted as right child of", self.tree[current][0]) break else: current = self.tree[current][2] else: print("Duplicate key", value, "ignored") break # Find a value in the tree def find(self, value): current = self.root_index while current != -1: if self.tree[current][0] == value: print(value, "found in the tree") return True elif value < self.tree[current][0]: current = self.tree[current][1] else: current = self.tree[current][2] print(value, "not found in the tree") return False # Inorder traversal: Left, Root, Right def inorder(self, index=None): if index is None: index = self.root_index if index == -1: return self.inorder(self.tree[index][1]) # Left child print(self.tree[index][0], end=" ") # Root self.inorder(self.tree[index][2]) # Right child # Preorder traversal: Root, Left, Right def preorder(self, index=None): if index is None: index = self.root_index if index == -1: return print(self.tree[index][0], end=" ") # Root self.preorder(self.tree[index][1]) # Left child self.preorder(self.tree[index][2]) # Right child # Postorder traversal: Left, Right, Root def postorder(self, index=None): if index is None: index = self.root_index if index == -1: return self.postorder(self.tree[index][1]) # Left child self.postorder(self.tree[index][2]) # Right child print(self.tree[index][0], end=" ") # Root # Example usage bt = BinaryTreeArray() bt.insert(50) bt.insert(30) bt.insert(70) bt.insert(20) bt.insert(40) bt.insert(60) bt.insert(80) print("Inorder traversal: ", end="") bt.inorder() print() print("Preorder traversal: ", end="") bt.preorder() print() print("Postorder traversal: ", end="") bt.postorder() print() # Find values bt.find(60) # Found bt.find(25) # Not found |
|---|
Graph
- A graph is an Abstract Data Type (ADT) because it models relationships between objects without specifying implementation.
- It defines operations like adding vertices and edges, and traversing connections.
- Vertices (nodes): Represent objects.
- Edges (links): Represent relationships
- Traversal: Explore connections between vertices.
- Use Cases:
- Graphs are useful when relationships matter, e.g., social networks, transport routes, computer networks, or task dependencies
- Weighted Graph: Edge has an associated value (weight), representing cost, distance, time, or capacity.
- Directed Graph: Edges have a direction, going from one vertex to another
Examples of ADTs and Possible Implementations
- Stack
- Using lists/arrays: Append to the end and remove from the end.
- Using linked lists: Insert and remove at the head.
- Queue
- Using lists/arrays: Append at the end and remove from the front (or use circular arrays).
- Using linked lists: Insert at tail, remove from head
- Linked List
- Using nodes and pointers explicitly.
Can also be emulated using arrays/lists where each element stores the value and index of the next element.
- Using nodes and pointers explicitly.
- Dictionary: Stores key-value pairs, allowing retrieval of values by keys
- Using hash tables (built-in dict in Python).
- Using linked lists or binary trees for ordered or chained implementations
- Binary Tree
- Using nodes with pointers to left and right children.
- Using arrays/2D arrays for complete binary trees where children indices are calculated.