💻 Year 9 Computer Science

Advanced algorithms, complexity, OOP, data structures, networking, and computing ethics.

Advanced Algorithms

Sorting Algorithms

  • Bubble sort: repeatedly compare adjacent pairs and swap if out of order. Simple but inefficient for large datasets. Best case O(n) (already sorted), worst case O(n²).
  • Selection sort: find the minimum element and place it at the front; repeat for remaining elements. Always O(n²) — no best case improvement.
  • Insertion sort: build the sorted list one element at a time by inserting each element into its correct position. Best case O(n), worst case O(n²). Good for small or nearly-sorted data.
  • Merge sort: divide the list in half recursively until single elements, then merge sorted halves. Always O(n log n) — more efficient for large datasets. Uses extra memory.
  • Quick sort: choose a pivot; partition elements into less-than and greater-than the pivot; recurse. Average O(n log n), worst case O(n²) (bad pivot choice).

Searching Algorithms

  • Linear search: check each element in order. Works on unsorted data. O(n) worst case.
  • Binary search: requires sorted data. Compare middle element; if the target is less, search the left half; if greater, search the right half. Repeat. O(log n) — extremely efficient.
  • Trace through: list = [2, 5, 8, 12, 16, 23, 38, 56]. Search for 23. Mid = 12 (index 3). 23 > 12 → search right half [16, 23, 38, 56]. Mid = 38 (index 6). 23 < 38 → search left half [16, 23]. Mid = 16. 23 > 16 → search right [23]. Found.

Recursive Algorithms

  • Recursion: a function that calls itself. Must have: a base case (stopping condition) and a recursive case that makes progress towards the base case.
  • Factorial: factorial(n) = n × factorial(n−1); base case: factorial(1) = 1 (or factorial(0) = 1)
  • Each recursive call adds a new frame to the call stack. Too many levels without a base case → stack overflow.
def factorial(n): if n == 1: # base case return 1 return n * factorial(n - 1) # recursive case

Complexity & Efficiency

Big O Notation (Introduction)

  • Big O notation describes how the runtime (or memory) of an algorithm grows as the input size n increases
  • O(1): constant time — the same regardless of input size. Accessing an element in an array by index.
  • O(n): linear time — runtime grows proportionally with n. Linear search.
  • O(log n): logarithmic time — runtime grows as the log of n. Binary search. Very efficient for large n.
  • O(n²): quadratic time — runtime grows as n squared. Bubble/selection sort. Poor for large datasets.
  • O(n log n): typical of good sorting algorithms. Merge sort, quick sort (average).

Why Efficiency Matters

  • For n = 1,000,000: O(log n) ≈ 20 operations; O(n) = 1,000,000; O(n²) = 10¹²
  • Time complexity: how runtime scales with input size
  • Space complexity: how memory usage scales with input size
  • Trade-offs: merge sort is faster than insertion sort but uses more memory; hash tables give O(1) lookup but require more space and have occasional collisions

Object-Oriented Programming

Core Concepts

  • Class: a blueprint or template for creating objects. Defines attributes (data) and methods (functions).
  • Object: an instance of a class. Creating an object is called instantiation.
  • Attribute: a variable belonging to an object (e.g. a Dog object might have attributes: name, breed, age)
  • Method: a function belonging to a class (e.g. a Dog might have methods: bark(), eat(), fetch())
  • Constructor (__init__): a special method called when an object is created; initialises the object's attributes
class Dog: def __init__(self, name, breed): self.name = name self.breed = breed def bark(self): return f"{self.name} says: Woof!" my_dog = Dog("Buddy", "Labrador") print(my_dog.bark()) # Buddy says: Woof!

Four Pillars of OOP

  • Encapsulation: bundling data and methods together within a class; hiding internal implementation (private attributes use _ or __). The user of a class doesn't need to know how it works internally.
  • Inheritance: a child class inherits attributes and methods from a parent class and can extend or override them. Promotes code reuse. e.g. Dog and Cat both inherit from Animal.
  • Polymorphism: different classes can have methods with the same name that behave differently. e.g. Dog.speak() returns "Woof!", Cat.speak() returns "Meow!" — both called via the same interface.
  • Abstraction: hiding complex implementation details and showing only essential features. Users interact with a simple interface without knowing the underlying complexity.

Data Structures

Stacks

  • LIFO (Last In, First Out): the last item added is the first one removed — like a stack of plates
  • Operations: push (add to top), pop (remove from top), peek (look at top without removing)
  • Applications: undo operations in software, the call stack in recursion, browser back button, expression evaluation, bracket matching

Queues

  • FIFO (First In, First Out): the first item added is the first one removed — like a queue at a shop
  • Operations: enqueue (add to back), dequeue (remove from front)
  • Applications: printer queues, process scheduling in operating systems, BFS graph traversal
  • Variants: priority queue (items have priorities, higher priority is dequeued first), circular queue

Hash Tables

  • Key-value pairs: each value is stored at a location determined by a hash function applied to the key
  • Average O(1) lookup, insert, and delete — extremely fast
  • Hash function: takes a key and returns an index. e.g. hash("apple") = 2 → store value at index 2
  • Collision: when two different keys hash to the same index. Resolved by: chaining (each slot stores a linked list), open addressing (probe for the next empty slot)
  • Python dictionaries and sets are implemented as hash tables

Graphs

  • A collection of nodes (vertices) connected by edges. Can be: directed or undirected, weighted or unweighted.
  • Applications: social networks, road maps, the internet, recommendation systems
  • Breadth-First Search (BFS): explores all neighbours of a node before going deeper. Uses a queue. Finds the shortest path in unweighted graphs.
  • Depth-First Search (DFS): goes as deep as possible before backtracking. Uses a stack (or recursion). Good for detecting cycles, maze solving.

Networking in Depth

The TCP/IP Model

  • Four layers (bottom to top): Network Access / Internet / Transport / Application
  • Network Access layer: physical transmission of data (Ethernet, Wi-Fi). MAC addresses.
  • Internet layer: routing packets across networks. IP addresses. Routers operate here.
  • Transport layer: reliable or unreliable delivery. TCP (Transmission Control Protocol): reliable, ordered, error-checked delivery — used by HTTP, email. UDP (User Datagram Protocol): fast, unreliable — used by video streaming, VoIP, gaming.
  • Application layer: protocols used by applications: HTTP/HTTPS (web), SMTP/IMAP/POP3 (email), FTP (file transfer), DNS (domain name resolution), SSH (secure shell).

IP Addresses and DNS

  • IPv4: 32-bit address, written as 4 numbers 0–255 separated by dots (e.g. 192.168.1.1). ~4.3 billion unique addresses — now exhausted.
  • IPv6: 128-bit address, written in hexadecimal. ~340 undecillion unique addresses — solving the exhaustion problem.
  • DNS (Domain Name System): converts human-readable domain names (www.bbc.co.uk) to IP addresses. The "phone book of the internet". Recursive lookup through a hierarchy of DNS servers.
  • DHCP: dynamically assigns IP addresses to devices on a network so you don't have to configure them manually.

Network Security Protocols

  • TLS/SSL: encrypts data in transit. Websites using HTTPS use TLS. The padlock in the browser address bar.
  • Symmetric encryption: same key encrypts and decrypts. Fast but key distribution is a problem.
  • Asymmetric encryption (public-key cryptography): public key encrypts, private key decrypts. Used in HTTPS handshake, digital signatures.
  • Certificates: issued by Certificate Authorities (CAs) to verify that a website's public key genuinely belongs to that website.
  • Firewall: inspects network traffic and blocks packets that don't meet defined security rules. Can be hardware or software.

AI, Ethics & Society

Machine Learning Basics

  • Traditional programming: humans write rules → computer applies them to data → output
  • Machine learning: humans provide data and outputs → computer learns the rules → applies to new data
  • Supervised learning: training data is labelled (e.g. images labelled "cat" or "not cat"). The model learns to classify new images.
  • Unsupervised learning: training data is unlabelled. The model finds patterns itself (clustering — e.g. customer segmentation).
  • Neural networks: loosely inspired by the brain. Many layers of interconnected nodes; learns patterns through training on vast datasets.

Ethical Issues in Computing

  • Algorithmic bias: if training data reflects historical biases, AI systems will replicate them. Examples: facial recognition less accurate for darker skin tones; loan-approval algorithms discriminating against minorities; hiring algorithms penalising women's CVs.
  • Privacy and surveillance: large-scale collection of personal data by governments and corporations. GDPR (UK/EU data protection law): the right to access your data, the right to be forgotten, data minimisation.
  • Misinformation and deepfakes: AI-generated fake images, videos, and text are increasingly difficult to detect. Implications for elections, trust, and evidence.
  • Automation and employment: AI and robotics will automate many jobs. Benefits: efficiency, new job types. Risks: structural unemployment, widening inequality.
  • AI in criminal justice: predictive policing algorithms used in the US (COMPAS) have been shown to be racially biased. Decisions affecting people's liberty made by opaque systems.
  • Autonomous weapons: lethal autonomous weapons systems (LAWS) — should a machine ever be allowed to decide to kill someone? Campaigners call for a ban.

Digital Citizenship

  • Online responsibility: everything you post can be shared, screenshotted, and is potentially permanent. Consider: would you be comfortable with everyone you know seeing this?
  • Open source software: source code is freely available for anyone to use, modify, and distribute. Examples: Linux, Python, Firefox. Promotes transparency and collaboration.
  • Intellectual property: copyright protects creative works (code, music, writing, images). Licences (MIT, GPL, Creative Commons) define how others can use copyrighted material.
  • Environmental impact: data centres consume enormous amounts of energy. Training a large AI model can emit as much CO₂ as several transatlantic flights.