IB Computer Science HL Topics
Contents
Paid resources available online here.
Topic 5 Abstract Data Structures
Learning Aim:
In this topic you will begin to learn about common data structures and be able to then describe the characteristics of arrays, stacks, queues, linked lists, and binary trees while also explaining the most common data processing operations on each of the data structures including addition, deletion and retrieval of data, traversal, searching for a given data, and sorting of data into some order.
What the syllabus says you need to know for this unit
5.1 Abstract Data Structures (HL only)
| Thinking recursively 5.1.1 Identify a situation that requires the use of recursive thinking 5.1.2 Identify recursive thinking in a specified problem solution 5.1.3 Trace a recursive algorithm to express a solution to a problem Abstract data structures 15.1.4 Describe the characteristics of a two-dimensional array 5.1.5 Construct algorithms using two-dimensional arrays 5.1.6 Describe the characteristics and applications of a stack 5.1.7 Construct algorithms using the access methods of a stack 5.1.8 Describe the characteristics and applications of a queue 5.1.9 Construct algorithms using the access methods of a queue 5.1.10 Explain the use of arrays as static stacks and queues Linked lists 5.1.11 Describe the features and characteristics of a dynamic data structure 5.1.12 Describe how linked lists operate logically 5.1.13 Sketch linked lists (single, double, and circular) Trees 5.1.14 Describe how trees operate logically (both binary and non-binary) 5.1.15 Define the terms: parent, left-child, right-child, subtree, root, and leaf 5.1.16 State the result of inorder, postorder, and preorder tree traversal 5.1.17 Sketch binary trees Applications 5.1.18 Define the term dynamic data structure 5.1.19 Compare the use of static and dynamic data structures 5.1.20 Suggest a suitable structure for a given situation |
What Are Abstract Data Structures?
Abstract Data Structures (ADS) are ways of organising and storing data so that it can be accessed and modified efficiently. They are called “abstract” because they focus on the operations that can be performed, rather than how they are implemented.
Key Abstract Data Structures in IB Computer Science
- Two-Dimensional Arrays: Grids of data, useful for representing tables, matrices, or game boards. Each element is accessed by two indices (row and column).
- Stacks: Follow the Last-In, First-Out (LIFO) principle. The most recently added item is the first to be removed. Used in undo features, backtracking, and recursion.
- Queues: Follow the First-In, First-Out (FIFO) principle. The first item added is the first to be removed. Used in print queues, task scheduling, and simulations.
- Linked Lists: Dynamic structures where each element (node) contains data and a reference (pointer) to the next node. Can be single, double, or circular.
- Trees: Hierarchical structures with nodes connected in parent-child relationships. Binary trees have at most two children per node. Trees are used in file systems, databases, and searching algorithms.
- Recursion: A method where a function calls itself to solve a problem. Commonly used with stacks and trees.
Static vs Dynamic Data Structures
- Static: Fixed size, determined at creation (e.g., arrays). Efficient for known, unchanging data sizes.
- Dynamic: Size can change during execution (e.g., linked lists). Efficient for unpredictable or changing data sizes.
Applications
- Stacks: Undo/redo in software, parsing expressions, backtracking algorithms
- Queues: Print queues, CPU scheduling, breadth-first search in graphs
- Linked Lists: Dynamic memory allocation, implementation of stacks and queues
- Trees: File systems, databases, decision-making processes
Glossary of Key Terms
| Term | Definition |
|---|---|
| Abstract Data Structure (ADS) | A way of organising and storing data that focuses on operations rather than implementation |
| Array | A collection of elements identified by index or key |
| Two-Dimensional Array | An array of arrays, accessed by two indices (row and column) |
| Stack | Data structure following Last-In, First-Out (LIFO) principle |
| Queue | Data structure following First-In, First-Out (FIFO) principle |
| Push | Adding an element to the top of a stack |
| Pop | Removing the top element from a stack |
| Enqueue | Adding an element to the end of a queue |
| Dequeue | Removing the element at the front of a queue |
| Linked List | A dynamic data structure where each node points to the next |
| Node | An element of a linked list or tree, containing data and references to other nodes |
| Pointer | A reference to another location in memory |
| Tree | Hierarchical data structure with nodes in parent-child relationships |
| Binary Tree | A tree where each node has at most two children |
| Parent | A node with one or more child nodes |
| Left-child | The left child node of a parent in a binary tree |
| Right-child | The right child node of a parent in a binary tree |
| Root | The topmost node in a tree |
| Leaf | A node with no children |
| Subtree | A tree formed by a node and its descendants |
| Traversal | The process of visiting all nodes in a tree (inorder, preorder, postorder) |
| Dynamic Data Structure | A structure whose size can change during execution |
| Static Data Structure | A structure whose size is fixed at creation |
| Recursion | A method where a function calls itself |
Topic 6 Resource Management
Learning Aim:
In this topic, you will begin to learn about how operating systems work in more detail including how they manage resources when dealing with processes/programs running on the system.
What the syllabus says you need to know for this unit
6.1 Resource Management
| 6.1.1 – Identify the resources that need to be managed within a computer system. Resources include primary memory, secondary storage, processor speed, bandwidth, screen resolution, disk storage, sound processor, graphics processor, cache, and network connectivity. 6.1.2 – Evaluate the resources available in a variety of computer systems. These should include mainframes, servers, PCs, sub-laptops, as well as personal digital devices such as cell phones, PDAs and digital cameras. Develop an appreciation of the issues linked to resource availability with continued developments in computer systems. 6.1.3 – Identify the limitations of a range of resources in a specified computer system. Notes: For example, single-processor computers may not be able to render 3D graphics effectively. 6.1.4 – Describe the possible problems resulting from the limitations in the resources in a computer system. Notes: For example, user time is wasted if the primary memory is too small or the processor speed is inadequate. Multi-access and multiprogramming environments should be considered as well as single-user systems. |
6.2 Role of the OS
| 6.1.5 – Explain the role of the operating system in terms of managing memory, peripherals and hardware interfaces. Includes concepts such as allocating storage and keeping track of programs in memory, swapping programs via time-slicing, priority etc. 6.1.7 – Outline OS resource management techniques: scheduling, policies, multitasking, virtual memory, paging, interrupt, and polling. Technical details as to how these are carried out will not be required, but it is expected that students will be familiar with these techniques and understand when and why they are used. 6.1.8 – Discuss the advantages of producing a dedicated operating system for a device. These are related to size, speed and customization. As an example, using a dedicated operating system for a cell phone rather than using a pre-existing operating system. S/E Issue of proprietary software. 6.1.9 – Outline how an operating system hides the complexity of the hardware from users and applications. Students should be aware of a range of examples where operating systems virtualize real devices, such as drive letters, virtual memory, input devices, and the Java virtual machine. INT Issue of localization causing compatibility problems between systems in different countries. |
Understanding Resource Management
What are System Resources?
System resources are the physical and virtual components within a computer system that must be managed to ensure smooth operation. These include both hardware and software elements, and their management is crucial for system performance and stability.
Main Types of Resources
- Primary memory (RAM): Temporary storage for data and instructions currently in use
- Secondary storage: Long-term data storage (e.g., hard drives, SSDs)
- Processor speed (CPU): Determines how quickly instructions are executed
- Bandwidth: The rate of data transfer, especially relevant for networks
- Screen resolution: The clarity and detail of visual output
- Disk storage: Space available for files and applications
- Sound processor: Handles audio signals and output
- Graphics processor (GPU): Manages complex visual computations and rendering
- Cache: High-speed memory between RAM and the CPU to speed up data access
- Network connectivity: The ability to connect and communicate with other devices and networks
Limitations and Problems
Each resource has its own limitations. For example, insufficient RAM can cause slow performance, limited bandwidth can lead to slow downloads, and a slow processor can bottleneck the entire system. These limitations can cause errors, crashes, or poor user experience.
The Role of the Operating System
The operating system (OS) is responsible for managing all system resources. Its key functions include:
- Memory management: Allocating and tracking memory use among applications
- Peripheral management: Controlling and communicating with devices like printers, keyboards, and mice using device drivers
- Multitasking: Allowing multiple applications to run simultaneously by allocating CPU time
- Security: Preventing unauthorised access and protecting files
- User interface: Providing a way for users to interact with the system (e.g., GUI, CLI)
Resource Management Techniques
| Technique | Description |
|---|---|
| Scheduling | Deciding which process gets to use the CPU and when |
| Policies | Rules that determine how resources are allocated |
| Multitasking | Running multiple applications at the same time |
| Virtual memory | Using disk space to extend RAM, allowing more or larger applications to run |
| Paging | Dividing memory into sections to manage how data is stored and accessed |
| Interrupts | Signals that temporarily halt the CPU to deal with urgent tasks |
| Polling | Regularly checking the status of a device or process |
Dedicated Operating Systems
A dedicated operating system is designed for a specific device or purpose, such as a smart TV or a mobile phone. These systems are often more efficient and secure because they are tailored to the device’s specific needs.
Hiding Hardware Complexity
The OS abstracts the complexity of hardware, providing a consistent interface for users and applications. This means users do not need to understand how hardware works to use the computer effectively.
Glossary of Key Terms
| Term | Definition |
|---|---|
| Resource | Any physical or virtual component of limited availability within a computer system |
| Primary memory (RAM) | Fast, temporary storage for data and instructions currently in use |
| Secondary storage | Permanent storage for data and programmes (e.g., hard drives, SSDs) |
| Processor (CPU) | The central component that executes instructions |
| Bandwidth | The amount of data that can be transferred in a given time, especially over a network |
| Screen resolution | The number of pixels displayed on the screen, affecting image clarity |
| Cache | Very fast memory used to store frequently accessed data for quicker retrieval |
| Peripheral | External devices connected to the computer (e.g., printers, keyboards, mice) |
| Device driver | Software that allows the OS to communicate with hardware devices |
| Multitasking | The ability of the OS to run multiple applications at the same time |
| Virtual memory | Technique that uses secondary storage to extend the apparent size of RAM |
| Paging | Dividing memory into fixed-size blocks to manage how data is stored and accessed |
| Interrupt | A signal that temporarily halts the CPU to give attention to an urgent task |
| Polling | The process of repeatedly checking the status of a device or process |
| Dedicated OS | An operating system designed for a specific device or function |
| Abstraction | The process of hiding complex details to provide a simpler interface |
Topic 7 Sensors
Syllabus Points
For IB Computer Science HL, Topic 7 covers “Control” and includes these key points related to sensors:
- 7.1.1: Discuss a range of control systems.
- 7.1.2: Outline the uses of microprocessors and sensor input in control systems.
- 7.1.3: Evaluate different input devices for the collection of data in specified situations.
- 7.1.4: Explain the relationship between a sensor, the processor, and an output transducer.
- 7.1.5: Describe the role of feedback in a control system.
- 7.1.6: Discuss the social impacts and ethical considerations associated with the use of embedded systems.
- 7.1.7: Compare a centrally controlled system with a distributed system.
- 7.1.8: Outline the role of autonomous agents acting within a larger system.
Understanding Sensors in Control Systems
What is a Control System?
A control system is a device or collection of devices that manages, directs, or regulates the behaviour of other devices or systems. These systems are found everywhere—from automatic doors and heating systems to washing machines and traffic lights.
The Role of Sensors
Sensors are input devices that detect or measure physical properties (such as temperature, light, pressure, or motion) and convert these measurements into signals that can be processed by a computer or microprocessor. The data collected by sensors is usually in analogue form and must be converted into digital data for processing.
Common Types of Sensors
- Light sensors
- Temperature sensors
- Pressure sensors
- Motion sensors
- Sound sensors (microphones)
- Ultrasonic sensors
- Infrared sensors
Microprocessors and Sensor Input
Microprocessors (or microcontrollers) are the “brains” of control systems. They receive input from sensors, process the data, and decide what actions to take. For example, in a heating system, a temperature sensor detects the room temperature, the microprocessor compares it to the set value, and then sends a signal to turn the heater on or off.
The Input-Process-Output (I-P-O) Model
- Input: Sensors collect analogue data from the environment.
- Process: The microprocessor receives this data (converted to digital form through an Analogue-to-Digital Converter, or ADC), processes it, and determines the appropriate response.
- Output: The microprocessor sends signals to output devices (output transducers), which convert digital signals back to real-world actions (such as turning on a motor or activating a light).
Output Transducers
An output transducer converts electrical signals from the processor into physical actions, such as movement, heat, or sound. Examples include motors, speakers, and lights.
Feedback in Control Systems
Feedback is a critical feature of control systems. It involves continuously monitoring the output and adjusting the system’s operation to ensure desired performance. For example, in a washing machine, sensors monitor water level and temperature, and the processor adjusts valves or heaters accordingly.
Examples of Control Systems Using Sensors
| System | Sensors Used | Output Devices |
|---|---|---|
| Automatic doors | Motion, proximity | Motor (door opener) |
| Heating system | Temperature (thermostat) | Heater on/off switch |
| Taxi meter | Speedometer, GPS | Display, fare printer |
| Lift (elevator) | Motion, button | Motor, display |
| Washing machine | Temperature, water level | Valves, motor |
| Traffic lights | Motion, timer, button | Light signals |
Glossary of Key Terms
| Term | Definition |
|---|---|
| Sensor | A device that detects or measures a physical property and responds to it. |
| Microprocessor | An integrated circuit that processes data and performs control functions. |
| Control System | A system that manages and controls devices using feedback and other techniques. |
| Output Transducer | A device that converts electrical signals into physical actions (e.g., motors). |
| Feedback Loop | A system where output is monitored and adjustments are made to achieve desired results. |
| Embedded System | A computer system integrated into other devices to perform dedicated functions. |
| Centrally Controlled System | A system managed by a single central controller. |
| Distributed System | A system where control functions are distributed across multiple controllers. |
| Autonomous Agent | A system that operates independently, making decisions based on rules or objectives. |
| Analogue-to-Digital Converter (ADC) | A device that converts analogue signals from sensors into digital data for processing. |
| Digital-to-Analogue Converter (DAC) | A device that converts digital signals from the processor back into analogue signals for output. |
) to enable essential functionality. Click "I accept" if you are okay with that! :)