Algorithms

Time & Space Complexity · Sorting · Searching · Trees · Graphs · Strings

Unit 1 · Fundamentals

Basics & Complexity

What algorithms are, data abstraction, and how to measure running time and memory.

▶ Algorithm Basics

Definition & characteristics (input, output, finiteness, effectiveness, correctness, generality).
Simple examples: max element, factorial, GCD, searching a key.

▶ Data Abstraction

Sets and Multisets as abstract data types.
Stacks and Queues: basic operations and use cases.

▶ Asymptotic Notation & Complexity

Big-O, Big-Ω, Big-Θ: upper, lower, and tight bounds.
Best, average, worst-case time complexity.
Space complexity: input size vs auxiliary memory.

▶ Algorithm Design Paradigms

Divide & Conquer: split, solve, combine (e.g. Merge Sort, Quick Sort).
Greedy: locally optimal choices (e.g. Prim, Kruskal, Dijkstra).
Dynamic Programming: optimal substructure & overlapping subproblems.

Order / Omega / Theta Time vs Space Complexity Analysis

Unit 2 · Sorting

Order the Data

Comparison-based and linear-time sorting, plus full complexity analysis.

▶ Basic Comparison Sorts

Bubble Sort – swap adjacent out-of-order pairs; O(n²) worst, O(n) best.
Selection Sort – repeatedly select minimum; O(n²) in all cases.
Insertion Sort – insert into sorted prefix; O(n²) worst, O(n) best.
Shell Sort – gap-based generalized insertion sort.

▶ O(n log n) Sorting

Merge Sort – divide, recursively sort, merge; O(n log n), extra O(n) space.
Quick Sort – partition around pivot; average O(n log n), worst O(n²).
Heap Sort – build heap, repeatedly extract max/min; O(n log n) worst.

▶ Linear-Time Sorting

Counting Sort – integer keys in limited range; O(n + k).
Bucket Sort – divide into buckets, sort each, concatenate.
Radix Sort – process digits (LSD/MSD) using stable inner sort.

▶ Complexity Comparison

Best / Average / Worst cases for each algorithm.
Stability and in-place behaviour.
When to choose which sorting algorithm.

Bubble Selection Insertion Merge Quick Heap Radix

Unit 3 · Searching & Tables

Search · Trees · Hashing

Searching in arrays, tree-based and hash-based dictionaries, and symbol tables.

▶ Array Searching

Linear Search – scan all elements, O(n).
Binary Search – sorted array requirement, O(log n) time.
Best / average / worst-case analysis.

▶ Search Trees

Binary Search Tree (BST): left < root < right.
BST operations: search, insert, delete.
Height effect: average O(log n), worst O(n) skewed.
Balanced Trees: motivation and advantages of height balancing.

▶ Hashing & Hash Tables

Hash functions: mapping keys to indices.
Collisions: inevitability and handling.
Collision resolution: chaining and open addressing techniques.
Load factor and its influence on performance.

▶ Symbol Tables

Abstract key–value dictionary for identifiers.
Implementations using arrays, search trees, or hash tables.
Trade-offs between search time, space, and update costs.

Linear vs Binary BST Balanced Trees Hashing Symbol Tables

Unit 4 · Graph Algorithms

MST & Shortest Paths

Graph concepts, traversal, topological sort, MST, and shortest-path algorithms.

▶ Graph Basics

Directed & Undirected graphs, weighted / unweighted.
Paths, cycles, DAGs, and spanning trees.
Representations: adjacency matrix vs adjacency list.

▶ Traversals & Topological Sort

BFS – level-order traversal using a queue.
DFS – depth-first traversal using recursion / stack.
Topological sorting for DAGs.

▶ Minimum Spanning Trees

Prim’s Algorithm – grow MST from a starting node.
Kruskal’s Algorithm – add smallest edges using Union–Find.

▶ Shortest Path Algorithms

Dijkstra – single source, non-negative weights.
Bellman–Ford – handles negative weights, detects negative cycles.
Floyd–Warshall – all-pairs shortest path via dynamic programming.

BFS DFS Topological Sort Prim Kruskal Dijkstra Bellman–Ford Floyd–Warshall

Unit 5 · Strings

Patterns & Matching

String sorting, tries, pattern matching algorithms, regex, and basic compression ideas.

▶ String Structures

String sort (lexicographic ordering).
Tries (prefix trees) for dictionary / prefix queries.

▶ Pattern Matching Algorithms

Naive string matching – O(n·m) worst case.
Rabin–Karp – rolling hash, average O(n + m).
KMP – prefix function / LPS, O(n + m).
Horspool – simplified Boyer–Moore with shift table.
Boyer–Moore – bad-character & good-suffix heuristics.

▶ Regex & Compression

Regular expressions for expressing string patterns.
Basic idea of data compression using symbol frequencies.

Naive Rabin–Karp KMP Horspool Boyer–Moore Regex Compression

Concise Definitions — Exam Quick Revision

Algorithm: A finite sequence of well-defined steps to solve a problem.
Time Complexity: Measure of how execution time grows with input size.
Space Complexity: Total memory used by an algorithm relative to input size.
Big-O: Upper bound of runtime (worst-case growth rate).
Big-Ω: Lower bound of runtime (best-case growth rate).
Big-Θ: Tight bound where upper and lower bounds are same.
Divide & Conquer: Break problem into subproblems, solve recursively, combine.
Greedy Algorithm: Chooses locally optimal solution at each step.
Dynamic Programming: Solves problems using optimal substructure + overlapping subproblems.
Sorting: Arranging data in a defined order (ascending/descending).
Stable Sort: Sorting that preserves order of equal elements.
Linear Search: Sequentially scans every element for a match.
Binary Search: Searches in sorted array by halving search space each step.
BST: Binary tree where left < root < right.
Balanced Tree: Tree that maintains height ≈ O(log n).
Hashing: Converts keys to array index using a hash function.
Collision: Two keys produce same hash index.
BFS: Graph traversal level by level using a queue.
DFS: Graph traversal deep-first using stack/recursion.
MST: Subgraph connecting all vertices with minimum total weight.
Topological Sort: Linear ordering of DAG vertices respecting edge direction.
Dijkstra: Finds shortest path from source in non-negative weighted graph.
Bellman-Ford: Finds shortest paths and detects negative cycles.
Floyd-Warshall: Computes all-pairs shortest paths using DP.
Rabin-Karp: String matching using hashing.
KMP: String matching using prefix table to skip comparisons.
Boyer-Moore: Pattern matching from right to left using skip heuristics.