Computer Science Fundamentals and Algorithms
Domain 1 tests how well you can reason about computation: number representation, Boolean logic, algorithm design, and complexity. Questions often ask you to trace code or compare strategies rather than recite definitions. Define terms precisely, because distractors often swap related ideas.
Core rules
- Positional systems use powers of the base. Binary 101101₂ equals 32+8+4+1 = 45. In fixed-width two's complement, the leading bit has negative weight; an 8-bit signed range is -128 to 127.
- Boolean identities include De Morgan's laws: NOT(A AND B) = (NOT A) OR (NOT B). Gates implement these operations; XOR is true when inputs differ. A truth table enumerates all input combinations and checks small expressions.
- A correct algorithm must terminate, produce the right output, and use finite resources. Pseudocode should expose initialization, condition, and update.
- Big-O describes growth, not seconds: linear search O(n), binary search O(log n) only on sorted data, selection/insertion sort O(n²), merge sort O(n log n).
- Recursion needs a base case and progress toward it; each call consumes stack space.
Worked example
Search for 23 in the sorted list [3, 8, 12, 19, 23, 31, 44]. Use low=0, high=6. Mid=floor((0+6)/2)=3, value 19 < 23, so low=4. Mid=floor((4+6)/2)=5, value 31 > 23, so high=4. Mid=4, value 23; found after three comparisons. The sorted precondition is what makes discarding half valid.
Traps
Updating low to mid instead of mid+1 can loop forever. Binary search is not O(log n) on unsorted data. Two's complement is not sign-magnitude. Recursion without a shrinking subproblem overflows the stack. Big-O ignores constants but does not describe exact runtime. Verify the midpoint formula and the loop invariant.