Hashing, graphs and sorting are among the most exam-relevant data-structure topics. They connect searching, indexing, networks, scheduling, routing and optimization. PSC questions commonly test collision handling, graph representation, BFS/DFS, shortest path, MST and sorting complexity.
Engineering Definitions
Hashing
Standard definition: A technique that maps keys to table indices using a hash function for fast lookup.
Exam meaning: Key लाई hash function बाट table index मा map गर्ने search technique।
Collision
Standard definition: A situation where two different keys map to the same hash table index.
Exam meaning: दुई key एउटै hash index मा जानु।
Graph
Standard definition: A non-linear structure consisting of vertices and edges.
Exam meaning: Vertices र edges बाट बनेको relationship structure।
Digraph
Standard definition: A directed graph where edges have direction.
Exam meaning: Direction भएको edges सहितको graph।
Sorting
Standard definition: Arranging records/elements in a specified order according to key.
Exam meaning: Elements लाई key अनुसार ascending/descending order मा राख्ने process।
Concept Teaching
Hashing targets average O(1) access but depends on good distribution and collision strategy. Graphs model relationships such as roads, networks and dependencies. Sorting organizes data and is often a prerequisite for searching, merging and optimization.
Hashing and Collision Resolution
A hash table is only good if collisions are managed.
- Hash function should distribute keys uniformly.
- Load factor = number of stored keys / table size.
- Separate chaining stores collided keys in linked lists/buckets.
- Open addressing searches alternative slots.
- Linear probing can cause primary clustering.
- Quadratic probing reduces primary clustering but has limitations.
- Double hashing uses second hash for probe step.
Graph Representation
Representation affects memory and traversal cost.
| Representation | Space | Best for |
|---|---|---|
| Adjacency matrix | O(V^2) | Dense graph and O(1) edge check |
| Adjacency list | O(V+E) | Sparse graph and traversal |
| Edge list | O(E) | Algorithms like Kruskal |
Graph Traversal
BFS and DFS are foundational.
- BFS uses queue and visits level by level.
- DFS uses stack or recursion and explores depth first.
- BFS gives shortest path in unweighted graph.
- DFS helps cycle detection, topological sort and connected components.
- Visited set prevents infinite traversal in cyclic graph.
Shortest Path and MST
Know the condition and purpose of each algorithm.
| Algorithm | Problem | Key condition |
|---|---|---|
| Dijkstra | Single-source shortest path | Nonnegative edge weights |
| Bellman-Ford | Shortest path with negative edges | Can detect negative cycle |
| Floyd-Warshall | All-pairs shortest path | Dynamic programming |
| Kruskal | Minimum spanning tree | Sort edges, use union-find |
| Prim | Minimum spanning tree | Grow tree from start vertex |
Sorting Algorithms
Sorting questions often compare time, stability and in-place property.
| Sort | Average time | Key point |
|---|---|---|
| Bubble | O(n^2) | Simple, stable, poor performance |
| Insertion | O(n^2) | Good for nearly sorted small data |
| Selection | O(n^2) | Few swaps, not stable generally |
| Merge | O(n log n) | Stable, needs extra memory |
| Quick | O(n log n) | Fast average, worst O(n^2) |
| Heap | O(n log n) | In-place, not stable generally |
Engineering Mechanism
- Hashing computes index from key.
- Collision strategy finds storage/search location.
- Graph algorithms choose representation and traversal method.
- BFS/DFS maintain frontier and visited set.
- Shortest path relaxes edges to improve distance estimates.
- Sorting repeatedly compares, partitions, merges or heapifies elements.
Diagrams / Models To Draw
- Draw hash table with chaining and open addressing.
- Draw graph adjacency matrix/list.
- Draw BFS queue levels and DFS recursion tree.
- Draw Dijkstra relaxation table.
- Draw quicksort partition and merge sort split/merge.
Formulas, Algorithms and Code Patterns
- Load factor alpha = n/m.
- Adjacency matrix space = O(V^2).
- Adjacency list space = O(V+E).
- BFS/DFS time = O(V+E) with adjacency list.
- Comparison sorting lower bound = Omega(n log n).
- Hash table average search = O(1), worst = O(n).
| Topic | Core idea | Exam trap |
|---|---|---|
| Hashing | Index by hash function | Collision handling required |
| BFS | Queue level traversal | Unweighted shortest path |
| DFS | Stack/recursion depth traversal | Cycle/topological applications |
| Dijkstra | Greedy shortest path | No negative weights |
| MST | Connect all vertices minimum total weight | For undirected connected graph |
| Stable sort | Preserves equal-key order | Not all O(n log n) sorts are stable |
Exam Point
- State graph representation before complexity.
- BFS uses queue; DFS uses stack/recursion.
- Dijkstra fails with negative edge weights.
- Kruskal needs cycle detection/union-find.
- Sorting comparison should include time, space, stability and in-place property.
- Hashing average O(1) depends on load factor and hash quality.
Worked Example
In BFS from source S, enqueue S and mark visited. Dequeue a vertex, enqueue all unvisited neighbors, and continue. The first time a vertex is discovered in an unweighted graph, the BFS level gives shortest edge-count distance from S.
Subjective Answer Pattern
- Define hashing, graph and sorting.
- Explain hash collision resolution.
- Compare graph representations.
- Describe BFS and DFS.
- Discuss shortest path/MST algorithms.
- Compare sorting algorithms with complexity and stability.
Common Engineering Mistakes
- Forgetting collision handling in hashing.
- Using adjacency matrix complexity for adjacency list traversal.
- Saying DFS gives shortest path in unweighted graph.
- Using Dijkstra with negative weights.
- Confusing MST with shortest path tree.
- Ignoring worst case of quicksort.
MCQ Revision
- What is load factor?
- Which collision method uses linked buckets?
- BFS uses which data structure?
- DFS uses which data structure?
- Dijkstra works with negative weights: true or false?
- Which sort is stable and O(n log n)?
Final Summary
- Hashing provides fast average search with collision management.
- Graphs model relationships using vertices and edges.
- BFS and DFS are core traversal algorithms.
- Shortest path and MST solve different graph problems.
- Sorting algorithms differ by time, space, stability and worst-case behavior.