Unit 5: Graphs, Hashing, Sorting and Searching

Graph traversal, hash tables and core algorithms

Learning Outcomes
  • Represent graphs with matrices and adjacency lists
  • Traverse graphs using BFS and DFS
  • Use hashing for average O(1) lookup
  • Apply standard sorting and searching algorithms

Graphs

A graph is a set of vertices and edges stored either as an adjacency matrix using O(V^2) space or as an adjacency list that is efficient for sparse graphs. BFS explores level by level using a queue, while DFS goes as deep as possible using recursion or a stack.

vector<int> adj[V]; adj[u].push_back(v); adj[v].push_back(u);

Hashing

A hash table maps a key to an index through a hash function, giving average O(1) insertion and lookup. Collisions, where two keys map to the same slot, are resolved by chaining or open addressing.

int hash(int key){ return key % TABLE_SIZE; }

Sorting and Searching

Binary search finds an element in O(log n) on sorted data, while merge sort and quick sort sort in O(n log n) and the simpler bubble and insertion sorts run in O(n^2).

int binarySearch(int a[], int n, int key){ int lo = 0, hi = n - 1; while (lo <= hi){ int mid = (lo + hi) / 2; if (a[mid] == key) return mid; if (a[mid] < key) lo = mid + 1; else hi = mid - 1; } return -1; }

Summary

This final unit covered graph representations and traversals, hashing for fast lookup, and the comparison of common sorting and searching algorithms by their time complexity.

Exercises

  • Represent a small graph using an adjacency list and perform BFS.
  • Implement DFS using recursion.
  • Design a hash function for strings and discuss collisions.
  • Implement binary search and state its time complexity.
← PreviousCourse HomeNext →