This is the sequel to C Programming and Data Structures. The first course gave you the basic containers; this one asks how to keep them fast at scale, and how to design algorithms rather than just use them. Every database index, cache, scheduler and route planner you work with rests on the ideas below. This article revisits the five units of the JNTUK course.
Unit 1: Algorithm analysis and hashing
Measuring an algorithm
The cost of an algorithm is how its time or space grows with input size n.
| Notation | Meaning | Reads as |
|---|---|---|
| O(f) | Upper bound | “No worse than” |
| Ω(f) | Lower bound | “No better than” |
| Θ(f) | Tight bound | “Grows exactly like” |
Common growth rates, from best to worst: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!). Amortized analysis averages the cost over a sequence of operations: appending to a dynamic array is O(1) amortized even though an occasional resize costs O(n). Recurrences such as T(n) = 2T(n/2) + n solve to O(n log n) by the master theorem.
Hashing in depth
A hash table maps keys to array slots with a hash function. The load factor α = items / slots controls speed.
| Collision strategy | How | Trade-off |
|---|---|---|
| Separate chaining | Each slot holds a list | Simple; degrades gracefully as α grows |
| Linear probing | Try the next slot | Cache-friendly but forms clusters |
| Quadratic probing | Try slots at growing offsets | Reduces clustering |
| Double hashing | Second hash gives the step | Best spread, more computation |
| Rehashing | Grow the table and reinsert | Needed once α is high |
A good hash function spreads keys uniformly and is cheap to compute. Extendible hashing and linear hashing grow a table on disk without rebuilding it.
Today: Python
dict, JavaHashMap, Redis and Git’s object store are hash tables. Bloom filters, which answer “possibly present or definitely absent” in tiny memory, use several hash functions and appear in databases and caches.
Unit 2: Balanced search trees and priority queues
A plain binary search tree can degrade to a linked list (O(n)) if keys arrive in order. Balanced trees keep the height at O(log n).
| Tree | Balancing rule | Key operation |
|---|---|---|
| AVL tree | Heights of the two subtrees of any node differ by at most 1 | Rotations (LL, RR, LR, RL) after insert and delete |
| Red-black tree | Node colours obey rules, so the longest path is at most twice the shortest | Recolouring and rotations |
| Splay tree | Moves each accessed node to the root | Amortized O(log n); recently used items stay near the top |
| B-tree | Each node holds many keys; all leaves at the same depth | Split and merge nodes |
| B+ tree | Data only in leaves, leaves linked in order | Fast range scans |
A B-tree of order m has up to m children per node, so a tree with a billion keys can be only three or four levels deep. That matters because each level is one disk read.
Heaps and priority queues
A binary heap is a complete binary tree where every parent is at least as large as its children (max-heap) or no larger (min-heap). It is stored in an array: the children of index i are 2i + 1 and 2i + 2. Insert and delete-max are O(log n); building a heap from n items is O(n). Heap sort uses this for an O(n log n) in-place sort. Variants include binomial and Fibonacci heaps, which speed up merging and decrease-key.
Today: database indexes in MySQL (InnoDB), PostgreSQL and most file systems are B+ trees. The Linux scheduler and Java
TreeMapuse red-black trees, and priority queues drive job schedulers, timers and Dijkstra’s algorithm.
Unit 3: Divide and conquer, and greedy algorithms
Divide and conquer
Split the problem, solve the pieces recursively, combine the answers.
| Algorithm | Idea | Time |
|---|---|---|
| Merge sort | Sort halves, merge them | O(n log n) always |
| Quick sort | Partition around a pivot, sort each side | O(n log n) average, O(n²) worst |
| Binary search | Halve the search range | O(log n) |
| Strassen’s matrix multiplication | Seven sub-multiplications instead of eight | About O(n2.81) |
| Closest pair of points | Split by line, check the strip | O(n log n) |
Greedy method
A greedy algorithm makes the best-looking choice at each step and never reconsiders. It works when the problem has the greedy-choice property and optimal substructure.
| Problem | Greedy rule |
|---|---|
| Fractional knapsack | Take items by highest value per weight |
| Activity selection | Always pick the activity that finishes earliest |
| Huffman coding | Repeatedly merge the two least frequent symbols |
| Job sequencing with deadlines | Schedule highest-profit jobs in the latest free slot |
| Minimum spanning tree | Kruskal: shortest edge that does not form a cycle. Prim: grow from a vertex using the cheapest edge |
| Dijkstra’s shortest path | Settle the nearest unvisited vertex, relax its edges (non-negative weights only) |
Today: Huffman coding is the idea inside gzip and JPEG. Dijkstra, in variants, finds routes in OSPF routers and map apps. Merge sort ideas power external sorting in databases, and quicksort variants are in most language libraries.
Unit 4: Dynamic programming and backtracking
Dynamic programming (DP)
DP solves problems with overlapping subproblems and optimal substructure by storing each answer once (memoization, top-down) or building a table bottom-up. Fibonacci by plain recursion is exponential, with memoization it is O(n).
| Problem | Idea | Time |
|---|---|---|
| 0/1 knapsack | Table of best value for each item count and capacity | O(nW) |
| Longest common subsequence | Table over prefixes of two strings | O(mn) |
| Matrix-chain multiplication | Best way to parenthesize a product | O(n³) |
| Optimal binary search tree | Minimise expected search cost | O(n³) |
| Floyd-Warshall | All-pairs shortest paths | O(V³) |
| Bellman-Ford | Single-source shortest paths, allows negative edges | O(VE) |
| Travelling salesperson (Held-Karp) | DP over subsets | O(n² 2ⁿ) |
Backtracking and branch and bound
Backtracking builds a solution one choice at a time and abandons (“prunes”) a partial solution when it cannot work. Classic examples: N-queens, sum of subsets, graph colouring, Hamiltonian cycle. Branch and bound adds a bound on the best possible value of each branch and discards those that cannot beat the best solution found so far. It is used for 0/1 knapsack and travelling salesperson.
Today:
diffand Git use longest common subsequence. Spell-checkers use edit distance, a DP. Sudoku solvers and constraint solvers in schedulers and package managers backtrack. Viterbi decoding in speech recognition is DP over a graph.
Unit 5: Graph algorithms and NP-completeness
Graph traversal and structure
| Algorithm | Purpose | Time (adjacency list) |
|---|---|---|
| BFS | Shortest path in unweighted graphs, levels | O(V + E) |
| DFS | Cycle detection, connected components, topological order | O(V + E) |
| Topological sort | Order tasks so every dependency comes first (for DAGs) | O(V + E) |
| Strongly connected components | Groups where every vertex reaches every other | O(V + E) |
| Articulation points and bridges | Single points of failure in a network | O(V + E) |
| Max flow (Ford-Fulkerson) | Maximum throughput through a network | Depends on augmenting method |
P, NP and NP-complete
| Class | Meaning |
|---|---|
| P | Problems solvable in polynomial time |
| NP | Problems whose proposed answer can be checked in polynomial time |
| NP-complete | The hardest problems in NP: if one has a fast algorithm, all do |
| NP-hard | At least as hard as NP-complete, not necessarily in NP |
A problem is shown NP-complete by reduction: a known NP-complete problem (starting with SAT, from Cook’s theorem) is converted into it in polynomial time. Examples: 3-SAT, clique, vertex cover, Hamiltonian cycle, travelling salesperson (decision form), subset sum. Whether P = NP is the most famous open question in computer science. In practice, NP-hard problems are tackled with approximation algorithms, heuristics and solvers.
Today: topological sort is how
make, Terraform and package managers order work, and Kubernetes controllers and CI pipelines are DAGs. Network flow and bridges appear in capacity planning and in finding single points of failure. Many scheduling and bin-packing problems, including pod placement, are NP-hard, which is why schedulers use heuristics.
One-minute recap
| Unit | Key idea | You meet it in |
|---|---|---|
| 1. Analysis and hashing | Big-O, amortized cost, load factor, collision handling | Dictionaries, Redis, Bloom filters |
| 2. Balanced trees and heaps | AVL, red-black, B+ tree; heap in an array | Database indexes, schedulers, TreeMap |
| 3. Divide and conquer, greedy | Split and combine; locally best choices | Merge sort, Huffman, Dijkstra, MST |
| 4. DP and backtracking | Store subproblem answers; prune dead ends | diff, edit distance, solvers |
| 5. Graphs and NP | BFS, DFS, topological sort; P versus NP | make, Terraform, pod scheduling |
Next in Engineering Revisited: Digital Logic and Computer Organization.
Written by Claude, Anthropic’s AI assistant, as part of Engineering Revisited, a quick refresher of the B.Tech subjects one at a time.