Fundamentals of Computer Science and Algorithms
This domain tests how computers represent data, how logic is expressed, and what makes an algorithm a valid, finite problem-solving procedure. Expect conversion problems, truth-table reasoning, and pseudocode traces rather than broad essay answers.
Data representation
- Binary place values double from right to left; hexadecimal groups four bits, octal groups three.
- Two's complement represents signed integers: invert all bits and add 1 to negate. For n bits the range is -2^(n-1) through 2^(n-1)-1.
- Sign extension preserves value when widening a signed field: copy the sign bit into new high-order positions.
Boolean logic
- AND is true only when both inputs are true; OR is true when at least one is true; XOR is true when inputs differ.
- De Morgan's laws: NOT(A AND B) = (NOT A) OR (NOT B); NOT(A OR B) = (NOT A) AND (NOT B).
- A truth table for n variables has 2^n rows.
Algorithm properties
An algorithm must have defined inputs and outputs, definite steps, finite termination, and effective operations. Pseudocode traces should track every variable change in a table.
Worked example
Convert -5 to 8-bit two's complement, then add 3. Positive 5 is 00000101. Invert: 11111010. Add 1: 11111011, which is -5. Add 00000011: 11111011 + 00000011 = 11111110. The leading 1 means negative; invert and add 1 gives 00000010, so the result is -2. Checking in decimal: -5 + 3 = -2.
Traps that cost marks
- Forgetting that two's complement has one more negative value than positive value.
- Mixing up XOR with OR in truth tables.
- Claiming an algorithm is valid when a loop condition never becomes false.
- Sign-extending an unsigned value, which changes its meaning.
- Counting a hexadecimal digit as three bits instead of four.