Computer Science Reference Sheet

1. Computer Science Fundamentals

Common units

2. Number Systems and Data Representation

Place-value rule

For a number written in base \(b\), each digit is multiplied by a power of \(b\) according to its position.

Example:
(1011)₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰
        = 8 + 0 + 2 + 1
        = (11)₁₀

Useful conversions

Binary addition rules

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10  (write 0, carry 1)
1 + 1 + 1 = 11  (write 1, carry 1)

Two's complement

Two's complement is commonly used to represent signed integers in binary. For an \(n\)-bit value, its signed range is \(-2^{n-1}\) to \(2^{n-1}-1\).

For example, an 8-bit two's-complement integer ranges from −128 to 127.

3. Programming Fundamentals

Common data types

• Integer: Whole numbers.
• Float / real: Approximate or floating-point numbers in many languages.
• Boolean: True or false.
• String: Text.
• Character: A character value in languages that provide this type.

Control structures

Sequence: instructions run in order.

Selection:
if condition:
    do one action
else:
    do another action

Iteration:
repeat an action while a condition is true.

4. Algorithms and Complexity

An algorithm is a finite, well-defined sequence of steps for solving a problem or performing a computation.

Core properties

• Clearly specified steps.
• Defined inputs and outputs where appropriate.
• Effective operations.
• Termination for algorithms intended to finish.

Common Big-O growth rates

Searching and sorting

• Linear search: Checks items one by one; worst-case time O(n).
• Binary search: Repeatedly halves a sorted search range; time O(log n).
• Merge sort: A divide-and-conquer sorting algorithm with O(n log n) time in its standard form.
• Bubble sort: Repeatedly swaps adjacent out-of-order elements; typical implementation has O(n²) worst-case time.

5. Data Structures

LIFO: Last In, First Out. FIFO: First In, First Out.

Typical operation costs

These costs assume typical implementations and conditions; they are not guarantees for every implementation.

6. Databases and SQL

• Database: An organised collection of data.
• DBMS: Software used to create, manage, query, and protect databases.
• Primary key: Uniquely identifies each row in a table.
• Foreign key: References a key in another or the same table to represent a relationship.
• Normalization: Organises relational data to reduce unwanted redundancy and update anomalies.
• Transaction: A logical unit of database work.

Common SQL commands

Example query

SELECT name, marks
FROM students
WHERE marks >= 80
ORDER BY marks DESC;

Useful aggregate functions

COUNT(), SUM(), AVG(), MIN(), and MAX().

ACID transactions

• Atomicity: All-or-nothing transaction behaviour.
• Consistency: Transactions preserve defined database rules.
• Isolation: Concurrent transactions are controlled according to the chosen isolation level.
• Durability: Committed changes persist according to the system's guarantees.

7. Computer Networks

Network types

• PAN: Personal Area Network.
• LAN: Local Area Network.
• MAN: Metropolitan Area Network.
• WAN: Wide Area Network.

Devices

Common protocols

Performance terms

• Bandwidth: A link's capacity to carry data.
• Throughput: The actual rate of successful data transfer.
• Latency: Delay in communication.
• Packet loss: Packets that fail to reach their destination.

8. Operating Systems

• Kernel: Core OS component that manages fundamental system operations.
• Process: A running instance of a program.
• Thread: A sequence of execution within a process.
• Scheduler: Selects which ready process or thread runs next.
• Virtual memory: Provides process address spaces and supports flexible memory management.
• File system: Defines how files and directories are organised and stored.
• Device driver: Software that enables communication between the OS and hardware.
• System call: A defined interface for requesting an operating-system service.

Process states

New → Ready → Running → Terminated
             ^      |
             |      v
             └── Waiting

Scheduling algorithms

• FCFS: First Come, First Served.
• SJF: Shortest Job First.
• Priority scheduling: Uses assigned priorities.
• Round Robin: Shares CPU time using time slices.

Deadlock conditions

1. Mutual exclusion.
2. Hold and wait.
3. No preemption.
4. Circular wait.

9. Cybersecurity and Digital Safety

The CIA triad

• Confidentiality: Prevents unauthorized disclosure.
• Integrity: Protects against unauthorized or improper changes.
• Availability: Keeps systems and information accessible to authorized users.

Essential terms

Good security habits

• Use unique passwords and a reputable password manager.
• Enable multifactor authentication.
• Install security updates from trusted sources.
• Verify unexpected requests through an independent, trusted channel.
• Keep protected backups of important information.
• Grant applications only the permissions they need.

10. Artificial Intelligence Fundamentals

Key terms

Learning approaches

• Supervised learning: Learns from labelled examples.
• Unsupervised learning: Finds patterns without target labels for every example.
• Reinforcement learning: Learns action strategies from reward signals.

Common evaluation metrics

• Accuracy: Correct predictions divided by all predictions.
• Precision: True positives divided by predicted positives.
• Recall: True positives divided by actual positives.
• Mean squared error: Average squared difference between predicted and actual values.

11. Quick Revision Checklist

Use this list to check which concepts you can already explain.