Please enable JavaScript.
Coggle requires JavaScript to display documents.
A-Level Computer Science - Paper 2 Revision (Algorithms / Programming …
A-Level Computer Science - Paper 2 Revision
Algorithms / Programming
IDEs (Integrated Development Environment)
Enter and edit tools
Compile tools
Debugging tools
Breakpoint
- A specific point (line) in the code where the code will stop. Allows the programmer ti see whether or not the code wwill reach that line
Watch
- set on a variable. Will display a value every time the variable changes
Step through
- Allows the programmer to see exactly what is happening in the code, line by line.
Erroneous
- Data that is just outside of the expected range.
Boundary
- Data which is at the ends of the expected range
Normal
- Data that is within the expected range
Iteration and Recursion
Iteration
- A repeating loop within a program, repeating a number of different statements.
While...endwhile
Repeat...until
For...next
Recursion
- a statement in a function which calls itself repeatedly.
Base case must be included
- a stopping condition that when met, the routine will no longer call itself
For input values other than stopping condition,
the routine must call itself
Stopping condition must be met after a finite number of calls
Sorting Algorithms
Merge Sort
O(n log n)
Quick Sort
O(n²)
Bubble Sort
O(n²)
Insertion sort
O(n²)
Big O Notation
Used to express time complexity, or the performance, of an algorithm
Constant Time
O(1)
Linear Time
O(n)
Polynomial Time
O(n²)
Exponential Time
O(2ᴺ)
Logarithmic Time
O(log n)
Queues
First in First Out (FIFO)
data structure
New elements can only be added to the end of the queue, and elements can only be taken out of the front of the queue
Size of queue depends on number of elements in it
Examples
Printing queue output
Characters typed on a keyboard queue held in keyboard buffer
For simulation problems
Queue operations
enQueue(item)
Adds new item to the end of a queue
deQueue()
Remove item from the front of the queue
isEmpty()
Tests to see if the queue is empty
isFull()
Tests to see if the queue is full
Queue pointers - Show where the front and the rear is within the queue.
Linked List
A dynamic data structure used to hold an ordered sequence
Each
item
in the list is a
node
Each node contains a
data field
and the
next address field
called a
link
Data field holds actual item, pointer field contains the address of next item in sequence
Null pointer
- used to indicate that there are no further items in the list
Add to a linked list
Delete from a linked list
Coding a linked list
Object Orientated Programming
Behaviour
- actions which are performed by an object
State
- what each attribute in a class is doing
Attributes
(methods) - data stored in the class
Class
- Template for an object, defines the attributes and behaviours of the object
Easy to manage
Extremely modular
Mimics real world, thus easier to understand
Reusable in other programs
Coding a class
Computational Thinking
Abstraction
The
removal
of
unnecessary information
in order to leave the most important information behind
Abstraction in high level programming languages
Allows the programmer to not worry about the finer, technological details of coding.
3rd generation languages remove fiddly details such as where a variable is stored within memory
Decomposition
The process of
breaking down
a problem into
smaller, manageable parts
Makes a problem easier to understand
Makes it easier to test and maintain parts of code
If modules are self-contained, it makes it easier to find the modules in a piece of code which need to be changed
if modules do need to be changed, it will not affect the rest of the program
Data Structures
Trees
Root node at the top, 'leaves' at the bottom
Elements of a tree
Node
- Contain the tree data
Edge
- Connects two nodes. Every node EXCEPT the root node is connected by one edge from another node
Root
- Only node with no incoming edges
Child
- Set of nodes that have incoming edges from the same node
Parent
- A node is a parent of all of the nodes it connects to with outgoing edges
Subtree
- Set of nodes and edges comprised of a parent and all descendants of the parent. Subtrees may also be a leaf
Leaf node
- A node which has no children
Examples of use
manipulation stored lists of data
For making information easy to search for
Manipulating hierarchal data (e.g. folder structures, movements in a game)
Binary Search Tree
A
rooted tree
in which each node has a
maximum of two children
Holds items in a way which is easy and quick to search for a particular item
Tree Traversal
Preorder
Post-order
In order
Depth first
Breadth first
Deleting Nodes
Adding nodes
Similarities and differences of trees and graphs
Similarities
Both use nodes
Both use edges
(- Both used to sow the relationship between different nodes)
Differences
Trees go in one direction while graphs allow for more than one directional path
Graphs can have weighted paths while trees do not
Graphs allow for loops to be created while trees do not
Trees can have one or two edges from a node while graphs the amount of edges for a graph is not defined
Trees feature one root node while graphs do not have any root nodes
A tree is a type of hierarchal diagram while a graph can be used to represent a network between nodes
