BITSAT Computer Science Prep

BITSAT Pattern: 2-3 questions on logic gates, truth tables, gate combinations. Quick pattern recognition critical.

// Basic Gates Truth Tables
AND Gate (·):          OR Gate (+):          NOT Gate ('):
A B | Y                A B | Y               A | Y
0 0 | 0                0 0 | 0               0 | 1
0 1 | 0                0 1 | 1               1 | 0
1 0 | 0                1 0 | 1
1 1 | 1                1 1 | 1

XOR Gate (⊕):          XNOR Gate (⊙):        NAND Gate:
A B | Y                A B | Y               A B | Y
0 0 | 0                0 0 | 1               0 0 | 1
0 1 | 1                0 1 | 0               0 1 | 1
1 0 | 1                1 0 | 0               1 0 | 1
1 1 | 0                1 1 | 1               1 1 | 0

NOR Gate:
A B | Y
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 0

// Key Circuit Functions
Half Adder:
  Sum = A ⊕ B  (XOR)
  Carry = A·B  (AND)

Full Adder:
  Sum = A ⊕ B ⊕ Cin
  Cout = (A·B) + (B·Cin) + (A·Cin)

Multiplexer (2-to-1):
  Output = S·A + S'·B
  where S is selector, A,B are inputs

// Karnaugh Map Simplification
2-variable:
  1 1    = 1 (both 1s → A+B)
  0 0

Group adjacent 1s (powers of 2)
Larger groups = fewer variables in result

BITSAT Favorite: Simplify expressions using laws, recognize De Morgan's patterns, verify with truth tables.

// De Morgan's Laws (Critical!)
(A+B)' = A'·B'
(A·B)' = A' + B'

Example: (A+B+C)' = A'·B'·C'
Example: (A·B·C)' = A' + B' + C'

// Distributive Laws
A·(B+C) = A·B + A·C    (AND over OR)
A+(B·C) = (A+B)·(A+C)  (OR over AND)

// Absorption Laws
A + A·B = A
A·(A+B) = A

// Simplification Techniques
1. Apply De Morgan to break down complex expressions
2. Factor common terms: A·B + A·C = A·(B+C)
3. Use A + A' = 1, A·A' = 0
4. Eliminate double negation: (A')' = A

// Example Simplifications
F = A'·B + A·B = B·(A'+A) = B·1 = B
F = (A+B)·(A+B') = A + B·B' = A + 0 = A
F = (ABC)' = A' + B' + C'  (De Morgan)

// Consensus Theorem
A·B + A'·C + B·C = A·B + A'·C
(AB included, AC excluded, BC redundant)

// Duality Theorem
Swap AND↔OR, 0↔1, keep variables same
Original: A + A'·B = A + B
Dual: A·(A' + B) = A·B

BITSAT asks: Conversion between bases, BCD, floating point, character encoding.

// Quick Base Conversion
Decimal → Binary: Repeated divide by 2
37 dec = 100101 bin   (32+4+1)

Binary → Decimal: Sum of position values
100101 = 32 + 4 + 1 = 37

Hexadecimal: Base 16 (0-9, A-F where A=10...F=15)
3A7 hex = 3×16² + 10×16¹ + 7×16⁰ = 935 dec
Hex→Bin: Each hex digit = 4 bits (A=1010, F=1111)

Octal: Base 8 (0-7)
725 oct = 7×64 + 2×8 + 5 = 469 dec
Oct→Bin: Each octal digit = 3 bits

// BCD (Binary Coded Decimal)
Each decimal digit = 4-bit binary
37 dec = 0011 0111 BCD (not 100101 binary!)
0 = 0000, 1 = 0001, ... 9 = 1001
Use: Display systems, calculators

// Two's Complement (Signed Integers)
MSB = sign bit (0=positive, 1=negative)
4-bit examples:
  0101 = +5
  1011 = -5 (invert 0101→1010, add 1→1011)
Range: -2^(n-1) to 2^(n-1) - 1
8-bit: -128 to 127

// Gray Code (Reflected Binary)
Adjacent codes differ by 1 bit only
Used in error correction, rotary encoders
Binary to Gray: gray[i] = binary[i] ⊕ binary[i+1]

// Floating Point (IEEE 754)
32-bit: Sign(1) | Exponent(8) | Mantissa(23)
Value = (-1)^sign × 1.mantissa × 2^(exponent-127)
Special: Exponent 0 = zero/denormal, All 1s = infinity/NaN

// ASCII & Character Encoding
A-Z: 65-90 decimal (01000001-01011010 binary)
a-z: 97-122 decimal
0-9: 48-57 decimal (00110000-00111001)
Space: 32, Newline: 10
UTF-8: Variable length (1-4 bytes)

BITSAT Pattern: Basic CPU architecture, memory hierarchy, instruction execution, I/O.

// CPU Components
ALU (Arithmetic Logic Unit): Performs arithmetic & logic
Control Unit: Directs operations, fetch-decode-execute
Registers: Ultra-fast storage (bytes to hundreds)
  - Accumulator: Main calculation register
  - Program Counter (PC): Next instruction address
  - Instruction Register (IR): Current instruction
  - Stack Pointer (SP): Top of stack location

// Fetch-Decode-Execute Cycle
1. Fetch: IR ← memory[PC], PC ← PC + 1
2. Decode: Identify opcode and operands
3. Execute: Perform operation, update registers
4. Repeat

// Memory Hierarchy (Speed ↓, Cost ↑, Capacity ↑)
L1 Cache:  ~64 KB, ~4 cycles, on-chip
L2 Cache:  ~256 KB, ~10 cycles, on-chip
L3 Cache:  ~8 MB, ~40 cycles, shared
RAM:       ~8-16 GB, ~100 cycles, main
Disk:      ~500 GB+, ~1M cycles, secondary

Cache hit rate: percentage of accesses found in cache
Spatial locality: Access nearby memory
Temporal locality: Re-access same location

// Instruction Types
Arithmetic: ADD, SUB, MUL, DIV
Logic: AND, OR, XOR, NOT
Load/Store: LDR (load register), STR (store register)
Branch: JMP (jump), BEQ (branch if equal)
I/O: IN (input), OUT (output)

// Addressing Modes
Immediate: operand = constant  (MOV A, 5)
Direct: operand = memory address  (MOV A, [100])
Indirect: operand = value at memory pointed by address
Register: operand = register  (MOV A, B)

BITSAT asks: Basic data structures, algorithm tracing, simple coding patterns.

// Basic Data Structures
Array:
  Access: arr[i] = arr[0] + i × element_size
  Insert: O(n), Delete: O(n)
  Use: When index-based access needed

Stack (LIFO):
  Push: Add to top
  Pop: Remove from top
  Peek: View top without removing
  Use: Function call stack, bracket matching

Queue (FIFO):
  Enqueue: Add to rear
  Dequeue: Remove from front
  Use: Job scheduling, BFS

Linked List:
  Node structure: [data | next pointer]
  Insertion: Update pointers, O(1)
  Search: Traverse, O(n)

// Simple Algorithm Pattern: Linear Search
for i = 0 to n-1:
    if arr[i] == target:
        return i
return -1
Time: O(n)

// Bubble Sort Pattern (Swapping adjacent)
for i = 0 to n-1:
    for j = 0 to n-i-2:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])
Time: O(n²)

// Function Tracing
f(5) → f(4) + 5 → f(3) + 4 + 5 → ...
Most questions ask: final return value, number of calls

// Recursive vs Iterative
Recursive: Elegant but stack overhead, risk of stack overflow
Iterative: Efficient, more code
Example: Factorial
  Recursive: factorial(n) = n × factorial(n-1)
  Iterative: result = 1; for i=2 to n: result *= i

Important for BITSAT: Parity bits, checksums, Hamming codes basics.

// Parity Bits (Simple Error Detection)
Even Parity: Add bit so total 1s = even
  Data: 1011 → Add 1 → 11011 (four 1s = even)
Odd Parity: Add bit so total 1s = odd
  Data: 1011 → Add 0 → 01011 (three 1s = odd)

Can detect: Single bit error
Cannot detect: Multiple bit errors, pattern like 11→11

// Checksum (Simple Error Detection)
Sum all data bytes, keep only last 8 bits
Send: Data + Checksum
Receive: Recalculate checksum, compare
Detects most single errors, not all patterns

// Hamming Code (Single Error Correction!)
Parity bits at positions 2^k (1, 2, 4, 8, ...)
Each covers specific bit positions:
  P₁ (position 1): covers odd positions (1,3,5,7,...)
  P₂ (position 2): covers positions 2-3,6-7,10-11,...
  P₄ (position 4): covers positions 4-7,12-15,...

For 7-bit data + 3 parity = 10-bit code
Syndrome calculation reveals error position

// CRC (Cyclic Redundancy Check)
Polynomial division using XOR (no borrow)
Good error detection for burst errors
Used in networks, storage

// Error Correcting vs Detecting
Single Error Detection: 1 parity bit needed
Single Error Correction: log₂(n) parity bits needed
Double Error Correction: More parity bits needed

BITSAT arithmetic questions: Operations in different bases, overflow, underflow.

// Addition in Different Bases
Binary Addition (Base 2):
  1010 + 1011 = 10101
  0+0=0, 0+1=1, 1+1=10 (carry 1), 1+1+1=11

Hexadecimal Addition (Base 16):
  2A + 3F = 69
  A(10) + F(15) = 19 = 13 in hex, write 3 carry 1
  2 + 3 + 1 = 6

// Subtraction in Different Bases
Binary (using two's complement):
  0101 - 0011 = 0101 + 1101 = 10010, ignore overflow = 0010

// Multiplication Patterns
Binary: Same as decimal (0×anything=0, 1×x=x)
Hex: Can convert to binary, multiply, convert back

// Overflow & Underflow
Overflow: Result too large for representation
  8-bit unsigned: max 255, adding 200+100 overflows
Underflow: Result too small (in floating point)
  2^-149 smallest positive in 32-bit float

// Complement Operations
One's Complement: Flip all bits
  +5: 00000101
  -5: 11111010 (one's complement)
  Problem: Two representations of zero (00000000, 11111111)

Two's Complement: Flip all bits + add 1
  +5: 00000101
  -5: 11111011 (two's complement)
  Single zero, wider range

BITSAT includes: OSI model basics, TCP/IP, packet structure, simple protocols.

// OSI Model (7 Layers)
Layer 7: Application (HTTP, FTP, SMTP, DNS)
Layer 6: Presentation (Encryption, compression)
Layer 5: Session (Connection management)
Layer 4: Transport (TCP, UDP) - End-to-end
Layer 3: Network (IP, Routing) - Logical addresses
Layer 2: Data Link (Ethernet, MAC) - Physical addressing
Layer 1: Physical (Cables, signals)

Remember: "All People Seem To Need Data Processing"

// TCP vs UDP
TCP (Transmission Control Protocol):
  - Connection-oriented (handshake)
  - Reliable, ordered delivery
  - Slower due to error checking
  - Use: Email, Web, File transfer

UDP (User Datagram Protocol):
  - Connectionless
  - Fast but unreliable
  - Minimal overhead
  - Use: Video streaming, VoIP, Games

// IP Addressing
IPv4: 4 octets, 32 bits (xxx.xxx.xxx.xxx)
  Example: 192.168.1.1
  Classes: A (0-127), B (128-191), C (192-223)
  Private: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16

IPv6: 128 bits, colon-separated hex
  Example: 2001:0db8::8a2e:0370:7334

// Subnet Mask
Identifies network vs host portion
255.255.255.0 = first 24 bits network
Network: AND IP with subnet mask
Host: AND IP with NOT(subnet mask)

// Basic Packet Structure
Header:
  - Source IP (32 bits)
  - Destination IP (32 bits)
  - Protocol (TCP=6, UDP=17)
  - TTL (Time To Live, decrements at each hop)
  - Checksum (error detection)
Data: Actual payload
Footer: CRC for error detection

// DNS (Domain Name System)
Translates domain → IP address
DNS record types: A (IPv4), AAAA (IPv6), MX (mail)
Query: Client → Recursive resolver → Root → TLD → Authoritative

Quick lookup for exam day:

// Frequently Tested Facts

ASCII Values:
  'A' = 65, 'Z' = 90
  'a' = 97, 'z' = 122
  '0' = 48, '9' = 57
  Space = 32, Newline = 10

Powers of 2:
  2^8 = 256, 2^10 = 1024 (1K)
  2^16 = 65536, 2^20 = 1048576 (1M)
  2^24 = 16777216, 2^32 = 4294967296

Gray Code Pattern:
  Binary to Gray: g[i] = b[i] XOR b[i+1]
  First digit same, then XOR adjacent bits

Byte Ordering:
  Big Endian: MSB first (network byte order)
  Little Endian: LSB first (Intel processors)
  0x12345678 as bytes:
    Big: 12 34 56 78
    Little: 78 56 34 12

Boolean XOR Truth:
  0 XOR 0 = 0
  0 XOR 1 = 1
  1 XOR 0 = 1
  1 XOR 1 = 0
  Same = 0, Different = 1

Cache Line Size: Typically 64 bytes
Page Size: Typically 4 KB = 4096 bytes

Common Gate Equivalences:
  NAND = NOT(AND) = A' + B'
  NOR = NOT(OR) = A' · B'
  XOR = (A · B') + (A' · B) = A ⊕ B
  XNOR = (A · B) + (A' · B') = A ⊙ B