Data types, data structures and algorithms Flashcards
What is a string?
A collection of characters
1 nybble=
1 nybble = 4 bits
The least significant bit of a binary number is the one furthest to the…
right
BINARY ADDITION
0+0+0=
0+0+1=
1+1+0=
1+1+1=
0+0+0=0
0+0+1=1
1+1+0= 10 (0 carry 1)
1+1+1= 11 (1 carry 1)
Explain sign magnitude
A way of representing negative numbers in binary
Ignore most sig bit and convert remaining bits to decimal then change the sign
e.g 10101101 =173
1 10101101 = -173 (1 for negative)
0 10101101 = +173 (0 for positive)
Explain two’s compliment
Its a way of representing negative numbers in binary
This is done by making the most significant bit negative
eg 7 = 00000111
In two’s complement
-7=-128+64+32+16+8+1
=11111001
What is an easy way of converting a number to two’s complement?
Flip the bits in the positive version and adding one
eg 7 = 00000111
In two’s complement
=11111000 then add one
=11111001
Number bases
Decimal = base 10
Binary = base 2
Hexadecimal = base 16
HEX conversion values
0-9 = 0-9
A-F = 10-15
Convert hex 4E7F into decimal
16^3 : 4 (4X4096)
16^2 : E (14X256)
16^1 : 7 (7X16)
16^0 : F (15X1)
(4X4096) + (14X256) + (7X16) + (1X15)= 20095
Convert hex B2 into decimal
16x11 =B
1X2= 2
(16X11) + (1X2) 178
OR
B=11 2=2
11=1011 2=0010
COMBINE: 10110010
10110010=178
Can be split into 2 parts mantissa and exponent
What is this?
Floating point binary numbers
Why does floating point binary need to be normalised?
To make sure they are as precise as possible in a given number of bits
(meaning making use of as much mantissa as possible)
To normalise number make sure it starts with:
01 for positive num
10 for negative num
What is meant by a character set?
A published collection of characters and corresponding codes which can be used by computers for respresenting text
2 examples of character sets are ASCII and Unicode
Give examples of character sets
ASCII and Unicode
ASCII
Example of a character set
-Uses 7 bits (2^7= 128 characters)
-Capital A-Z=65-90
-Lower a-z= 97-122
-Also has codes to represent other symbols and numbers
-Can only represent characters in English language
UNICODE
-Uses a varying number of bits
-Better than ASCII as it can represent more characters meaning that it can be used for more different languages rather than just English
-Can represent letters, numbers, symbols, emojis….
What is an array?
An ordered, finite set of elements of a single type
-Taken to be zero-indexed (first index 0) unless stated in question
Linear array = 1D
What is a record made up of?
Row in a file made up of fields
-eg used in databases
Lists can contain elements of more than one data type
TRUE OR FALSE
TRUE
(Unlike arrays)
What is a list?
A data structure consisting of a number of ordered elements where each element can occur more than once
(ordered because the elements retain the sequence in which they were added until you change them)
A difference between lists and arrays is that the values in a list are stored non-contiguously.
What does this mean?
Non contiguous = The values don’t have to be stored in consecutive memory locations. Each element of a list can be in different places in memory.
Because lists store references (or pointers) to their values, which may be scattered in memory. This flexibility allows lists to grow dynamically and hold elements of different types.
Arrays, on the other hand, store values in contiguous memory locations, which ensures fast access using indexes but requires fixed size memory allocation.
Give ways to represent graphs
-Adjacency matrix
-Adjacency list
Give advantages of using adjacency matrices
Advantages:
Fast Edge Lookup:
-Checking whether an edge exists between two vertices is O(1), as it’s just a direct index access.
Simplicity:
-Easy to implement and understand, especially for dense graphs.
-Efficient for Dense Graphs:
Works well when the number of edges is close to the maximum possible (otherwise wasted memory space as it allocates space in memory for every possible edge in the graph even the ones that dont exist)
Give advantages of using adjacency lists
-Better to work with for small, sparse graphs
-No wasted memory space because it only allocates memory to the edges that exist within the graph (rather than all possible ones like with matrices)
What is meant by sparse graph?
A graph in which the number of edges is relatively SMALL compared to the number of POSSIBLE edges among the vertices.
(small edge to vertex ratio)
LESS EDGES
What is meant by a dense graph?
A graph in which the number of edges is relatively large compared to the number of POSSIBLE edges among the vertices.
(large edge to vertex ratio)
MORE EDGES
What is a stack?
-Last in first out (LIFO) data structure
-Can be implemented as a static or dynamic structure
-Used to reverse an action
-They are implemented using a pointer which points to the top of the stack
What is a queue?
-First in first out (FIFO) data structure
-Can use an array to implement it
-2 POINTERS one at the start and the other at the end of queue
Give a disadvantage of linear queues and why they aren’t effective at implementing queues
They can lead to inefficient memory usage due to the “wasted space” problem
In a linear queue, elements are added at the back and removed from the front . As items are removed, even tho the front of the queue technically moves forward, the space at the front is not reused.
Over time, the queue might reach the end of the allocated memory even if there’s free space at the beginning.
-To combat this: either shifting all elements to the front (which is inefficient) or setting a maximum size that limits the queue’s use ( so that the queue appears full).
So circular queues are preferred, as they allow the queue to wrap around and reuse the memory efficiently.
How do Circular queues work?
FIFO
Get around the ‘waste space’ problem from linear queues:
START
-Front Pointer: The front pointer typically starts at 0, because the first element in the queue will be added at index 0.
-Rear Pointer: The rear pointer also starts at 0 because initially, no items have been added yet. However, after adding the first element (enqueue), the rear pointer moves to 1.
END
-When the rear pointer reaches maxsize - 1, it wraps around to index 0, ensuring that the queue efficiently uses the available space.
What is meant by a subtree?
A subsection of a tree consisting of a parent and all the children of a parent
What is meant by a tree?
A data structure
-Its a simply connected graph with no loops or multiple edges
Formula for finding the number of edges in a tree
For n nodes there is n-1 edges
Formula for finding the number of nodes in a tree
For n edges there is n+1 nodes
What is a binary tree?
A type of tree
-Each node has a max of 2 child nodes
Give methods of traversing a binary tree
-Pre order
-In order
-Post order
-Pre order
-In order
-Post order
Are examples of?
Methods of traversing binary trees
Pre order traversal
Root left right
In order traversal
Left root right
Post order traversal
Left right root
Hash tables
A data structure
Its an array coupled with a hash function.
HF takes in an input (key) and produces an output (hash)
-Role of hash function is to map a key to its index
A good hashing function should have ….
a low probability of collisions
What is the role of a hash function?
To map a key(input) to an index (output) in the hash table
BOOLEAN ALGEBRA:
AND
Operation: Conjunction
Symbol: ^
BOOLEAN ALGEBRA:
OR
Operation: Disjunction
Symbol: V
BOOLEAN ALGEBRA:
NOT
Operation: Negation
Symbol: ¬
BOOLEAN ALGEBRA:
XOR
Operation: Exclusive disjunction
Symbol: ⊻
De Morgan’s law
Break negation (break the line), change the operator (change the sign)
DISTRIBUTION LAWS:
LAW OF CONJUNCTION OVER DISJUNCTION
A ^ (B v C) = (A ^ B) v (A ^ C)
DISTRIBUTION LAWS:
LAW OF DISJUNCTION OF CONJUNCTION
A v (B ^ C) = (A v B) ^ (A v C)
Commutative law
Shows that the order of literals doesnt matter
xy= yx
Associative law
Addition or removal of brackets and reordering of literals (variables) in a boolean expression
x(yz) = (xy)z = xyz
D type flip flops
A type of sequential logic circuit and memory unit which can store the value of one bit
The output can only change at a rising clock edge (which is the start of a clock tick)
It has 2 inputs: data and a clock
-A clock meaning a regular pulse generated by CPU used to coordinate the computer’s components
It has 2 outputs: Q and NOT Q
Explain the logic circuit of a D type flip flop
Uses 4 NAND gates
A D Type flip flop is an example of a…
Sequential logic circuit and memory unit
A flip-flop is a type of SEQUENTIAL logic circuit. While many logic circuits, like simple gates, are COMBINATIONAL.
What is the difference?
SEQUENTIAL= (flip-flops belong to the sequential category) their output depends on both current inputs and the past states (value that was previously stored) (i.e., they have memory).
COMBINATIONAL (like simple logic gates)= Their output depends only on the current inputs without any memory (eg A AND B where 0 AND 1 = 0)
In a D-type flip-flop, the output (Q) depends on…..
In a D-type flip-flop, the output (Q) depends on:
-The current input (D/Data)
-The clock signal: determines when the flip-flop samples the D input. The D-type flip-flop responds on the rising edge of the clock pulse (start of clock tick). This means that Q only updates when a rising clock edge occurs and if the value of D (past value) has also changed since the last clock pulse.
-Past state: The value that was previously stored when the last clock pulse was applied (the past state).
flip-flop holds its last output value until the next clock edge which continues as the output (Q) until the clock pulse triggers an update with a new D input value. => important as it allows digital systems to keep track of information over time, essential for building memory etc….
A D-type flip-flop is both a memory unit and a logic circuit. Explain this
Memory Unit: The D-type flip-flop functions as a single-bit memory storage device. Stores a bit of data by holding its output (Q) constant until it’s updated by the next clock pulse.
Logic Circuit: The D-type flip-flop is also a sequential logic circuit. Like other logic circuits, it takes inputs (D and clock) and produces outputs (Q and sometimes Q’).
-Outputs depend on input and past states
Sets of flipflops can be conbined to…
Form registers
As a single flipflop is a memory unit then multiple can form registers
What is meant by an ‘adder’?
A logic circuit used to perform the addition of binary numbers
-There are two types: half and full
What is a half adder?
Has two inputs ( A and B) and 2 outputs (Sum and Carry)
-Symbols XOR then AND
XOR for sum
AND for carry
*Its used to perform the addition of binary numbers. It takes binary inputs and produces a sum as output, often accompanied by a carry-out if the sum exceeds the maximum value that can be represented with the given number of bits.
What is a full adder?
Similar to half adder but has an additional input which is carry in. As it has this the circuits can be chained together to form a ripple adder (where the carry output from each stage ripples to the next stage (from one full adder to another)
-Uses 2 XOR gates, 2 AND gates and an OR gate
Sometimes a boolean expression is identical to another shorter expression. Its more desirable to use the shorter version. What can be used in order to simplify an expression?
Kaurnaugh Maps
-Can be used in a table with 2, 3 or 4… input variables
Ways of representing negative numbers in binary
-Twos compliment
-Sign magnitude
Floating point binary
Increasing mantissa=….
-With more bits, the mantissa can represent numbers more precisely, reducing rounding errors.
E.G. in a 4-bit mantissa: 1.101 (binary) may approximate a number, but a 6-bit mantissa like 1.10101 gives a closer representation.
-Smaller Gaps Between Numbers: A longer mantissa reduces the gap between two adjacent floating-point numbers.
What does the mantissa represent in floating point binary?
The mantissa holds the significant digits of the number. These digits determine the precission of the value being represented.
Give disadvantages of increasing the mantissa in floating point binary
Longer Mantissa: Increases precision but uses more memory
May slow computation due to the additional processing.
Give disadvantages of decreasing mantissa
Fewer bits lead to less precision, resulting in larger rounding errors.
-Smaller Gaps Between Numbers: A shorter mantissa increases the gap between two adjacent floating-point numbers.
Give disadvantages of using adjacency matrices
-An adjacency matrix allocates space for every possible edge between vertices, even those that don’t exist in the graph.
This results in a large amount of wasted memory, especially for sparse graphs (less edges)
-Not good for sparse graphs
Give disadvantages of using adjacency lists
Slower Edge Lookup:
-Checking whether an edge exists between two vertices can take O(V) in the worst case (linear search in the adjacency list of a vertex/search through the whole list)
-More Complex Implementation:
Slightly harder to implement compared to an adjacency matrix, especially for weighted graphs as a dictionary would have to be used
Formula for possible number of edges in a graph with n vertices
(1/2)n(n-1)
What is a static data structure?
A static data structure is a data structure with a fixed size, determined at the time of its creation.
Key Characteristics:
Size is predetermined: Cannot grow or shrink during runtime.
Memory allocation: Fixed memory is allocated at compile time.
Examples: Arrays (in most languages like C, Java, etc.).
Disadvantages:
Inflexibility: Cannot adapt to changing data requirements; may lead to wasted memory or insufficient storage.
Wasted space: If the reserved size is too large for the actual data.
Give advantages of using static data structures
Advantages:
Efficient access: Random access is often faster because memory locations are contiguous.
-Memory is allocated at compile-time, no overhead during runtime for storing pointers and allocation and deallocation
Give disadvantages of using static data structures
-Inflexibility: Cannot adapt to changing data requirements; may lead to wasted memory or insufficient storage.
So Wasted space: If the reserved size is too large for the actual data.
Give advantages of using dynamic data structures
-No wasted space in memory as space is allocated when needed
Give disadvantages of using dynamic data structures
-Implementation is more challenging, requiring careful management of memory (e.g., pointers in linked lists).
-Overhead: Dynamic memory allocation may introduce runtime overhead due to pointers and repeated allocations or reallocations, potentially slowing performance.
-Risk of fragmentation due to constant allocation and deallocation
What are the logic gates used in a full adder?
-Uses 2 XOR gates, 2 AND gates and an OR gate
What is meant by a primitive data type?
A primitive data type is a basic, predefined type of data that is built into a programming language.
It represents the simplest form of data that cannot be broken down into smaller components.
(int, bool, char, string, double/float)
Why would you use linear search over binary search?
If the data is not in any order // binary search requires the
data to be in order
* When the number of items to search is small
