1.4 Data types, data structures and algorithms

Question 1

What are the different types of data? (5)

Answer 1

-integer
-boolean
-real/floating point
-character
-string

Question 2

What is an integer data type?

Answer 2

whole numbers (includes 0 and -ve numbers)

Question 3

What is a boolean data type?

Answer 3

values which are restricted to true and false

Question 4

What is a real/floating point data type?

Answer 4

+ and -ve numbers which can also be fractional/decimal numbers

Question 5

What is a character data type?

Answer 5

a single symbol used by the computer
-include the letters A to Z, the numbers 0 to 9 and hundreds of symbols like % and £

Question 6

What is a string data type?

Answer 6

a collection of characters

Question 7

How are integers stored on computers? How does this work?

Answer 7

-stored using binary
-computers count in base 2
-0 is just to show an ‘empty space’ whereas the 1 shows the number which the integer will consist of [0= false, 1=true]

128 64 32 16 8 4 2 1
-the row above shows the place value of each digit of the number (remember computers count in base 2 e.g. 2^2, 2^3)

-if the binary code beneath consists of 1 then the integer will be made up of the place value above the 1
e.g.
128 64 32 16 8 4 2 1
0 1 0 0 1 1 0 1

64+ 8 +4 +1 = 77

Question 8

Explain how we can convert the binary code into denary

Answer 8

128 64 32 16 8 4 2 1
0 1 0 0 1 1 0 1

-the row below is the binary code which can be converted into an integer by adding the numbers which have a value of 1

-in this case we add 64, 8, 4 and 1 as they have a place holder value of 1 which gives a number of 77

Question 9

Explain how we can convert denary into binary code

Answer 9

-first step: find the largest power of two which is smaller than the number you’re converting, then write up the place values in power of 2 up to this power
e.g. , if we were converting the decimal 47 into binary, we would write out place values up to 32

32 16 8 4 2 1

-then, place a 1 or a 0 in each position so that the total adds up to 47 starting with the most significant bit (32)
-if we write a 1, then we subtract the place value from
our value and use the result for the next stage e.g. 47-32= 15
-as 16 is larger than 15 a 0 will be used as an empty space/false number so we move on to the next numbers and continue the steps until we reach the final bit and the number is complete

32 16 8 4 2 1
1 0 1 1 1 1

Question 10

What are the four rules when adding binary code?

Answer 10

1. when adding 0 + 0 it always gives a 0
2. when adding a 0 + 1 it always gives a 1
3. when adding 1 + 1 you carry the one to the next addition and instead place a zero
4. when adding a 1 +1 + 1 you carry the one to the next addition and instead place a 1

Question 11

How do we add binary code together?

Answer 11

-line up digits
-start from right hand side (least significant bit)
-add values from each column whilst following the rules
-if the value has an overflow error (having an extra digit at the end), write out the code with the extra digit noting the error
-convert value into denary to check if calculation is correct

Question 12

What are the two methods which can represent negative numbers in binary?

Answer 12

-sign and magnitude
-two’s complement

Question 13

Explain how sign and magnitude works

Answer 13

-equivalent of adding a + or - sign in front of a number
-binary can only use 0s and 1s, so instead we represent the signs using 0 as positive and 1 as negative.

e.g. [010101101] = 173
[110101101] = -173

Question 14

How can we convert from sign and magnitude into denary and vice versa?

Answer 14

-same as converting normally from binary to denary and vice versa
-only difference is adding the sign at the end of the largest significant bit for binary and adding a +/- to a denary number

Question 15

Explain how two’s complement works

Answer 15

-works by making the most significant bit negative e.g., the most significant bit, usually 128, represents -128
-add place values as normal
e.g.,
-128 64 32 16 8 4 2 1
1 1 1 1 1 0 0 1
so: -128 + 64 + 32 +16 + 8 +1= -7

Question 16

How can we add binary numbers using two’s complement?

Answer 16

-flip the first number (all 0s turn to 1 and vice versa)
-add as a normal binary

Question 17

What is hexadecimal?

Answer 17

makes use of the characters A-F to represent numbers 10-15

Question 18

Show the conversions between denary and hexadecimal

Answer 18

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 <—-DENARY
0 1 2 3 4 5 6 7 8 9 A B C D E F <—-HEXADECIMAL

Question 19

How do we convert hexadecimal into binary and vice versa?

Answer 19

B2
-split into two characters –> B 2
-convert both into denary –> 11 2
-convert denary into binary
-combine both binary sections into one

-for vice versa, split the binary into sections of 4 bits and do the opposite

Question 20

How do we convert hexadecimal into denary and vice versa?

Answer 20

-first convert hexadecimal into binary
-convert binary into denary

-do opposite for vice versa

Question 21

How can floating point numbers be shown in binary?

Answer 21

-can be split into two parts: mantissa and exponent
e.g., 6.63 x 10^-11
mantissa is 6.63 and exponent is -11

-the last bit next to the most significant bit shows the sign (remember 0 is positive and 1 is negative sign)

Question 22

How does the mantissa and exponent work in binary?

Answer 22

-the mantissa is always taken to have the binary point (same as a decimal point)
[as the mantissa is considered a binary point the binary number e.g. 1100100111 becomes 1.100100111]

-the exponent is used to show the shift of how many places the decimal point moves and in which direction

-mantissa comes first then the exponent (which will also have the smaller bytes)

e.g. 6.63 x 10^-11
mantissa is 6.63 and the exponent is -11
so the decimal point will be shifted 11 times from the decimal point to give us 0.0000000000663

Question 23

How do we convert the a floating point number into denary?

Answer 23

-convert exponent into denary using the normal method
-as the mantissa is considered a binary point the binary number e.g. 1100100111 becomes 1.100100111
-move the binary point the required number of places that the exponent gives (e.g. moving the binary point 5 places to the right of the mantissa)

-this mantissa can then be converted to the denary version
[REMEMBER for the place values in decimal, the computer counts in base 2s so it goes on as 2^-1, 2^-2 etc)

[REMEMBER WITH TWO’S COMPLEMENT IF THE INIRIAL BIT IS A NEGATIVE THE MOST SIGNIFICANT PLACE VALUE IS A NEGATIVE]
e.g.
32 16 8 4 2 1 . 0.5 0.25 0.125 0.0625
1 1 0 0 1 0 . 0 1 1 1

32 + 16 + 2 + 0.25 + 0.125 + 0.0625 = 50.4375

Question 24

Give the decimal place values for binary. Explain how we get these numbers

Answer 24

0.5
0.25
0.125
0.0625

[REMEMBER for the place values in decimal, the computer counts in base 2s so it goes on as 2^-1, 2^-2 etc)

Question 25

What does it mean if we normalise floating point numbers? What is shown to present a floating point number as normalised?

Answer 25

-making them precise as possible in a given number of bits -to normalise a binary number, adjust it so that it starts 01 for a positive number or 10 for a negative number

Question 26

How can we normalise a floating point number?

Answer 26

-check if it is a positive or negative number -split the number into its mantissa and exponent -adjust the mantissa so it starts in 01 (for +) or 10 (for -) -to adjust the mantissa to create a normalised number, move bits to the required number to the left and add zeros to the end of the mantissa -then adjust the exponent so you still remain with the same number (as we move the bits to the left the mantissa becomes larger so we need to reduce the exponent by the number of bits moved) e.g. if we move the bits two places to the left we subtract the exponent by two and replace it with what has been left -----> 5 - 2 = 3 so the new exponent would be three

Question 27

How do we add floating point numbers?

Answer 27

-the exponents need to be the same -add mantissa's together -normalise answer if needed if the exponents are not the same, they need to be modified to match -to do this, we shift the bits of the mantissa to the right to the needed number of places until the exponent is modified to match the other (same as when we normalise)

Question 28

How can we subtract floating point numbers?

Answer 28

-make exponents the same -the number which will be subtracted from the first needs to be flipped (converted to two's complement) -add both numbers together -normalise answer if needed if the exponents are not the same, they need to be modified to match -to do this, we shift the bits of the mantissa to the right to the needed number of places until the exponent is modified to match the other (same as when we normalise)

Question 29

What is a logical shift?

Answer 29

involves moving all of the bits in a binary number a specified number of places to the right or to the left

Question 30

What happens to the number if a logical shift occurs?

Answer 30

multiplication (or division if shifting right) by two to the power of the number of places shifted

Question 31

What are the different masks that can be applied to binary calculations?

Answer 31

AND OR XOR

Question 32

What does the AND mask do to a binary calculation?

Answer 32

all values must be true (1= true, 0 = false) e.g. if a calculation involves 1 and 0 the result would be 0 if a calculation involves 1 and 1 the result would be 1 if there is a false then the answer would be false

Question 33

What does the OR mask do to a binary calculation?

Answer 33

only one value needs to be true (1= true, 0 = false) e.g. if a calculation involves 1 and 0 the result would be 1

Question 34

What does the XOR mask to do a binary calculation?

Answer 34

works the same as OR where the result is true if the calculation consists of 1 (1= true, 0 = false) both values cannot be the same: the value must consist of 1 and 0

Question 35

What is a character set?

Answer 35

a published collection of codes and corresponding characters which can be used by computers for representing text

Question 36

What are two types of character sets?

Answer 36

ASCII Unicode

Question 37

Describe the ASCII character set

Answer 37

-stands for American Standard Code for Information Interchange -7 bits to represent 2^7 = 128 different characters -capital letters A-Z are represented by codes 65-90 while the lower case letters a-z correspond to codes 97-122

Question 38

What is one issue that arose from using ASCII? What was used to fix this?

Answer 38

-became a disadvantage when computers needed to represent other languages with different characters -Unicode was introduced to solve this

Question 39

Describe the Unicode character set

Answer 39

-uses a varying number of bits allowing for over 1 million different characters -has enough capacity to represent a wealth of different languages, symbols and emoji

Question 40

What is an array? Describe its characteristics

Answer 40

-a data structure -an ordered, finite set of elements of a single data type -usually zero indexed unless told otherwise can be 1D, 2D, 3D

Question 41

What can a 1 dimensional array be called? Give an example

Answer 41

a linear array e.g. oneDimensionalArray = [1, 23, 12, 14, 16, 29, 12] //creates a 1D array print(oneDimensionalArray[3]) >> 14

Question 42

Describe a 2 dimensional array. Give an example

Answer 42

-can be visualised as a table or spreadsheet -when searching through a 2D array, you first go down the rows and then across the columns to find a given position e.g. twoDimensionalArray = [[123, 28, 90, 38, 88, 23, 47],[1, 23, 12, 14, 16, 29, 12]] print(twoDimensionalArray) >> [[23, 28, 90, 38, 88, 23, 47], [ 1, 23, 12, 14, 16, 29, 12]] print(twoDimensionalArray[1,3]) // Goes down and then across >> 14

Question 43

Describe a 3 dimensional array. Give an example

Answer 43

-can be visualised as a multi-page spreadsheet and can be -in a 3D array requires the following syntax to be used: threeDimensionalArray[z,y,x], where z is the array number, y is the row number and x is the column number e.g. threeDimensionalArray = [[[12,8],[9,6,19]],[[241,89,4,1],[19,2]]] print(threeDimensionalArray[0,1,2]) >> 19

Question 44

What is a record?

Answer 44

-a data structure -commonly referred to as a row in a file -made up of fields

Question 45

What is a list?

Answer 45

-a data structure consisting of a number of ordered items where the items can occur more than once -list values are stored non-contiguously (means they do not have to be stored next to each other in memory) -can also contain elements of more than one data type

Question 46

What are the different operations used for lists? (9)

Answer 46

isEmpty() append(value) remove (value) search(value) length() index(value) insert(position, value) pop() pop(position)

Question 47

What are the two differences between an array and a list?

Answer 47

-lists store data non-contiguously whereas arrays store data in order -lists can store more than 1 data type

Question 48

What does the isEmpty() command do for a list? Give an example

Answer 48

checks if the list is empty List.isEmpty() >> False

Question 49

What does the append(value) command do for a list? Give an example

Answer 49

adds a new value to the end of the list List.append(15) >>

Question 50

What does the remove(value) command do for a list? Give an example

Answer 50

removes the value the first time it appears in the list List.remove(23) >>

Question 51

What does the search(value) command do for a list? Give an example

Answer 51

searches for a value in the list List.search(38) >> False

Question 52

What does the length() command do for a list? Give an example

Answer 52

returns the length of the list List.length() >> 7

Question 53

What does the index(value) command do for a list? Give an example

Answer 53

returns the position of the item List.index(23) >> 0

Question 54

What does the insert(position, value) command do for a list? Give an example

Answer 54

inserts a value at a given position List.insert(4,25) >>

Question 55

What does the pop() command do for a list? Give an example

Answer 55

returns and removes the last value in the list List.pop() >>12

Question 56

What does the pop(position) command do for a list? Give an example

Answer 56

returns and removes the value in the list at the given position list.pop(3)

Question 57

What is a tuple?

Answer 57

-a data structure -an ordered set of values of any type is called a tuple -a tuple is immutable (cannot be changed) -uses normal brackets instead of square

Question 58

How can a tuple be accessed? Give an example

Answer 58

-accessed in the same way as an array tupleExample = (“Value1”, 2, “Value3”) print(tupleExample[0]) >> Value1

Question 59

What are two differences between a tuple and an array?

Answer 59

-elements cannot be added or removed once it has been created (will result in a syntax error) -initialised using regular brackets instead of square brackets

Question 60

What is a linked list?

Answer 60

a dynamic data structure used to hold an ordered sequence which are not stored in contiguous locations

Question 61

What is each item in a linked list called?

Answer 61

nodes

Question 62

What does each node in a linked list contain?

Answer 62

contains a field data and an address field called link/pointer

Question 63

What is a data field in a linked list?

Answer 63

a field that stores the actual data

Question 64

What is the pointer field in a linked list?

Answer 64

a field that contains the address of the next node in the list

Question 65

How does a linked list work? Give an example

Answer 65

Index Data Pointer 0 ‘Linked’ 2 1 ‘Example’ 0 2 ‘List’ - 3 Start = 1 NextFree=3 to start, the algorithm will provide a start pointer (1) as well as the next free space (3) -start with 1, to get 'example' as the first data item -the pointer is showing to go to index 0 which outputs the values at each node -this then gives a pointer to index 2 which gives the next value -this doesn't have another pointer as there is no other value occupying the next available space by following the algorithm we end up with 'example' , 'linked' , 'list'

Question 66

What is one advantage of using a linked list? How does this work? Give an example

Answer 66

values can easily be added or removed by editing pointers adding: done by adding the value at the end of the linked list and updating the pointer e.g. index data pointer 3 ‘OCR’ 4 Start = 1 NextFree=4 removing: rearrange the pointers so that the value wanting to e removed wont be called upon and therefore not in use e.g. index data pointer 0 ‘Linked’ 2 1 ‘Example’ 2 2 ‘List’ - this will leave out 'linked' and instead give 'example' , 'list' -if needed, update other pointers so the algorithm works properly without any mix up of values

Question 67

What is one disadvantage when trying to remove a value from a linked list?

Answer 67

the value isn't fully removed, only ignored which wastes memory

Question 68

What are two differences between a linked list and an array?

Answer 68

-storing pointers means more memory is required compared to an array -as items in linked lists are stored in a sequence, they can only be transported in this order so an item cannot be directly accessed, as is possible in an array

Question 69

What is a graph?

Answer 69

-a data structure -a set of vertices/nodes connected by edges/arcs

Question 70

What are the three categories of graphs? Describe them

Answer 70

directed graph: the edges can only be traversed in one direction undirected graph: the edges can be traversed in both directions weighted graph: a cost is attached to each edge

Question 71

How can computers process graphs?

Answer 71

by using an adjacency matrix or an adjacency list

Question 72

What are positives of an adjacency matrix and an adjacency list?

Answer 72

adjacency matrix: -convenient to work with due to quicker access times -easy to add nodes adjacency list: -more space efficient for large, sparse networks

Question 73

What is a stack? How does it work?

Answer 73

-a last in first out (LIFO) data structure -items can only be added to or removed from the top of the stack

Question 74

Give two examples of where stacks may be used?

Answer 74

-back button in a web page -undo button

Question 75

How are stacks implemented?

Answer 75

implemented using a pointer which points to the top of the stack, where the next piece of data will be inserted

Question 76

What are the two data structures stacks can be used as? Which is preferred and why?

Answer 76

-implemented as either a static structure or a dynamic structure -when maximum size is required, static stacks are preferred, as they are easier to implement and make more efficient use of memory

Question 77

What are the 6 types of stack operations?

Answer 77

isEmpty() push(value) peek() pop() size() isFull()

Question 78

What does the isEmpty() command do for a stack? Give an example

Answer 78

-checks if the stack is empty -works by checking the value of the top pointer Stack.isEmpty() >> True

Question 79

What does the push(value) command do for a stack? Give an example

Answer 79

-adds a new value to the end of the list -needs to check that the stack is not full before pushing to the stack Stack.append(“Nadia”) >> Stack.append(“Elijah”) >>

Question 80

What does the peek() command do for a stack? Give an example

Answer 80

-returns the top value from the stack -first checks the stack is not empty by looking at value of top pointer Stack.peek() >> “Elijah”

Question 81

What does the pop() command do for a stack? Give an example

Answer 81

-removes and returns the top value of the stack -first checks the stack is not empty by looking at value of top pointer Stack.pop() >> “Elijah”

Question 82

What does the size() command do for a stack? Give an example

Answer 82

returns the size of the stack Stack.size() >> 2

Question 83

What does the isFull() command do for a stack? Give an example

Answer 83

-checks if the stack if full and returns a Boolean value -works by comparing stack size to the top pointer Stack.isFull() >> False

Question 84

What is a queue? How does it work?

Answer 84

-a first in first out (FIFO) data structure -items are added to the end of the queue and are removed from the front of the queue

Question 85

Give three examples of where queues may be used in

Answer 85

-printers -keyboards -simulators

Question 86

What is a linear queue? How does it work?

Answer 86

-a data structure consisting of an array -items are added into the next available space in the queue, starting from the front -items are removed from the front of the queue

Question 87

How are pointers used in a queue?

Answer 87

-make use of two pointers -one pointing to the front of the queue -one pointing to the back of the queue, where the next item can be added

Question 88

Why can a linear queue be ineffective to use? How can we fix this?

Answer 88

-as the queue removes items, there are addresses in the array which cannot be used again -this makes a linear queue an ineffective implementation -use a circular queue to fix this

Question 89

What is a circular queue? How does it work to fix the issue with a linear queue?

Answer 89

-a queue which operates in a similar way to a linear queue in that it is a FIFO structure -coded in a way that once the queue’s rear pointer is equal to the maximum size of the queue, it can loop back to the front of the array and store values here, provided that it is empty -therefore, circular queues can use space in an array more effectively

Question 90

What are the four different stack commands?

Answer 90

enQueue(value) deQueue() isEmpty() isFull()

Question 91

What does the enQueue(value) command do? Give an example

Answer 91

-adds a new item to the end of the queue -increments the back pointer Queue.enQueue(“Nadia”) >> Queue.enQueue(“Elijah”) >>

Question 92

What does the deQueue() command do? Give an example

Answer 92

-removes the item from the front of the queue -increments the front pointer Queue.deQueue() >>

Question 93

What does the isEmpty() command do for a queue? Give an example

Answer 93

checks if the queue if empty by comparing the front and back pointer Queue.isEmpty() >> False

Question 94

What does the isFull() command do for a queue? Give an example

Answer 94

checks if the queue is full by comparing the back pointer and queue size Queue.isFull() >> False

Question 95

What is a tree?

Answer 95

-a data structure -has a root node and child node which are connected by branches -is a connected form of a graph

Question 96

What is a node (for a tree data structure)?

Answer 96

an item in the tree

Question 97

What is an edge (for a tree data structure)?

Answer 97

connects two nodes together and is also known as a branch, or arc

Question 98

What is a root (for a tree data structure)?

Answer 98

a single node which does not have any incoming nodes

Question 99

What is a child (for a tree data structure)?

Answer 99

a node with incoming edges

Question 100

What is a parent (for a tree data structure)?

Answer 100

a node with outgoing edges

Question 101

What is a subtree?

Answer 101

subsection of a tree consisting of a parent and all the children of a parent

Question 102

What is a leaf (for a tree data structure)?

Answer 102

a node with no children

Question 103

What is a binary tree? What are they used for?

Answer 103

-a type of tree where each node has a maximum of two children -used to search for values quickly such as representing information for binary searches

Question 104

What are the three ways we can traverse through a binary tree?

Answer 104

-pre-order -in-order -post-order

Question 105

How does pre-order traversing work?

Answer 105

-follows the order: root node, left subtree, then right subtree -nodes are traversed in the order in which you pass them on the left, beginning at the left-hand side of the root node

Question 106

How does in-order traversing work?

Answer 106

-follows the order: left subtree, root node, right subtree -nodes are traversed in the order in which you pass under them, beginning at the first node from the left which does not have two child nodes

Question 107

How does post-order (depth first) traversing work?

Answer 107

- follows the order: left subtree, right subtree, root node -nodes are traversed in the order in which you pass them on the right

Question 108

What is a hash table?

Answer 108

-an array which is coupled with a hash function

Question 109

How does a hash table work?

Answer 109

-the hash function takes in data (a key) and releases an output (the hash) -the role of the hash function is to map the key to an index in the hash table

Question 110

What is a collision (hashing)? How can we solve this issue?

Answer 110

-two keys producing the same hashed value -if this occurs, the item is typically placed in the next available location

Question 111

What properties does a good hashing algorithm have?

Answer 111

-has a low chance of collision -must be fast

Question 112

How can problems in boolean equations be solved?

Answer 112

by using boolean logic

Question 113

What are the only two solutions a boolean equation can equate to?

Answer 113

true or false

Question 114

What are the four operations which can be used for boolean equation?

Answer 114

-conjunction (AND) -disjunction (OR) -negation (NOT) -exclusive disjunction (XOR)

Question 115

What is the symbol for conjunction? What can it also be called?

Answer 115

^ also known as AND

Question 116

What is the symbol for disjunction? What can it also be called?

Answer 116

v also known as OR

Question 117

What is the symbol for negation? What can it also be called?

Answer 117

¬ also known as NOT

Question 118

What is the symbol for exclusive disjunction? What can it also be called?

Answer 118

⊻ also known as XOR

Question 119

Draw a diagram showing all the logic gates for the four operations

Answer 119

https://spinningnumbers.org/i/logic11.svg

Question 120

What is a truth table? How are the inputs and outputs represented?

Answer 120

-a table showing every possible arrangements of inputs to a logic gate and the corresponding output -inputs are usually labelled A, B, C etc -1 represents True, 0 represents False

Question 121

How are boolean equations made? Give an example and explain how to solve it

Answer 121

made by combining boolean operators -e.g. ¬(A ^ (B v C)) -first do the equation in the first bracket---> B v C -work out the next bracket---> A ^ (B v C) -then apply the negation to the answer -this could be carried out using truth tables

Question 122

How can we simplify boolean expressions?

Answer 122

by using karnaugh maps

Question 123

How do karnaugh maps work?

Answer 123

-they create tables filled corresponding to the expression's truth table -can be used for a truth table with two, three or four variables -use the bits for each column and row and apply the operation

Question 124

How can we simplify an expression using a karnaugh map? Show an example

Answer 124

-first write your truth table as a Karnaugh map -then highlight all of the 1s in the map with a rectangle -the larger the rectangle you can highlight at once the better -only groups of 1s with edges equal to a power of 2 (1, 2 or 4 in a row) can be highlighted, wraparound is included -remove variables which change within these rectangles from the expression -keep variables which do not change, but negate to become True if required https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcROPkC5L7D_3lwHMAcnkYks-WVR7mfrPeMbWA&usqp=CAU

Question 125

What are the four laws to simplify boolean algebra?

Answer 125

-De Morgan's Laws -distribution -association -commutation -double negation

Question 126

How does De Morgan's Law work and when is it used? Give an example

Answer 126

-involve breaking UP negation (NOT) and changing the operator between two literals -used when negation (NOT) applies to the whole of the operator between the two literals -the AND symbol would also be replaced by the OR symbol and vice versa e.g. ¬(A ^ B) == ¬A v ¬B ¬(A v B)== ¬A ^ ¬B

Question 127

How does distribution work and when is it used? Give an example

Answer 127

-applies when conjunction (AND) is used with another operator that contains disjunction (OR) and vice versa -can also be used with the same operator e.g. A ^ (B v C) == (A ^ B) v (A ^ C) A v (B ^ C) == (A v B) ^ (A v C)

Question 128

How does association work? Give an example

Answer 128

-involves the addition or removing of brackets and reordering of literals in a boolean expression e.g. (A ^ B) ^ C == A ^ B ^ C (A v B) v C == A v B v C

Question 129

How does commutation work? Give an example

Answer 129

-shows that the order of literals around an operation do not matter e.g. A v B == B v A A ^ B == B ^ A

Question 130

How does double negation work? Give an example

Answer 130

-if negation on a literal is used twice, they cancel out and remain the same truth value e.g. ¬¬A == A

Question 131

What are three types of logic circuits?

Answer 131

-D-type flip flops -half adders -full adders

Question 132

Describe what a D-type flip flop is

Answer 132

-a type of logic circuit which can store the value of one bit -has two inputs, a control signal and a clock input (a regular pulse generated by the CPU to coordinate the computers' components)

Question 133

How does a D-type flip flop circuit work? Draw a diagram

Answer 133

-clock pulse rises and falls -edges can be classified rising or falling -the output of a D-type flip flop can only change at a rising edge, the start of a clock tick -uses four NAND gates -updates the value of Q to the value of D whenever the clock (CLK) rises -the value of Q is the stored value e.g. https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2017/01/D-logic-diag.png

Question 134

Describe what an adder is

Answer 134

-a logic circuit which adds together the number of inputs which are true and outputs the number in binary

Question 135

How does a half adder work? Draw a diagram

Answer 135

-has two inputs, A and B -has two outputs, Sum and Carry -formed from two logic gates: AND and XOR -when both A and B are False, both outputs are False -when one of A or B is True, Sum (S) is True -when both inputs are True, Carry (C) is True e.g. https://media.geeksforgeeks.org/wp-content/uploads/20201009113450/outputonlinepngtools3.png https://www.techopedia.com/wp-content/uploads/2023/03/9097e01b7bfd4e8dbf671dcfa129beae.png

Question 136

How does a full adder work? Draw a diagram

Answer 136

-similar to a half adder, but has an additional input -allows carry in to be represented -formed from two XOR gates, two AND gates and an OR gate can be chained together to form a ripple adder with many inputs e.g. https://www.watelectronics.com/wp-content/uploads/Full-Adder-Truth-Table.jpg https://circuits-diy.com/wp-content/uploads/2021/08/full-adder-circuit.png