Skip to main content

Prerequisite Diagnostic

Attempt before reading the new lessons. These questions check earlier material; knowing why Dijkstra fails or how SCCs work is not an entry requirement.

  1. Trace FIFO and LIFO removal orders after inserting A,B,C. Explain why a list's front deletion may be more expensive than a queue operation.
  2. State the three obligations of an invariant proof and give a strictly decreasing nonnegative measure for a loop over a finite worklist.
  3. A heap contains (5,A) and (2,A) after A's best score changes from 5 to 2. How could a separate best-score table identify the stale record?
  4. Compare O(n+m), O(n²), and O(nm) work when n is large and m=3n. State whether these bounds alone predict seconds.
  5. If a set has a,b,c, list all subsets containing a and excluding c. Explain how the count grows when there are k unconstrained elements.
  6. Explain why (0,1,5) and (0,1,2) can be distinct records even though two fields match. What information does an original-record index preserve?

Feedback and repair​

  1. FIFO A,B,C; LIFO C,B,A. Contiguous-list front deletion may shift later elements. Review queues, stacks and representation costs if unclear.
  2. Initialization, maintenance, and invariant plus exit condition imply the result. For a fixed worklist consumed once without new entries, the number of remaining items decreases to zero. A worklist proof also needs to bound newly added work when insertions are allowed; merely removing an item each iteration is insufficient if unlimited items are added.
  3. Compare popped score to the current best-score table and skip obsolete entries. Review Module 2's lazy priority-queue updates and retained-state accounting.
  4. Linear, quadratic, quadratic respectively in this substitution. Constants, operation definitions, input family and environment are still needed for time.
  5. {a}, {a,b}. k independent included/excluded choices give 2^k subsets.
  6. The last field can mean distinct cost or capacity and the records can identify different physical edges. An index refers back to the exact original record.

Repair each failed item, then explain a fresh example without viewing this key. Do not average away a missing skill. Previous module: Sorting, Searching & Fundamental Structures.