Key term
Eduqas A-Level Computer Science A500QS
Data Structures: Arrays, Records and Hash Tables
Stacks, Queues, Linked Lists and Trees
Boolean Logic and Simplification
Algorithms, Pseudo-Code and Programming Constructs
Variables, Scope, Parameters and Identifiers
Recursion and Modular Programming
Sorting Algorithms
Searching and Shortest-Path Algorithms
Big O Notation and Algorithm Efficiency
Validation, Verification and Testing
Data Compression
Programming Paradigms and Computer Languages
Topic overviewProgramming paradigms and where each is usedProcedural programmingEvent-driven and visual programmingMark-up languagesObject-oriented programming: objects, classes and methodsAmbiguity in natural language and the standardisation of languagesBackus-Naur form and syntax diagramsHigh-level and low-level languages, and choosing one
Systems Analysis, Maintenance and Documentation
Topic overviewWaterfall, Agile and approaches to systems developmentThe feasibility study, budgets and time scalesMethods of investigationAbstraction, decomposition and data flow diagramsSelecting suitable hardware and softwareAcceptance testing and methods of changeoverPerfective, adaptive and corrective maintenanceBackup and recovery proceduresUser and maintenance documentation
System Design and Human-Computer Interaction
Software Engineering Tools and Translators
Topic overviewSoftware tools for the software engineering processSoftware packages in analysis, specification, design and testingIntegrated development environmentsDebugging toolsProgram version managementCompilers, interpreters and assemblersThe stages of compilationTranslation errors and execution errors
Computing, Society and the Law
Computer Architecture, the Processor and Assembly Language
Topic overviewHardware elements and how they are connectedVon Neumann architecture and the stored program conceptThe processor: control unit, ALU and registersTypes of memory: RAM, ROM and virtual memoryCache memory and locality of referenceThe fetch-execute cycle and its registersParallel processing and the limits to parallelisationAssembly language and executing a program
Input, Output and Secondary Storage
Topic overviewInput devices and how data is capturedOutput devices and how results are presentedChoosing input and output devices for a situationVoice input, dictation and voice print recognitionMagnetic, optical and solid state storageComparing secondary storage for a purposeDisc organisation, fragmentation and defragmentation
Networks, Protocols and the Internet
Topic overviewNetworks, LANs and WANsNetwork topologies and connection hardwareNetworking standards and the layered modelIP addressing, TCP and UDPApplication protocols: HTTP, FTP, SMTP, IMAP and DHCPHandshaking and establishing a connectionWireless hardware and wireless technologiesThe internet and connected mobile devices
Data Transmission and Network Performance
Topic overviewSerial and parallel transmissionSimplex, half duplex and full duplexMultiplexing and sharing a channelCircuit, message and packet switchingPackets, headers and packet contentsNetwork collisions and collision detectionRouting traffic on a networkCalculating transfer rates and lowest cost routes
Number Systems and Binary Arithmetic
Data Types, Characters and Floating Point
Topic overviewPrimitive data typesStorage requirements for each data typeASCII and standardised character setsUnicode and multilingual encodingFloating point form: mantissa and exponentConverting between real numbers and floating pointInteger and floating point comparedTruncation, rounding and accuracy
Files, Records and File Organisation
Topic overviewThe purpose of files in data processingFiles, records and fieldsFixed and variable length fields and recordsMaster files and transaction filesSerial and sequential file accessIndexed sequential access and multi-level indexesDirect access and hashing algorithmsOverflow handling and file reorganisationFile security, backups, generations and archiving
Databases, Normalisation and Entity Modelling
SQL, Big Data and Distributed Systems
Topic overviewQuery languages and the purpose of SQLCreating tables: CREATE TABLE, data types and keysRetrieving data with SELECT, FROM and WHEREComparison operators, IN, AND, OR and sub-queriesSorting, grouping and aggregate functionsInserting, updating, deleting and joining dataThe DBMS, the data dictionary and distributed databasesBig Data, data warehousing, data mining and predictive analytics
The Operating System and Its Modes
Topic overviewThe need for an operating system and the role of the kernelManaging peripherals, processes and memory protectionThe user interface and the layers between user and hardwareDirectory structures and file attributesUtility softwareBatch processing, real time control and real time transaction systemsTypes of operating system: single-user, multi-user, multi-tasking and multi-programmingDesigning an interface for different users and environments
Interrupts, Memory Management and Scheduling
Topic overviewWhat causes an interruptInterrupt handling and the interrupt service routineInterrupt priorities and how they are allocatedPartitioning main memoryMethods of data transfer between processor and devicesBuffers and double bufferingHigh level scheduling, processor and device allocationProcess states, time-slicing, polling and threading
Types of Software System
Data Security, Cryptography and Attack
Topic overviewOnline updating and the integrity of shared filesDangers of holding personal dataClerical procedures, access levels, passwords and write protectionCryptography: its purpose, and symmetric and asymmetric keysHashing, digital signatures and certificatesCaesar and Vernam ciphers and comparing cipher strengthBiometric technologies and their limitationsThreats, damage and contingency planningMalicious software, hacking and penetration testing
Searching and Shortest-Path Algorithms
- 7 subtopics
- 21 things to know
- Component 1
What Searching and Shortest-Path Algorithms covers
Searching and Shortest-Path Algorithms is examined in Component 1, Programming and System Development. It covers linear search, binary search, comparing linear and binary search, graphs, weights and the shortest-path problem, Dijkstra's shortest-path algorithm, tracing a shortest-path algorithm by hand and choosing the right searching technique.
The 7 subtopics
Each one has its own page.
- Linear searchHow a linear search works, main advantage of a linear search and time complexity of a linear search.Open →
- Binary searchHow a binary search works, time complexity of a binary search and three outcomes of one comparison in a binary search.Open →
- Comparing linear and binary searchThe two searches set against each other on how they narrow the data, on comparisons needed in the worst case, on memory, and on when the difference is worth anything.Open →
- Graphs, weights and the shortest-path problemGraph in computing terms, weighted graph and node and what is an edge.Open →
- Dijkstra's shortest-path algorithmSettling the nearest unvisited node, relaxing the distances to its neighbours, and repeating — the algorithm that finds the lowest-cost route rather than the fewest hops.Open →
- Tracing a shortest-path algorithm by handOne weighted graph carried through the whole algorithm, with the tentative distances after each step and the order in which the nodes settle.Open →
- Choosing the right searching techniqueMatching the technique to the data — a short unsorted list, a large sorted array queried constantly, a weighted network — and the cost of keeping data sorted in the first place.Open →
What you need to know
Answer each one before you reveal it.
Your recallNot started
Key term
Compare the linear and binary searches on memory use and on which duplicate they return.
Key term
What condition must the data meet before a binary search can be used?
Key term
What is a graph in computing terms?
Key term
What does Dijkstra's algorithm compute?
Key term
How is the tentative distance to a node updated during a trace?
Key term
Which search technique suits a small unsorted list?
Key term
Describe how a linear search works.
Key term
Describe how a binary search works.
Key term
State the key difference in how linear and binary searches narrow the data.
Key term
What is a weighted graph?
Key term
Describe the first step of Dijkstra's algorithm.
Key term
Describe the layout of a table used to trace Dijkstra's algorithm by hand.
Key term
Which search technique suits a large sorted array that is queried often?
Evaluation
What is the main advantage of a linear search?
Numbers
A binary search runs on 2, 5, 8, 12, 16, 23, 38 and looks for 23. How many comparisons are made?
Key term
Compare the time complexity of the two searches.
Key term
What does a shortest-path algorithm find?
Key term
Which node does Dijkstra's algorithm visit next at each step?
Key term
How do you read the route itself out of a completed trace table?
Key term
Which technique is used to find the cheapest route through a network of nodes?
Take Searching and Shortest-Path Algorithms further
The same content, four other ways.
Commonly confused
Pairs that lose marks when they are blurred together.
Linear search vs Binary search
Linear search: working on any list and checking items one at a time. Binary search: needing sorted data and discarding half the list at each step.
Adjacency matrix vs Adjacency list
Adjacency matrix: a store holding every possible connection, suited to dense graphs. Adjacency list: a store holding only the connections that exist, suited to sparse graphs.
Tentative distance vs Settled distance
Tentative distance: a value that may still be lowered. Settled distance: a value that is final.
Questions from this topic
Each one with the model answer underneath.
- 1
Describe how a linear search works.
Model answer
A linear search examines each item in turn from the start of the list. The search stops when the target is found or the end of the list is reached.
- 2
What is the main advantage of a linear search?
Model answer
A linear search needs no ordering of the data, so it works on any list. The algorithm is also very simple to write and to check.
- 3
State the worst case number of comparisons a linear search makes on a list of n items.
Model answer
The worst case is n comparisons, which happens when the target is last or absent. A list of twice the length gives twice the worst case.
- 4
How many comparisons does a linear search make on average when the item is present?
Model answer
The average is about half the list, or (n + 1) ÷ 2 comparisons. The figure is roughly 100 for a list of 200 items.
- 5
A linear search looks for 23 in the list 8, 15, 4, 23, 42, 7. How many comparisons are made?
Model answer
Four comparisons are made because 23 sits in the fourth position. The search stops as soon as the item is found.
- 6
A linear search looks for 30 in the list 8, 15, 4, 23, 42, 7. How many comparisons are made?
Model answer
Six comparisons are made because every item must be checked. The search then reports that 30 is not in the list.
What is inside Levo
Six ways to work the same material.
Searching and Shortest-Path Algorithms revision questions
- What does Searching and Shortest-Path Algorithms cover in Eduqas A-Level Computer Science?
- 7 subtopics: linear search, binary search, comparing linear and binary search, graphs, weights and the shortest-path problem, dijkstra's shortest-path algorithm, tracing a shortest-path algorithm by hand and choosing the right searching technique. Each one has its own page with questions and model answers.
- How is Searching and Shortest-Path Algorithms organised?
- By the Eduqas A500QS specification, subtopic by subtopic, so it matches the order you are taught it in.
Every question in Searching and Shortest-Path Algorithms, on a schedule.
Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.
Or £46 a year, about £3.83 a month. Cancel anytime.