1
Q
What is a primitive data type?
A
A data type that can’t be broken down further.
2
Q
What is an abstract data type?
A
A conceptual model of how data is to be organised and the operations we might perform on the data.
3
Q
What is a data structure?
A
Implementation of ADTs. Can combine multiple data under a single identifier.
4
Q
What are the key ADTs?
A
- Stacks
- Queues
- Graphs
- Trees
- Hash Tables
5
Q
What are arrays?
A
Static data structures that stored data of the same type arranged as a contiguous block in memory with a fixed length
6
Q
How does indexing work in arrays?
A
The index acts as an offset to the data from the start off the structure in memory. For this reason the dimensions and data type of the array must be known.
7
Q
What is a multidimensional array?
A
An n-dimensional array is a set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements.
8
Q
What are the uses of arrays?
A
- Can store multiple homogenous values
- Can represent vectors
- Can store tabular data in a matrix
- 2D arrays are common in machine learning applications that consist of large related data sets
9
Q
What are the advantages of static data structures?
A
- Do not require pointers so take up less space
- Can randomly access any element in constant time because data is stored continuously in memory
- Faster than dynamic data structures to access elements
10
Q
What are the disadvantages of static data structures?
A
- Cannot grow to accommodate more data being declared
- Cannot shrink to free up memory
- Inefficient if more space is allocated than required
- Can lead to errors if not enough space is allocated
11
Q
On what kind of basis is date retrieved from a stack?
A
Last-In-First-Out
12
Q
On what kind of basis is data retrieved from a queue?
A
First-In-First-Out
13
Q
What are the key operations of a stack?
A
- Push
- Pop
- Peek
- Test for empty stack
- Test for full stack
14
Q
What are the key operations of a queue?
A
- Add and item
- Remove an item
- Test for an empty queue
- Test for a full queue
15
Q
What is a stack overflow?
A
An attempt is made to push more data onto the stack that it can store
16
Q
What is a stack underflow?
A
Occurs when a pop is attempted on an empty stack.
17
Q
What are stacks comprised of?
A
- A sequence of items
- A stack pointer
18
Q
What are queues comprised of?
A
- Sequence of items
- Rear pointer
- Front pointer
19
Q
What are the uses of stacks?
A
- Reversing sequences of items
- Maintaining “undo” lists in applications
- Maintaining a web-browser history
- Storing processor state (register values) when handling an interrupt
20
Q
What are the uses of queues?
A
- Maintaining a queue of print jobs
- Managing an input buffer
- Handling multiple file downloads
- Maintaining a playlist of media
21
Q
Test if a stack is empty?
A
Check if the stack pointer is equal to -1
22
Q
Test if a stack is full?
A
Compare the stack pointer to the maximum size of the array (-1)
23
Q
Push an item onto a stack?
A
- Check if the state is full if not…
- Increment the stack pointer by 1
- Assign the pushed item to the element within item indexed by the stack pointer
24
Q
Peeking a stack?
A
- Check if the stack is empty, if not…
- Return the item at the stack pointer
25
Popping a stack?
1. Check if the stack is empty, if not…
2. Decrement the stack pointer
3. Return the item at the stack pointer + 1
26
What is a linear queue?
A simple static and array based implementation of a queue
27
What are the advantages and disadvantages of linear queues?
+Simple to program
-Can lead to wasted capacity as memory is never used up
-Process of shuffling data to solve this issue is inefficient
28
What is a circular queue?
A static array based implementation of a queue with “wrapping” front and rear pointers
29
What are the advantages and disadvantages of a circular queue?
+It avoids wasted memory space with no need of shuffling
- more complex to implement
(-Can still run out of storage space)
30
What are the different types of queues?
- Linear
- Circular
- Priority
31
How do you test if a linear queue is empty?
Check if the front pointer is greater than rear pointer
32
How do you test of a linear queue is full?
Check if the rear pointer points to the last element
33
How do you enqueue items in a linear queue?
1. Check if full
2. Increment rear pointer
3. Assign item to index indicated by rear pointer
34
How do you dequeue items in a linear queue?
1. Check if empty
2. Return value at the front pointer
3. Increment front pointer
35
How do you peek a linear queue?
1. Check if empty
2. Return value at front pointer
36
How do you enqueue items in a circular queue?
1. Check if queue is full
2. Increment rear pointer and modulus it with the **maximum size of the array**
3. Add items at index indicated by rear pointer
4. Increment queue size
37
How do you dequeue items from a circular queue?
1. Check if empty
2. Store removed item
3. Increment front pointer and modulus with maximum size of the array
4. Decrement the queue size and return item
38
What area the differences between a circular and linear queue? (Structure only)
- Circular more efficient but also more complex
- Can wrap around memory locations
- No space is wasted after dequeueing
- Linear queues shuffle but this is inefficient
- Circular queues don’t need to do this
39
What is a priority queue?
A type of queue where each item in the queue has a priority.
40
How do priority queues work?
- Items are stored within the queue based on priority with highest priority at the front.
- When enqueueing we search for an item that has less priority and insert the item in front of it by shuffling everything after it
- This preserves FIFO within priority levels
41
What are the advantages of a dynamic data structure?
- Can change size at run-time by dynamically allocating memory
- More flexible, with no wasted space
42
What are the disadvantages of a dynamic data structure?
- Do not store items in continuous memory locations so retrieving items takes longer
- Require memory to store pointers to next items so take up more space
43
What is a recursive subroutine?
A subroutine that **calls itself**
44
What is the base case?
Condition that evaluates to a known value to stop recursion.
45
What is a call stack?
An area of memory used to store data used by running processes and subroutines.
46
How does the call stack work?
1. Each new subroutine call pushes a stack frame onto the call stack
2. When a process completes, its stack frame is popped off the call stack
3. The previous process continues
47
What information does a stack frame contain?
- local variables
- parameter values
- return addresses
48
What are graphs?
An ADT comprised of a network of nodes connected by edges used to model complex relationships.
49
What is a node?
Part of a graph that represents objects or entities
50
What is an edge?
Part of a graph that represents a relationship between entities
51
What is a weight in a graph?
A data value used to label an edge.
52
What are the uses of graphs
- Human (social) networks
- Transport networks , including road and rail networks
- Connections between devices on a network
- Planning telecommunications networks
53
What is an undirected graph?
A graph in which each relationship between nodes is two-way.
54
What is a directed graph?
A graph where each relationship between nodes can be one-way as shown by arrows or bidirectional.
55
What is a weighted graph?
A graph in which each edge is given a weight.
56
What are some possible graph operations?
- Adding/Removing a node
- Adding/Removing an edge
- Test if an edge exists between two nodes
- Getting and updating weights on edges
- Finding a valid path between two nodes
57
What are the two main ways of implementing a graph?
- Adjacency matrix - size of N squared
- Adjacency list - size of N + E
58
How can an adjacency matrix be represented?
Static 2D array
59
How can an adjacency list be represented?
Dynamically as an array of graph nodes, each containing a list of pointers to other nodes
60
What are the advantages of adjacency matrices?
- Edges between nodes can be quickly identified using the coordinates of the nodes in the 2D array
61
What are the disadvantages of adjacency matrices?
- Almost half of the matrix is repeated data
- Stores every possible edge between nodes, even those that don’t exist
- Wasted data
62
When are adjacency matrices used?
- “Dense graphs” where there are a lot of edges
- When edges need to be frequently created,removed,identified or their weights changed
63
When are adjacency lists used?
- “Sparse graphs” where there are not many edges
- Nodes are frequently added/removed
64
What are the advantages of adjacency lists?
- Memory efficient as they only store edges that exist in the graph
65
What are the disadvantages of adjacency lists?
- They are slow to identify edges as each item in a list must be be searched linearly until the desired edge is found
66
What is graph traversal?
Visiting every node within the graph to achieve an purpose
67
What are the two different types of graph traversal?
- Depth-First Search
- Breadth-First Search
68
How does Depth First traversal work?
- **Recursively** visits nodes that are adjacent to a starting node
- Until a node is reached with no unvisited adjacent nodes
- At this point the algorithm backtracks
69
How is a stack used in depth first traversal?
Uses it to keep track of the currently visiting node and the history of nodes required to get there.
70
What are the uses of a depth first traversal algorithm.
- Finding a solution to a maze, where the maze is modelled as a graph
- Finding the valid path from one node to another
- Determining the order with which processes that depend on one another should occur
71
How does breadth first traversal work?
Adds all adjacent nodes to a queue and uses iteration to repeat the process with the node at the front of the queue.
72
What are some uses of breadth first searches?
- Identifying “friends” and first-degree contacts
- Finding immediately connected devices on a network
- Crawling web pages to build an index of linked pages as used by search engines
- Mapping an unknown graph
73
What is a tree data structure?
A specialised form of undirected graph with exactly one path between two nodes used to model hierarchical relationships.
74
What are the features of a tree?
- Undirected
- Unweighted
- Fully connected
- Acyclical
75
What is a binary tree?
A type of rooted tree where each node can have at most two children.
76
What are the uses of trees?
- Efficient searching and sorting algorithms
- Storing data that has a hierarchical structure
- Processing syntax in natural and programming languages
- Implementing probability and decision trees
77
Why are trees well suited for recursion?
They are a recursive data type such that each child node can be the root of a separate tree.
78
What is a rooted tree?
- One node is designated as the root which has no parents
- All nodes described as parent or child nodes
- Direction of hierarchy often shown by arrows
79
What are the features on a rooted tree?
- Root node: has no parent
- Child and Parent nodes
- Edges/Branches
- Leaf node: has no children
80
What is a binary search tree?
A type of binary tree where a particular method is used to insert new node in an optimal location for later search/retreival
81
What are Binary Search Trees used for?
Provide an efficient way of searching for items as well as providing an effective way of returning all items in the correct order.
82
What are the key operations of a tree?
- Add nodes
- Get child nodes
- Getting a subtree
- Searching for a node
- Determining the height of the tree
83
What are the uses of a pre-order traversal?
- Copying a tree
- Evaluating mathematical expressions using prefix notation
84
What are the uses of an in-order traversal?
- Outputting the contents of a binary tree in ascending order
85
What are the uses of a post-order traversal?
- Converting mathematical expressions from infix to postfix notation (Reverse Polish)
- Producing a postfix expression from an expression tree
- Deleting a tree
- Completing dependant processes in order
86
What is an expression tree?
A tree that represents a mathematical expressions evaluated using post-order traversals.
87
What it Reverse Polish Notation?
An alternate means of writing mathematical expressions using postfix notation
88
What is infix notation?
The operator sits between the operands
89
What is postfix notation?
Operator comes after operands
90
What are the benefits of Reverse Polish Notation?
- Simplifies mathematical expressions by eliminating the need for brackets as order is implied by notation
- More easily evaluated by stack-based interpreters
91
What are some properties of stack-based interpreters?
- Translate and execute program code line-by-line
- Invoke pre-complied subroutines to perform the line being translated
92
What is a hash table?
A data structure that stores a key/value pair based on an index calculated from a hashing algorithm
93
What is a collision in hash tables?
When two key values compute to the same hash value
94
What are properties of good hash functions?
- Make use of all info provided by the key
- Uniformly distribute output across table
- Maps similar keys to very different hash values
- Make use of only the fastest operations
95
How can collisions be dealt with in hash tables?
- Rehashing
- Linear probing
- Chaining
96
What is linear probing and what are its disadvantages?
- Look for the next available index and insert item there
- However increases potential for further collisions and can promote clustering
97
What is clustering in hash tables?
Nearby indexes are not randomly or evenly distributed
98
What is chaining?
Replacing the existing contents of the index with a list and add the new items to the list
99
What is rehashing?
Process of increasing the size of a hash table and redistributing the elements to new indexes based on their new hash values
100
What are the uses of hash tables?
- Databases: quick storage and retrieval of data based on primary keys
- Cache memory: determining the memory address for a given item of data
- Operating Systems: store locations of its programs and utilities for quick access
(Encryption)
101
How do hash tables work?
- When an item is added, its **key** is processed by a **hashing algorithm** that returns a **hash value**
- Items are placed in indexes specified by the hash value
- To search for an item, key is processed again and the resulting index is checked for the item, if it does not exist we can confidently say it is not in the table
102
What are the advantages of using hash tables to store data?
- Faster to lookup a record
- Time complexity of O(1) for retrieval
103
What are the advantages of storing data in a dictionary?
- More compact file as there are no empty records
- Produce a sorted list
- Do not have to design a hash algorithm so easier to design
- No need to **deal** with collisions
104
What is a vector?
A data structure that represents a size and a magnitude, made up of at least 2 components.
105
How can vectors be represented?
- List of numbers
- Functions
- Geometric point in space pointed to by an arrow
106
How can a vector with n components from the set of reals be written?
Rn
107
How can a vector be represented using a dictionary?
- Key: The value in the domain
- Value: The image in the codomain
108
How can we express a vector as a function?
f:S —> R where S is the set of values that the function can be applied to (domain) and R is the potential outputs of the function (co-domain)
109
What is the dot product of 2 vectors?
The single value result when applying one vector’s magnitude and direction to another
110
How do you calculate the dot product?
U = [u1, u2, … , un]
V = [v1, v2, … , vn]
U x V = u1v1 + u2v2 + … unvn
111
What are the uses of the dot product?
Can be used to find the angle between them using the formula:
ab = |a||b|cosx
112
What is a convex combination of two vectors?
A vector that lies on the line between two vectors
113
When is D a convex combination where:
D = aA + bB
Where A, B are vectors and a,b are scalars
If a and b are both greater than or equal to 0 and a + b = 1
114
What is a linear search algorithm?
An algorithm that looks through each item in a set until the search key is found or every item has been inspected.
115
What are the advantages and disadvantages of linear search?
+ Only option for unsorted lists
- Inefficient: O(n)
116
What does the efficiency of a linear search depend on?
- Size of the dataset
- The location of the item to search for
117
What is a binary search algorithm?
An algorithm that looks at the middle item, if it is less look at the middle item in the lower half, if it is more look at the middle item in the upper half. This is repeated until it is found or **low pointer is above the high pointer**
118
What are the advantages and disadvantages of binary search?
+ Very efficient for large databases - O(log n)
- Can be more difficult to implement
- Must be a sorted list
119
How do you search in a binary search tree?
Using an in-order traversal
120
How does bubble sort work?
Each item in a list is compared to the one after it. If the item after is smaller that the current one then they swap until no swaps are made and it is sorted.
121
What are the disadvantages of bubble sort?
- Inefficient time wise as time complexity of O(n2)
- Algorithm continues to iterate over the list even if no further swaps are required
122
How can bubble sort be improved?
- Reducing the number of comparisons after each pass
- A sorted flag that can stop the sort if no swaps are made
123
How does merge sort work?
- Example of a divide and conquer algorithm where the program is broken down into smaller units
- List is continuously divided until there is only one item in each
- Sublists are combined in order until the list os fully sorted
124
What are the disadvantages of merge sort?
If done recursively is not very memory efficient
125
What are the advantages of merge sort?
Time efficient with an efficiency of O(nlogn)
126
What is an optimisation algorithm?
An algorithm that finds the best possible solution to the problem proposed.
127
What is an example of an optimisation algorithm?
Dijkstra’s Shortest Path (DSP)
128
What does DSP do?
Calculates the shortest distance between a starting node to all other nodes in the graph
129
What is the efficiency of DSP?
O(n2)
130
What are the uses of DSP?
- Shortest path between two locations in a transport network
- Telephone and computer network planning
- Network routing / packet switching
131
What properties are used to classify algorithms?
- Time complexity
- Space required
132
What is a tractable algorithm?
An algorithm that can be solved within polynomial time: O(nk)
133
What are all the time complexities?
- Constant complexity: O(1)
- Logarithmic Complexity: O(logn)
- Linear Complexity: O(n)
- Polynomial Complexity: O(nk)
- Exponential Complexity: O(xn)
- (Factorial Complexity: O(n!) )
134
What is an intractable algorithm?
An algorithm that has a computational solution which is not within polynomial time so is not practical for anything other than small n.
135
What are the properties of an algorithm with constant complexity?
- **Time Taken** is constant so is independent of size of the dataset
- As n increases the time taken stays the same
136
What are some examples of algorithms with a constant complexity?
- Accessing an index in an array
- Looking up a value in a hash table (assuming no collisions)
- Popping from a stack or dequeueing from a queue
137
What are the properties of an algorithm with logarithmic complexity?
- Time taken increases logarithmically with respect to the size of the database
- The size of the problem set is halved after each iteration or recursive call
138
What are some examples of algorithms with a logarithmic time complexity?
- Binary Search
- Merge Sort
139
What are the features of an algorithm with a linear time complexity?
Time taken increases proportionally with the size of the dataset
140
What are some examples of algorithms with a linear time complexity?
- Linear Search
- Traversing a linked list
141
What are the properties of an algorithm with a polynomial complexity?
- Time taken increases exponentially with the size of the dataset
- At the limit of the tractability
142
What are some examples of algorithms with a polynomial time complexity?
- Bubble Sort
- Dijkstra’s shortest path
143
What are the properties of an algorithm with exponential complexity?
- Time taken increases exponentially with size of dataset
- Intractable
144
What are some examples of algorithms with an exponential time complexity?
- Brute force password cracking
- Travelling Salesman Problem
145
What are the number of different permutations for a set with size n?
n!
146
How to identify O(1)
No iteration or number of steps doesn’t depend on n
147
How to identify O(n)
Single iteration that depends on n
148
How to identify O(nk)
Nested iteration where each iterative structure depends on n and k is the iterative depth
149
How to identify O(logn)
Breaking down the problem into halves
150
How to identify O(xn)
Number of iterative structures/ recursive calls depends on n
151
What do you do if an algorithm has a combination of time complexities?
You select the worst Big O factor
152
What is a heuristic?
Rules based on the knowledge of a problem that can be used to find an approximate solution by changing some constraints in the problem or reducing the problem space.
153
What is the halting problem?
Determining whether a program will halt for a particular input without running the program
154
What did the Halting Problem prove?
There was an example of a problem that is unsolvable
155
What was the significance of the Halting Problem?
Demonstrated that there are un-computable problems where no algorithm can solve them
156
Why are heuristics used?
A solution will arise within a reasonable time. However this may not be the best solution.
157
How are records added to a hash table?
- **Hashing algorithm** is applied to a **key**
- Result is the **location in the table** where the record should be stored
- If location **is not empty** then use **next free location**
158
What is a heuristic technique?
A method of finding a solution to a problem that might not be the most optimum solution
159
What is a hash function in the context of storing data in a file?
A function that computes a record address within a specified range from a key field value
160
What is a dictionary?
A collection of key-value pairs in which the value is accessed via the associated key
161
What is the main use of dictionaries?
Information retirival such as dictionary based compression
