Revision

CT: The Master Encyclopedia (Revision & Exam Handbook)

TIP

Use this document for “Day Before Exam” revision. It focuses on high-density information and trap avoidance.

---

🚨 Exam Trap Alerts

1. The “Off-By-One” Loop

• Trap: While (i < Length(L)) vs While (i <= Length(L)).
• Fix: If accessing L[i] and 1-indexed, loop usually goes to Length(L). If iterating rest(L), loop until L is empty.

2. The “Variable Scope” Illusion

• Trap: Assuming a variable count inside a procedure retains value between calls.
• Fix: Local variables RESET every call. Only Global variables or Return values persist state.

3. The “List Copy” Mistake

• Trap: L1 = L2. modifying L1 logic.
• Fix: In pseudocode, often pass-by-value implies copy, but be careful with nested structures.

4. The “Early Return”

• Trap: Putting Return inside a loop without a conditional check.
• Result: Loop runs exactly ONCE and returns.

---

⚡ Cheat Tables

📝 List Operations Reference

Operation	Syntax	Returns	Notes
Head	first(L)	Element	Error if L is empty
Tail	rest(L)	List	Returns List even if 1 element left ([])
Init	init(L)	List	All except last
Last	last(L)	Element	Error if L is empty
Append	L ++ [X]	List	Adds to END
Prepend	[X] ++ L	List	Adds to START
Member	member(L, x)	Boolean	Linear Search O(N)

🔑 Dictionary Operations Reference

Operation	Syntax	Logic
Check Key	isKey(D, k)	MANDATORY before access!
Get Value	v = D[k]	Returns value associated with k
Set Value	D[k] = v	Overwrites if exists, Creates if new
Get Keys	keys(D)	Returns List of keys (Arbitrary order often)

🕸️ Graph Matrix Logic

Condition	Meaning (in Adjacency Matrix M)
M[i][j] == 1	Edge exists from i to j
M[i][j] == 0	No edge
M[i][j] == M[j][i]	Undirected Graph (Symmetric)
Sum(Row i)	Out-Degree of node i
Sum(Col j)	In-Degree of node j

---

🧠 Recursion Tracing Template

When verifying recursive code, use the Stack Trace Table:

Call Level	Input L	Checking Condition	Action	Return Value
1	[A, B, C]	Len==0? No	first=A	A + Sum([B, C])
2	[B, C]	Len==0? No	first=B	B + Sum([C])
3	[C]	Len==0? No	first=C	C + Sum([])
4	[]	Len==0? YES	Base Case	0
Unwind	-	-	-	A + B + C + 0

---