ALGORITHMS AND DATA STRUCTURES
Full Course Notes
Contents
1. Introduction to Algorithms and Data Structures
2. Algorithm Analysis and Complexity
– Big O, Big Omega, Big Theta
– Time vs. Space Complexity
3. Arrays and Strings
4. Linked Lists
– Singly, Doubly, Circular Linked Lists
5. Stacks and Queues
6. Recursion
7. Trees
– Binary Trees
– Binary Search Trees
– Balanced Trees (AVL)
– Tree Traversals
8. Heaps and Priority Queues
9. Hash Tables
10. Graphs
– Representation
– BFS and DFS
– Shortest Path Algorithms
11. Sorting Algorithms
– Bubble, Selection, Insertion, Merge, Quick, Heap Sort
12. Searching Algorithms
– Linear Search, Binary Search
13. Algorithm Design Paradigms
– Divide and Conquer
– Greedy Algorithms
– Dynamic Programming
14. Practice Project
1. Introduction to Algorithms and Data Structures
What is an Algorithm?
An algorithm is a finite, well-defined sequence of steps that takes some input and produces a desired
output, solving a specific problem. A good algorithm should be:
• Correct – it produces the right output for every valid input.
• Finite – it terminates after a finite number of steps.
• Unambiguous – each step is precisely and clearly defined.
• Efficient – it uses time and memory resources as economically as possible.
What is a Data Structure?
A data structure is a specific way of organizing, storing, and managing data so that it can be
accessed and modified efficiently. The choice of data structure directly affects the efficiency of the
algorithms that operate on it – there is no single "best" structure, only the structure best suited to a
given problem.
Data structures are broadly classified as:
• Linear structures – data elements are arranged sequentially (arrays, linked lists, stacks,
queues).
• Non-linear structures – data elements are arranged hierarchically or in networks (trees,
graphs).
• Primitive structures – basic types built into a language (int, float, char, boolean).
• Abstract Data Types (ADTs) – logical descriptions of data and operations (e.g. Stack, Queue,
List) independent of implementation.
Together, algorithms and data structures form the foundation of efficient software design – captured
in the classic formulation: Program = Algorithms + Data Structures.
2. Algorithm Analysis and Complexity
Why Analyze Algorithms?
Algorithm analysis lets us predict how an algorithm's resource usage (time and memory) grows as the
input size grows, independent of any specific hardware or programming language. This allows fair
comparison between different algorithms that solve the same problem.
Time Complexity vs. Space Complexity
• Time Complexity – how the running time of an algorithm grows with input size, n.
• Space Complexity – how much extra memory an algorithm requires as input size, n, grows.
Asymptotic Notations
• Big O (O) – describes the worst-case (upper bound) growth rate of an algorithm's running time.
• Big Omega (Ω) – describes the best-case (lower bound) growth rate.
• Big Theta (Θ) – describes a tight bound – when best and worst case grow at the same rate.
Common Time Complexities (fastest to slowest)
Notation Name Example
O(1) Constant Accessing an array element by index
O(log n) Logarithmic Binary search
O(n) Linear Traversing a list once
O(n log
Linearithmic Merge sort, heap sort
n)
O(n²) Quadratic Bubble sort, selection sort, insertion sort
O(2¹■) Exponential Naive recursive Fibonacci, subset generation
O(n!) Factorial Brute-force traveling salesman problem
3. Arrays and Strings
Arrays
An array is a collection of elements of the same type, stored in contiguous memory locations, and
accessed using an index. Arrays provide O(1) constant-time access to any element by index, since
the memory address can be computed directly, but inserting or deleting an element (other than at the
end) requires shifting elements, giving O(n) time.
Time
Operation Notes
Complexity
Direct memory address
Access by index O(1)
calculation
Must check each
Search (unsorted) O(n)
element
Search (sorted) O(log n) Binary search possible
Amortized, for dynamic
Insertion/Deletion (end) O(1)
arrays
Requires shifting
Insertion/Deletion (middle) O(n)
elements
Strings
A string is essentially an array of characters, and many array algorithms (searching, sorting,
reversing) apply directly to strings. Common string algorithms include pattern matching (e.g. the naive
method, KMP, and Rabin–Karp algorithms), palindrome checking, and string reversal.
4. Linked Lists
A linked list is a linear data structure in which elements (called nodes) are not stored in contiguous
memory. Instead, each node stores its data plus a reference (pointer) to the next node in the
sequence. Unlike arrays, linked lists do not require shifting elements to insert or delete, but they do
not support constant-time random access.
Types of Linked Lists
• Singly Linked List – each node points only to the next node; traversal is one-directional.
• Doubly Linked List – each node has pointers to both the next and previous nodes, allowing
traversal in both directions.
• Circular Linked List – the last node points back to the first node instead of to null, forming a
loop.
Example: Singly Linked List Node (Python)
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
class LinkedList:
def __init__(self):
[Link] = None
def insert_at_head(self, data):
new_node = Node(data)
new_node.next = [Link]
[Link] = new_node
Linked Lists vs. Arrays
Aspect Array Linked List
Scattered (linked via
Memory layout Contiguous
pointers)
Random access O(1) O(n)
Insertion/Deletion at
O(n) O(1)
start
Extra memory per Pointer storage
None
element required
5. Stacks and Queues
Stacks
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle – the last element
added is the first one removed. Core operations are:
• push(x) – add element x to the top of the stack – O(1)
• pop() – remove and return the top element – O(1)
• peek()/top() – view the top element without removing it – O(1)
Applications: undo/redo functionality, expression evaluation and syntax parsing, backtracking
algorithms, and function call management (the call stack).
Queues
A queue is a linear data structure that follows the FIFO (First In, First Out) principle – the first element
added is the first one removed. Core operations are:
• enqueue(x) – add element x to the back of the queue – O(1)
• dequeue() – remove and return the front element – O(1)
Variants include the circular queue, the double-ended queue (deque), and the priority queue (covered
under Heaps). Applications: task scheduling, print queues, and breadth-first search in graphs.
6. Recursion
Recursion is a technique in which a function solves a problem by calling itself on smaller
sub-problems. Every correct recursive function needs:
• Base case(s) – the simplest instance(s) of the problem, solved directly without further recursive
calls, which stop the recursion.
• Recursive case – the function calls itself with a smaller or simpler version of the original
problem, moving it closer to the base case.
Example: Factorial (Python)
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case
Recursion underlies many important algorithms, including tree and graph traversals,
divide-and-conquer algorithms (merge sort, quick sort), and backtracking algorithms. Every recursive
solution can also be rewritten iteratively using an explicit stack, and doing so can avoid the memory
overhead of the call stack for deep recursions.
7. Trees
Basic Terminology
• Root – the topmost node of the tree.
• Parent / Child – a node directly connected to another node below/above it.
• Leaf – a node with no children.
• Height – the length of the longest path from a node down to a leaf.
• Depth – the length of the path from the root down to a given node.
Binary Trees
A binary tree is a tree in which each node has at most two children, referred to as the left child and
the right child.
Binary Search Trees (BST)
A BST is a binary tree with an ordering property: for every node, all values in its left subtree are
smaller, and all values in its right subtree are larger. This ordering allows efficient search, insertion,
and deletion, all averaging O(log n) time for a reasonably balanced tree – but degrading to O(n) in the
worst case (e.g. inserting already-sorted data creates a tree that behaves like a linked list).
Balanced Trees (AVL Trees)
An AVL tree is a self-balancing BST in which the heights of the two child subtrees of any node differ
by at most one. Whenever an insertion or deletion violates this balance, the tree performs rotations to
restore it. This guarantees O(log n) time for search, insertion, and deletion in all cases, avoiding the
worst-case degradation of an ordinary BST.
Tree Traversals
• In-order (Left → Root → Right) – visits nodes of a BST in ascending sorted order.
• Pre-order (Root → Left → Right) – useful for copying/serializing a tree.
• Post-order (Left → Right → Root) – useful for safely deleting a tree.
• Level-order (Breadth-First) – visits nodes level by level, using a queue.
8. Heaps and Priority Queues
A heap is a specialized, complete binary tree that satisfies the heap property:
• Max-Heap – every parent node's value is greater than or equal to its children's values (the
maximum value is always at the root).
• Min-Heap – every parent node's value is less than or equal to its children's values (the minimum
value is always at the root).
Heaps are typically implemented using an array (no explicit pointers needed), and support insertion
and removal of the top element in O(log n) time, with O(1) access to the minimum/maximum. A
priority queue is an abstract data type where each element has an associated priority, and elements
are served in priority order rather than insertion order – heaps are the standard implementation for
priority queues. Applications include task scheduling, Dijkstra's shortest path algorithm, and heap
sort.
9. Hash Tables
A hash table (hash map) stores key-value pairs and uses a hash function to convert each key into
an index within an underlying array, allowing average-case O(1) insertion, deletion, and lookup –
dramatically faster than the O(n) search required in an unsorted array or list.
Collisions
A collision occurs when two different keys hash to the same index. Common resolution strategies
include:
• Chaining – each array slot holds a small list (or linked list) of all entries hashed to that index.
• Open Addressing – on a collision, the algorithm probes for the next available slot (e.g. linear
probing, quadratic probing, double hashing).
A good hash function distributes keys uniformly across the table to minimize collisions and keep
operations close to O(1) on average. Hash tables underpin the implementation of Python dictionaries
and sets, and are widely used for caching, database indexing, and duplicate detection.
10. Graphs
A graph G = (V, E) is a data structure consisting of a set of vertices (nodes), V, and a set of edges, E,
connecting pairs of vertices. Graphs can be:
• Directed (edges have direction) or Undirected (edges are bidirectional)
• Weighted (edges carry a cost/value) or Unweighted
• Cyclic (contains at least one cycle) or Acyclic (no cycles, e.g. a DAG)
Graph Representations
• Adjacency Matrix – a V × V matrix where cell (i, j) indicates an edge between vertex i and j.
Simple, O(1) edge lookup, but O(V²) space – wasteful for sparse graphs.
• Adjacency List – each vertex stores a list of its neighboring vertices. Space-efficient for sparse
graphs, O(V + E) total space.
Graph Traversal Algorithms
• Breadth-First Search (BFS) – explores a graph level by level using a queue; finds the shortest
path in an unweighted graph.
• Depth-First Search (DFS) – explores as far as possible along each branch before backtracking,
typically implemented using recursion or an explicit stack.
Shortest Path Algorithms
• Dijkstra's Algorithm – finds the shortest path from a source vertex to all other vertices in a
weighted graph with non-negative edge weights, using a priority queue – O((V + E) log V).
• Bellman-Ford Algorithm – finds shortest paths even with negative edge weights, and can
detect negative-weight cycles – O(V × E).
• Floyd–Warshall Algorithm – computes shortest paths between all pairs of vertices – O(V³).
11. Sorting Algorithms
Sorting algorithms arrange the elements of a list into a defined order (typically ascending). Different
sorting algorithms trade off simplicity, speed, memory usage, and stability (whether equal elements
retain their relative order).
Best Average Worst Spa
Algorithm
Case Case Case ce
Bubble Sort O(n) O(n²) O(n²) O(1)
Selection Sort O(n²) O(n²) O(n²) O(1)
Insertion Sort O(n) O(n²) O(n²) O(1)
O(n log O(n log O(n log
Merge Sort O(n)
n) n) n)
O(n log O(n log O(lo
Quick Sort O(n²)
n) n) g n)
O(n log O(n log O(n log
Heap Sort O(1)
n) n) n)
Bubble, Selection, and Insertion Sort
• Bubble Sort – repeatedly steps through the list, swapping adjacent elements that are in the
wrong order, until no swaps are needed.
• Selection Sort – repeatedly finds the minimum element from the unsorted portion and moves it
to the end of the sorted portion.
• Insertion Sort – builds the sorted list one element at a time, inserting each new element into its
correct position among the already-sorted elements. Efficient for small or nearly-sorted datasets.
Merge Sort (Divide and Conquer)
Merge sort recursively splits the list in half until each sub-list has one element, then merges the
sub-lists back together in sorted order. It guarantees O(n log n) performance in all cases and is
stable, but requires O(n) additional memory.
Quick Sort (Divide and Conquer)
Quick sort selects a "pivot" element and partitions the remaining elements into those less than and
those greater than the pivot, then recursively sorts each partition. It is typically faster in practice than
merge sort due to good cache performance and in-place partitioning, but its worst case (O(n²)) occurs
with a poorly chosen pivot on already-sorted data.
Heap Sort
Heap sort builds a max-heap from the input data, then repeatedly removes the maximum element
from the heap and places it at the end of the array, shrinking the heap each time. It guarantees O(n
log n) time and sorts in place, but is not stable.
12. Searching Algorithms
Linear Search
Linear search checks each element of a list in sequence until the target value is found or the list is
exhausted. It works on both sorted and unsorted data, but runs in O(n) time.
Binary Search
Binary search operates only on sorted data. It repeatedly compares the target value to the middle
element of the current search range: if equal, the search is done; if the target is smaller, the search
continues in the left half; if larger, in the right half. This halves the search space at each step, giving
O(log n) time complexity.
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # not found
13. Algorithm Design Paradigms
Divide and Conquer
Divide and conquer solves a problem by breaking it into smaller sub-problems of the same type,
solving each sub-problem recursively, and combining their solutions into a solution for the original
problem. Classic examples: merge sort, quick sort, and binary search.
Greedy Algorithms
A greedy algorithm builds up a solution piece by piece, at each step choosing the option that looks
best at that moment (a "locally optimal" choice), without reconsidering earlier choices. Greedy
algorithms are simple and fast, but only produce a globally optimal solution for problems that have the
greedy-choice property. Examples: Dijkstra's shortest path algorithm, Kruskal's and Prim's
algorithms for minimum spanning trees, and Huffman coding for data compression.
Dynamic Programming
Dynamic programming (DP) solves complex problems by breaking them into overlapping
sub-problems, solving each sub-problem only once, and storing its result (memoization or tabulation)
to avoid redundant recomputation. DP is applicable to problems exhibiting:
• Optimal substructure – an optimal solution to the problem can be constructed from optimal
solutions of its sub-problems.
• Overlapping sub-problems – the same sub-problems recur multiple times during a naive
recursive solution.
Classic DP problems include the Fibonacci sequence (computed efficiently in O(n) instead of
exponential time), the 0/1 Knapsack problem, the Longest Common Subsequence problem, and
shortest path problems such as Floyd–Warshall.
14. Practice Project
To consolidate the concepts covered in this course, implement a small project that combines multiple
data structures and algorithms, for example:
• Build a library/inventory management system using a hash table for fast lookup by ID and a
BST for browsing items in sorted order.
• Implement a pathfinding tool on a graph representing a road network, using BFS for
unweighted shortest paths and Dijkstra's algorithm for weighted routes.
• Build a task scheduler using a priority queue (min-heap) to always process the highest-priority
task next.
• Implement and benchmark several sorting algorithms on the same datasets, comparing their
actual running times against their theoretical time complexities.
For each project, document the data structures chosen, justify why they are appropriate for the
problem, and analyze the time and space complexity of the core operations implemented.