Computer ScienceQ&A by dot point

Big-O notation for time and space complexity: the constant, logarithmic, linear, linearithmic, polynomial and exponential complexity classes, how to determine the Big-O of an algorithm, and using it to compare and judge the suitability of algorithms.

Graph and tree traversal: breadth-first and depth-first traversal of a graph, the pre-order, in-order and post-order traversal of a binary tree, and the shortest-path algorithms Dijkstra's algorithm and A* search.

Searching algorithms: linear search, binary search and binary tree search, how each works with a trace, the precondition for binary search, and their time complexity in Big-O notation.

Sorting algorithms: bubble sort, insertion sort, merge sort and quick sort, how each works with a trace, and their time complexity in Big-O notation including best, average and worst cases.

Logic gates (AND, OR, NOT, XOR, NAND, NOR) and their truth tables, constructing and interpreting truth tables, and simplifying Boolean expressions using the laws of Boolean algebra including De Morgan's laws, distribution, association and commutation, and Karnaugh maps.

Floating-point representation of real numbers using a mantissa and an exponent (both in two's complement), normalisation of a floating-point number, and the trade-off between range and precision.

Logic circuits built from gates: the half adder and full adder for binary addition, and the D-type flip-flop as a single-bit memory element, including their truth tables and Boolean expressions.

Number systems: binary, denary and hexadecimal conversion, representing negative numbers with sign and magnitude and two's complement, binary addition and subtraction, fixed-point binary fractions, and the use of hexadecimal and bitwise masks.

Assembly language and the relationship between assembly instructions and machine code, the instruction set with opcode and operand, the Little Man Computer model, and the addressing modes (immediate, direct, indirect and indexed).

Input, output and storage devices: how different input and output devices are used, the characteristics, uses and operation of magnetic, optical and solid-state (flash) storage, the difference between RAM and ROM, and virtual storage.

The structure and function of the processor: the arithmetic logic unit, control unit, registers (PC, ACC, MAR, MDR, CIR), buses (data, address, control), and the fetch-decode-execute cycle in the von Neumann architecture.

Factors affecting processor performance (clock speed, number of cores, cache size and type), pipelining, and the characteristics and uses of CISC and RISC processors, multicore and parallel systems, and GPUs.

The functions of an operating system: memory management (paging, segmentation, virtual memory), interrupts and the interrupt service routine, scheduling algorithms, and the distinction between systems software (operating systems, utilities) and application software.

Compression (lossy and lossless, run length encoding and dictionary coding), encryption (symmetric and asymmetric) and hashing, including their characteristics, differences and appropriate uses.

The relational database model: entities, attributes, primary and foreign keys, entity relationships, the difference between a flat file and a relational database, and normalisation to first, second and third normal form.

Structured Query Language (SQL): defining tables, and using SELECT, FROM, WHERE, ORDER BY, INSERT INTO, UPDATE, DELETE and joining tables to query and maintain a relational database, with referential integrity.

Transaction processing and the ACID properties (atomicity, consistency, isolation, durability), record locking and serialisation to manage concurrent access, and redundancy through commitment ordering and backups.

The legislation relevant to computing: the Data Protection Act, the Computer Misuse Act, the Copyright, Designs and Patents Act and the Regulation of Investigatory Powers Act, and the principles of copyright and software licensing including open source and proprietary models.

Data structures: arrays, records, tuples and lists, the stack and queue abstract data types and their operations, linked lists, trees and graphs, and hash tables, including how each is used and its advantages.

Primitive data types (integer, real/float, Boolean, character, string) and how text is represented using character sets such as ASCII and Unicode, including the size and range implications of each type.

Mathematical skills for computer science: set theory and set operations, the comparison of binary, denary and hexadecimal magnitudes, simple logic propositions, and the use of these tools to reason about data and algorithms.

The moral, social, ethical and cultural impact of computer science, including privacy, the environmental impact of computing, automation and employment, the digital divide, and how to evaluate the ethical issues raised by new technologies.

Web technologies: HTML for structure, CSS for presentation and JavaScript for client-side behaviour, the difference between client-side and server-side processing, and how search engines index and rank pages using web crawlers and the PageRank algorithm.

Networks (LAN and WAN, network topologies, client-server and peer-to-peer), network hardware (NIC, switch, router, WAP), the need for protocols and protocol layering, the TCP/IP four-layer stack, and packet switching.

Network security: the threats from malware (viruses, worms, trojans), social engineering and network attacks, and the protective measures of firewalls, proxy servers, encryption and access control.

The structure of the internet, the Domain Name System (DNS), URLs and IP and MAC addressing, the difference between the internet and the world wide web, and the protocols HTTP, HTTPS, FTP and the client-server model of the web.

Object-oriented programming techniques in practice: defining classes with attributes and methods, constructors and instantiation, getters and setters for encapsulation, inheritance and method overriding for polymorphism, and the benefits of an object-oriented design.

Programming techniques: sequence, selection and iteration, recursion, the use of subroutines (procedures and functions) with parameters passed by value and by reference, local and global variable scope, and the features of an integrated development environment (IDE).

Thinking abstractly: the nature and need for abstraction, representational and procedural abstraction, and the use of models; thinking ahead and decomposition: breaking a problem into smaller sub-problems.

Thinking ahead: identifying inputs and outputs, preconditions, caching and reusable program components; thinking procedurally: identifying the steps and the order of a solution and the components that can be reused.

Thinking concurrently: determining which parts of a problem can be tackled at the same time, the benefits and limitations of concurrent and parallel processing, and the difference between true parallel processing and concurrent processing on a single processor.

Thinking logically: identifying the decision points and conditions that affect the flow of a solution; computational methods including problem recognition, divide and conquer, backtracking, heuristics, performance modelling and visualisation.

The nature of applications generation, the role of utilities and the difference between systems and application software, and the types and uses of software including open source versus closed source and custom-written versus off-the-shelf.

Types of operating system (distributed, embedded, multitasking, multiuser, real-time) and software development methodologies (waterfall, agile, extreme programming, spiral, rapid application development), with their merits and appropriate uses.

Programming paradigms (procedural, low-level / assembly and object-oriented), the need for and characteristics of different levels of programming language, and the core principles of object-oriented programming: classes, objects, methods, attributes, encapsulation, inheritance and polymorphism.

The need for, and the characteristics of, translators (assemblers, compilers, interpreters), the stages of compilation (lexical analysis, syntax analysis, code generation, optimisation), and the role of linkers, loaders and libraries.