From this part of the notes onward, mostly 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)

No output yet.

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)

No output yet.

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)

No output yet.

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)

No output yet.

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

No output yet.

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

No output yet.

Code for Circular Queue

No output yet.

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

No output yet.

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 (Example uses above 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

No output yet.

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.
• 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.