Exercise 3: Choosing a Representation for Frequent Edge-Existence Checks — Possible Solution ==================================================================================== THE ACCESS PATTERN ------------------------------ The system needs to check very frequently whether a specific pair of users is directly connected (an edge-existence check), but rarely needs to list all of a user's own connections (a neighbor-listing operation). APPLYING THIS CHAPTER'S OWN TRADEOFF TABLE ------------------------------ Per this chapter's own time/space tradeoff table: Check if edge (u,v) exists: O(1) for the matrix, O(degree(v)) for the list. List all neighbors of v: O(V) for the matrix, O(degree(v)) for the list. Since the dominant, frequent operation here is specifically edge existence checking - not neighbor listing - the ADJACENCY MATRIX is the better fit for this particular access pattern, despite this chapter's own general guidance that sparse graphs usually favor the list. WHY THIS IS THE RIGHT CHOICE DESPITE THE GRAPH BEING SPARSE ------------------------------ Per this chapter's own "when each representation actually wins" guidance, the matrix's O(1) edge lookup can outweigh its larger space cost specifically when that exact operation - checking if a specific edge exists - is needed very frequently, even for an otherwise sparse graph. This is exactly that situation: the system's own usage pattern, not the graph's overall density, is what should drive the representation choice here. The rarely-needed neighbor-listing operation being slower on the matrix (O(V) instead of O(degree(v))) matters far less, since it's used infrequently. WHY THIS WORKS AS AN ANSWER ------------------------------ The recommendation is derived directly from matching the system's own stated, dominant access pattern (frequent edge checks, rare neighbor listing) against this chapter's own operation-by-operation tradeoff table, explicitly noting that this overrides the general sparse-graph default rather than contradicting it without explanation.