All of Computer Science Paper One

Regular language

any language that can be described using regular expressions

Regular expression

notation (ab*,a+) that represents all elements of a set

Context-free languages

a way of describing the syntax of a language when the syntax is complex (e.g. palindrome). Used when counting and matching is infinite

Backus-Naur Form

a form of notation describing the syntax used by a programming language

• method of context-free language

• produces a set of acceptable strings (describing the rules of the language)

e.g. <Integer> ::= <Digit>|<Digit><Integer>

Terminal

the final element that requires no further rules

Syntax diagram

a way to represent BNF expressions or any context-free language

A set

A set is a collection of unordered, unique values (only appears once)

cartesian product

combining the elements of two or more sets to create a set of unordered pairs

e.g.
A = {1, 2}

B = {x, y}
then A × B = {(1, x), (1, y), (2, x), (2, y)}

Finite State machines

• Any device that changes state based on an input

State transition diagram

• a visual representation of finite state machines using circles and arrows

• double circle - end state

State transition table

• a table to represent an FSM by showing its inputs, current state and next state

Mealy machine

• a finite state machine with outputs

Turing Machine

a type of finite state machine that reads and writes data to an unlimited tape

How does a Turing Machine operate

• the tape is used as memory and is divided into many cells

• the read write head can either read the cell or write into it

• the machine can halt at any point if the 'halting state' is entered or if the input has been processed fully

Universal Machine

• a machine simulating other turing machines by reading a description of the machine with the inputs of its own tape

• (turing machines linked together with one tape)

Constant O(C)

time independent of input (e.g. determining if a number is odd or even)

Logarithmic - O(log₂(n))

halves items per iteration (e.g. binary)

linear O(n)

worst case scenario, goes through every item (e.g. linear)

linear logarithmic

o(nlog(n)) - merge sort

polynomial O(n²)

bubble sort

Exponential O(2ⁿ)

Cannot be solved, intractable - recursively calculating fibonacci numbers

Factorial O(n!)

intractable - travelers problem

graphs for BigO

Algorithm

a sequence of steps that can be followed to complete a task that always terminates

tractable problems

problems that have a polynomial (or less) time solution

intractable problems

problems that have a longer time solution than polynomial

representational abstraction

Removes unnecessary details from the problem

abstraction by generalisation

Groups common characteristics

Information hiding

 hiding unessential details of an object

Procedural abstraction

breaking down a complex model into reusable procedures

Functional abstraction

disregards the particular method of a procedure and results in just a function

Data abstraction

hiding specific details of how data is represented to create new data structures

Problem abstraction/reduction

 removing details from a  problem until its solvable

Decomposition

 breaking down a problem into small sub-problems to be solved individually

Composition

combining procedures to form a larger system

Automation

putting abstractions of real world phenomena into actions by creating algorithms

Halting Problem

Process of writing a program to test if another program will halt from given inputs without running the given program

The halting problem demonstrates that there are some problems that cannot be solved

Depth-first

Fully explores branch before backtracking
Uses a stack

e.g. navigating a maze

Breadth-first

searches left to right in rows from the top (level by level)

uses a queue

e.g. shortest path for an unweighted graph

tree traversal orders (pre,in,post)

pre-order: VLR

in-order: LVR

post-order: LRV

Linear Search

Searches every item in a list

List can be unordered

O(N)

Binary Search

Looks at the midpoint of a list and determines if the target is higher or lower than the midpoint until it is found

Time halves each search

Requires an ordered list

O(logN)

Binary tree search

Compares child nodes on a binary tree to see if its higher/lower

O(logN)

Bubble sort

Makes passes through data and swaps adjacent items until no swaps are performed

O(n²)

Merge sort

Divides array up into sorted lists and merges them together

O(nlogn)

Dijkstra’s algorithm

works out the shortest path between a single source and every other vertex on weighted graphs, producing the shortest path tree

Tracing Dijkstra’s algorithm

1. starting with A, list all the connections to other nodes, marking unconnected nodes as infinity

2. the smallest number from this row is the next row's node

3. B was the smallest so next we list all the connections from B to other nodes as before.

what does pre-order traversal do on a tree

copies the tree

what does in-order traversal do on a tree

sorted output for BST

what does post-order traversal do on a tree

delete tree

What are data structures

methods for storing information on a computer

Why are there multiple data structures?

Depending on the usecase, different complexities and efficiencies are needed

Arrays

A finite indexed set of related elements (of the same data type)

What are files made up of (records/fields)

Each file is made up of records, composed of fields

Characteristics of static datatypes

• amount of memory set prior by the programmer

• fixed in size

• fast access speeds

  • cannot grow/shrink in size (results in memory wastage or overflow)

Characteristics of dynamic data structures

• Flexible in size

• Efficient memory use

• Slower access

• Requires more memory

• Increased complexity

Why are graphs used

to represent complex relationships between items (e.g. networks - transport, IT, the internet)

What do graphs consist of

nodes, joined by edges

Weighted vs unweighted graphs

Weighted graphs assign values to an edge (e.g. time, distance, cost)

Directed vs undirected graphs

Edges have directions, connecting nodes to each other

Adjacency list

Stores every possible connection per node

A: B,C,D
B: A,C,E

Adjacency matrix

Stores all possible connections that exist on a table (1 = edge exist, 0 = no edge)

Adjacency List advantages

Adjacency List is quicker for lookups (searched by row/column) and is suited for sparse graphs with lots of connections

Adjacency List disadvantages

More complex to implement

Adjacency Matrix advantages

Suited for dense graphs with less connections
O(1) lookup time

Disadvantages of Adjacency matrixes

wastes space if there a few edges

Tree characteristics

• connected

• undirected

• no loops

Rooted trees

all nodes stem from root/parent node

Leaf nodes

Nodes with no children

Binary trees characteristics

• has a root node

• two or less child nodes

Used in file management on computers

how does a hashing algorithm work

hashing algorithm takes an input (key) and returns a hash, that aims to be unique to its input.

the result of the hash is the index of the key-value pair in the hash table.

what is a hash table

a way of storing data that allows it to be retrieved with a constant time complexity O(1) made up of a table containing the data and key

advantages of hashing

faster to lookup and search

disadvantages of hashing

hard to design

risk of collisions

two ways to how to handle hashing collisions

• chaining

• rehashing

what is chaining

creating a linked list for duplicated indexs

what is rehashing

recalculating the hashing algorithm to provide a new index until it finds an empty slot or using an alternative hashing algorithm

dictionaires

a data structure that stores key-value pairs

how do dictionaries work?

a dictionary maps keys to data (associative array), where the keys identifiy the location of the data. this can be done by implementing a hash table to calculate the key.

for example:

Car = {"make": " toyota"}

Car["make"]

or

Car = {}

Car["make"] = "toyota"

dot product

dot product of A = [12,3] and B = [5,8]
= (12×5) + (3×8) = 84

what does scaling a vector do (magnitude/direction)

magnitude changes, direction remains the same

Access order in Queues

FIFO (first in, first out)

Usecase of queues

Computer keyboards → letters appear in order typed

Enqueuing an item to a linear queue

1. Check if full - if full → error

2. If empty, set front to 0

3. Increment rear and insert value at rear

Dequeuing an item from a linear queue

1. Check queue isn’t empty - if empty → error

2. Remove item at front

3. Increment front pointer

Benefits of circular queues

Reuses empty spaces, wrapping the array around itself

Enqueuing to a circular queue

1. Check if queue is full → error

2. Compare rear pointer with maximum size of array

3. If not empty, rear pointer increments and item added to new rear position

Dequeuing from circular queue

1. Check if queue is empty → error

2. If not, dequeue front item in queue

3. Reduce size of queue

4. Check if front pointer is at the end of the array, if it is set to first position. Else, add 1 to front pointer

Priority queue advantages

Higher priority elements are removed first

Equal prioriy elements = standard FIFO order

Elements in priority queue are based on

their priority, with elements being shifted when added

Usecase for priority queues

Processor scheduling

Access order in stacks

LIFO (last in, first out)

Adding to a stack

Push

1. check if full

2. Increment top

3. Inset item at top

Remove item from stack

Pop

1. Check if empty

2. Remove elements from top

3. Decrement top

Peek operation

Returns item at top

Checking if stack is full/empty

• IsFull

• IsEmpty

Binary search trees

• used for efficient searching

• searches left, then root, then right

div symbol

//

mod symbol

%

normal division

/