IB Computer Science SL flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

System life cycle stages

Analysis, design, development, and implementation/testing, followed by evaluation that feeds back into analysis. Each stage produces documentation used by the next stage.

Bits to values

With n bits you can represent 2^n distinct values. Unsigned integers therefore range from 0 to 2^n − 1, so 8 bits cover 0 to 255.

Two's complement range

For n bits, two's complement represents integers from −2^(n−1) to 2^(n−1) − 1. To negate a value, invert every bit then add 1.

Binary prefix sizes

One byte is 8 bits. A kibibyte is 2^10 bytes (1024 B), a mebibyte is 2^20 bytes, and a gibibyte is 2^30 bytes. Decimal prefixes use powers of 1000.

Hexadecimal to binary

Each hexadecimal digit corresponds to exactly four binary bits. Convert by replacing each hex digit with its 4-bit group, so 2F becomes 0010 1111.

XOR gate behaviour

The XOR gate outputs 1 only when its two inputs differ, and 0 when they are the same. It is used in parity checking and simple encryption.

De Morgan's laws

NOT(A AND B) equals NOT A OR NOT B, and NOT(A OR B) equals NOT A AND NOT B. They allow circuits to be rewritten using only one gate type.

NAND as universal gate

Any Boolean function can be built using only NAND gates, because NAND can produce NOT, AND and OR when wired appropriately. This simplifies chip manufacture.

LAN versus WAN

A LAN covers a small area under one organisation's control, such as a school. A WAN spans large distances and links separate networks, often using leased telecommunications lines.

Router versus switch

A router forwards packets between different networks using IP addresses. A switch forwards frames within one LAN using MAC addresses, sending each frame only to the target port.

Star topology trade-off

All nodes connect to a central switch or access point. A single cable failure affects one node, but failure of the central device disables the whole network.

Simplex and duplex modes

Simplex transmits in one direction only. Half-duplex allows both directions but not simultaneously. Full-duplex allows simultaneous transmission both ways, as in most modern Ethernet links.

Abstraction in computational thinking

Abstraction removes unnecessary detail so a problem can be modelled at a manageable level. A subway map is an abstraction: it keeps stations and connections but drops real distances.

Decomposition

Decomposition breaks a large problem into smaller sub-problems that can be solved independently. The sub-solutions are then combined into a complete solution.

Linear versus binary search

Linear search checks elements in order and works on unsorted data in O(n) time. Binary search halves the search space each step in O(log n) but requires sorted data.

Bubble sort behaviour

Bubble sort compares adjacent pairs and swaps them when out of order, repeating passes until no swaps occur. Worst-case complexity is O(n²) because of nested comparisons.

Merge sort complexity

Merge sort recursively splits the list in half, sorts each half, then merges them. It runs in O(n log n) time but requires additional memory for merging.

Stack versus queue

A stack is last-in-first-out: push and pop act at the same end. A queue is first-in-first-out: enqueue at the rear and dequeue from the front.

Linked list characteristics

A linked list stores each element in a node with a pointer to the next node. Insertion at a known position is O(1), but reaching the nth element is O(n).

Binary search tree property

In a binary search tree, every value in the left subtree is smaller than the node, and every value in the right subtree is larger, enabling ordered search and traversal.

Recursion base case

A recursive method needs a base case that returns without calling itself, plus a recursive case that reduces the problem. Without a base case the call stack overflows.

Nested loop iteration count

For nested loops, total iterations equal the product of the outer and inner iteration counts. Two loops each running n times perform n² iterations.

CPU fetch-decode-execute

The program counter's address goes to the MAR, the instruction returns to the MDR and IR, the control unit decodes it, then the ALU or memory unit executes it.

ALU and control unit roles

The arithmetic logic unit performs calculations and comparisons. The control unit fetches and decodes instructions and coordinates the other components by sending control signals.

Cache memory purpose

Cache is small, fast memory holding recently or frequently used instructions and data. It reduces average memory access time because most requests hit the cache.

RAM versus ROM

RAM is volatile and stores programs and data currently in use. ROM is non-volatile, retains contents without power, and typically holds the bootstrap loader.

Virtual memory and thrashing

Virtual memory pages inactive data to secondary storage to extend usable RAM. Thrashing is excessive paging that leaves little time for useful processing.

Polling versus interrupts

Polling repeatedly checks a device's status flag, consuming processor time. An interrupt pauses the current process, runs a service routine, then resumes execution.

Operating system functions

An operating system manages memory, schedules processes, controls devices through drivers, organises files, provides a user interface, and enforces access security.

Hypervisor role

A hypervisor creates and runs virtual machines, allocating hardware resources among them. Each virtual machine runs its own operating system independently of the host.

SSD versus HDD

Solid-state drives use flash memory with no moving parts, giving fast random access and low power use but higher cost per gigabyte. Hard disks offer cheaper large capacity but slower seeks.

Cloud service models

IaaS provides virtual hardware, PaaS provides a development platform, and SaaS provides ready applications. Control decreases and provider management increases from IaaS to SaaS.