Question 7 of 7: Short Questions

Question 7: Short Questions (20 marks: 5 items, 4 marks each)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

1. Detecting a loop in a linked list — 4 marks

The standard technique is Floyd's cycle-detection ("tortoise and hare"): run two pointers from the head, one advancing one node per step and the other two nodes per step. If the list is acyclic, the fast pointer reaches NULL and the search ends with no loop found; if the list contains a loop, the fast pointer eventually laps the slow pointer and the two become equal at some node inside the loop, which proves a cycle exists. This runs in $O(n)$ time and $O(1)$ extra space, unlike a hash-set-of-visited-nodes approach which needs $O(n)$ space.

2. Hash table — 4 marks

A hash table stores key–value pairs by applying a hash function to the key to compute an array index (bucket), giving average-case $O(1)$ insert, lookup, and delete — dramatically faster than a linear or even sorted-array search. Because different keys can map to the same bucket (a collision), a collision-resolution scheme is required, most commonly chaining (each bucket holds a small linked list of entries) or open addressing (probing for the next free slot); a good hash function spreads keys uniformly so buckets stay short and the $O(1)$ average case actually holds.

3. NP-problems — 4 marks

"Polynomial" means a proposed solution can be verified as correct in time polynomial in the input size (e.g. checking that a given assignment satisfies a Boolean formula, or that a claimed Hamiltonian path really visits every vertex once) — this is the "P" of NP. "Non-deterministic" refers to the theoretical model of computation that could guess the right solution (e.g. try every branch of a search simultaneously) and then verify it in polynomial time; on a real (deterministic) computer, no polynomial-time algorithm is known for the NP-complete problems, even though checking a proposed answer is fast. NP is therefore the class of decision problems whose "yes" answers have polynomial-length certificates that can be checked in polynomial time.

4. Greedy algorithms — 4 marks

A greedy algorithm builds a solution incrementally by always making the choice that looks locally best at the current step — e.g. the cheapest available edge, the item with the best value-to-weight ratio — and never reconsidering that choice later. Greedy algorithms are simple and fast (typically $O(n\log n)$ from a sort plus a linear scan) but only produce a globally optimal solution for problems that have the right structure (a "matroid"-like exchange property, as in Kruskal's MST or activity-selection); applied to a problem lacking that structure (e.g. naive greedy for 0/1 knapsack) they can produce a solution far from optimal.

5. Space–time tradeoff: string search in a large ASCII document — 4 marks

At one extreme, a plain linear scan (e.g. naive or Boyer–Moore search) uses $O(1)$ extra space and $O(nm)$ or better time per query but re-scans the whole document every single search — fine for one-off searches, wasteful for many repeated searches of the same document. At the other extreme, pre-building an index over the document — a suffix array/tree, or a hash table/inverted index of substrings or words — costs $O(n)$ or more extra space and $O(n)$ (or $O(n\log n)$) build time up front, but then answers each subsequent search in time close to $O(m)$ (the length of the query), independent of document size. The right choice depends on how many searches will be run against the same document: a single search favours the low-memory linear scan, while a document searched repeatedly (e.g. a search engine's corpus) favours paying the one-time space cost of an index for much faster repeated queries.