# Set 7 Flashcards

1
Q

What is important about the components of a vector?

A

That they are all drawn from the same field of values, e.g Reals or Rationals

2
Q

Give four ways vectors be represented

A
• A list of values
• A one-dimensional array
• A dictionary (if the vector can be considered to represent a function)
• Visually (using an arrow)
3
Q

How can a vector be represented in code if the vector is viewed as a function?

A

A dictionary

4
Q

A

Translation

5
Q

What does scalar-vector multiplication achieve?

A

Scaling

6
Q

What is another name for dot product?

A

Scalar product

7
Q

What is a convex combination of vectors u and v?

A

αu + βv

such that α , β >= 0
and α + β = 1

8
Q

What is the scalar product of vectors: A = (a1,a2) and B = (b1,b2)

A

A.B = a1b1 + a2b2

9
Q

What is an application of the dot product?

A

Finding the angle between two vectors

10
Q

In a convex combination of u and v, what is the significance of α = β = 0.5?

A

The resultant vector is the midpoint of the position vectors u and v

11
Q

When might it be appropriate to represent a vector using a dictionary?

A

If the vector is used to represent a function

12
Q

What is a set?

A

A set is an unordered collection of values in which each value occurs at most once

13
Q

What does proper subset mean? What is its symbol?

A
• Equality not allowed
• (a set is a subset of itself but not a proper subset of itself)
14
Q

A\B

A

Set difference between A and B

15
Q

What is a finite set?

A

One whose elements can be counted off by natural numbers up to a particular number

16
Q

What is the Cartesian product of A and B?

A

The set of all ordered pairs (a, b) where a is a member of A and b is a member of B.

17
Q

What can the Cartesian product be used for?

A

Defining function types

18
Q

What is a countable set?

A

A set with the same cardinality as some subset of the natural numbers

19
Q

What are regular expressions?

A

Metalanguage for defining all valid strings of a regular language

20
Q

What is the purpose of regular expressions?

A

Allow for regular languages to be described in a convenient shorthand notation

21
Q

What is the RegEx metacharacter for: zero or more

A

*

22
Q

What is the RegEx metacharacter for: one or more

A

+

23
Q

RegEx : zero or one lots of

A

?

24
Q

What are | ? * + called in RegEx?

A

Metacharacters

25
Q

Context free languages are a __________ of regular languages

A

Superset

26
Q

Why are context-free languages needed? (2*)

A
• RegEx doesn’t have enough expressive power
• This is because regular languages can be expressed in terms of a finite state machine, and a finite state machine only has finitely many states
27
Q

What is BNF?

A
• Backus-Naur form
• A metalanguage for describing the syntax used by a context-free language
28
Q

General statement in BNF

A

LHS ::= RHS

29
Q

What is a function?

A
• A function is a mapping of values from a domain to a set of values from a co-domain.
• Not all of the co-domains members needs to be outputs.
30
Q

Notation for “the set difference between sets A and B”

A

A\B

31
Q

Set comprehension for all even natural numbers less than 10

A

{2x | x ∈ ℕ ∧ x<5}
(| means such that, ∧ means AND)

32
Q

What sorts of strings match {0ⁿ1ⁿ| n ≥ 1}

A

{ 01, 0011, 000111, 00001111, … }

33
Q

How can you identify normalised floating point numbers?

A

Mantissa must begin with 01 or 10

34
Q

Give two advantages of normalisation of floating point numbers

A
1. It maximises precision for a given number of bits
2. It ensures that there is a unique representation of each number, making it simpler to test for equality of numbers
35
Q

If the exponent of a number is negative, what do you need to do to the mantissa when converting from binary to decimal?

A

Fill in with 0s if the leftmost bit is a 0, and fill in 1s if its a 1.

36
Q

Advantages of fixed point binary numbers

A
• More representable numbers, as numbers don’t need to be normalised
• Maximum precision for the given number of bits
• Can be simpler, and faster, to work with
37
Q

Give three advantages of floating point numbers

A
• Can represent a much larger range of numbers
• The trade-off between range and precision can be tailored to the context the system is being used in
• Additional non-numeric values can be represented using the unnormalised range (e.g. NaN, infinity)
38
Q

What is meant by the precision of a binary number?

A

The maximum number of significant digits that can be represented in a number format.

39
Q

When the result of an arithmetic operation is a real number (e.g. pi), what options are there for storing it in binary?

A
• Rounding to the nearest representable value
• Truncating
40
Q

What is absolute error?

A

The difference between the actual value and the nearest representable value

(always positive)

41
Q

What is relative error?

A

The absolute error ÷ the actual value
(could be given as 0.05, 1/20 or 5%)

42
Q

When does overflow occur?

A

When a number is too large to be represented using the available number of bits

43
Q

When does underflow occur?

A

When a number is too small to be represented using the available number of bits

44
Q

What is a bitmapped graphic made of?

A

A grid of pixels

45
Q

What is a pixel?

A
• Pixel is short for picture element
• It is the smallest addressable area of an image
46
Q

What is colour depth?

A

The number of bits used to represent the colour of a single pixel in a bitmap image

47
Q

What determines the minimum colour depth?

A

The number of different colours that need to be used in an image

48
Q

What is the image size in pixels?

A

(image width in pixels) * (image height in pixels)

49
Q

What is the image resolution measured in?

A

dots per inch (ppi)

50
Q

How do you calculate image file size? (ignoring metadata)

A

file size
= (image size in pixels) x colour depth
= (image width in pixels) x (image height in pixels) x colour depth

51
Q

Give five examples of metadata for a bitmap image

A
• Image width in pixels
• Image height in pixels
• Colour depth
• File format
• Geographical location of creation
52
Q

How are vector graphics stored?

A
• Images are described using a list of objects.
• The properties of each object in the vector graphic image are also stored as a list
53
Q

Give five examples of properties of objects in a vector graphic image

A
• Coordinates of object
• Shape
• Border colour
• Fill colour
• Border thickness
54
Q

Give three advantages of vector graphics

A
1. Vectors can be enlarged without distortion, whereas bitmapped graphics can look pixelated when the size changes
2. In general, vector graphics tend to result in smaller file sizes. Especially when they are composed of relatively simple geometric shapes
3. It is much simpler to create and edit vector graphic images as each object in a vector graphic can be adapted independently by accessing its set of attributes
55
Q

What is the advantage of bitmapped graphics?

A
• The variety of images that can be created by the geometric shapes implemented by vector graphics is limited.
• On the other hand, bitmapped graphics can depict almost any level of complexity and detail.
• Photographs are always stored as bitmaps.
56
Q

What are vector graphics mostly used for?

A

Illustrations and logos

57
Q

What does MIDI stand for?

A

Musical Instrument Digital Interface

58
Q

Describe what MIDI is and what its purpose is

A
• MIDI is a technical standard that describes
1. A protocol
2. Digital interface
3. Standard set of connectors
• MIDI allows for a wide range of electronic musical instruments to communicate with each other so as to manipulate music
59
Q

Describe the use of event messages in MIDI. Include examples of event messages.

A

Event messages are a list of instructions that specify how the music should be played. For example
- Note on / note off
- Pitch
- Volume
- Instrument
- Vibrato

60
Q

Give three advantages of using MIDI files for representing music

A
• A MIDI file provides a more compact representation of sound, often leading to MIDI files using far less storage than an equivalent sampled recording.
• The performance data can be easily manipulated (e.g. duration of a note can be changed, or even an entire instrument)
• No information about a note is lost through sampling
61
Q

Difference between analogue data and digital data

A
• Analogue ​data is ​continuous​, there are ​no limits​ to the values that the data can take
• Digital data is ​discrete​, meaning that it can only take ​particular values​.
62
Q

Where do ADCs get the analogue signal from?

A

Analogue sensors

63
Q

Most common use for a DAC?

A

Converting a digital audio signal to an analogue audio signal

64
Q

Why are files compressed?

A
• To reduce their size
• Smaller files can be transferred faster between storage devices or over the internet
65
Q

What is lossy compression?

A
• When the file is compressed, there is loss of information from the original version.
• When decompressed, the file will be lower quality than the original
66
Q

Name two methods of lossless compression

A
• Run length encoding
• Dictionary-based compression
67
Q

How does run length encoding work?

A

RLE reduces the size​ of a file by removing ​repeated information​ and replacing it with ​one occurrence ​of the repeated information followed by the number of times​ it is to be repeated

68
Q

When are RLE and dictionary-based compression most effective?

A

On files that contain a lot of repeated data

69
Q

True or False: relative error is always given as positive

A

True (in this A-level)

70
Q

What is sampling rate measured in?

A

Hertz

71
Q

What does Nyquist’s theorem state?

A

The sampling rate must be at least double the highest frequency present in the signal

72
Q

What is the advantage of lossless compression?

A

The size of a file can be reduced without decreasing its quality (there is no loss of information)

73
Q

What is the key difference between lossy and lossless compression?

A

Lossy : original data cannot be recovered. lossy compression cannot be reversed

Lossless : original data can be fully recovered. lossless compression can be reversed

74
Q

Describe how dictionary-based compression could be used on a paragraph of text

A
1. Each word in the text is allocated a shorter code
2. The paragraph is then represented as a sequence of these codes
3. The dictionary containing the repeated data is appended to the file
75
Q

What is a bit?

A
• The fundamental unit of information
• A bit is either 0 or 1
76
Q

If the actual number is A, but B is stored, what is the absolute error?

A

|A-B|
absolute error is positive

77
Q

Describe the principles of operation of an ADC

A
• Analogue signal is sampled at regular time intervals
• Amplitude of signal at each sample point measured
• Measurement is coded into a fixed number of bits
78
Q

How are logic gates used in a half-adder?

A

XOR for S(um)
AND for C(arry)

79
Q

What are `S`, `C_in` and `C_out` in a full adder?

A
• `S` is the sum
• `C_in` is the carry from the previous calculation
• `C_out` is the carry that is going to be passed to the next calculation
80
Q

Inputs for an edge-triggered D-type Flip-flop

A

D and a clock signal

81
Q

Outputs for Edge-triggered D-type Flip-flop

A

Q and not Q

82
Q

What is the purpose of the clock in an Edge-triggered D-type Flip-flop? (2*)

A
• To synchronise the change of state of the circuit
• The clock oscillates between low and high signals at regular time intervals
83
Q

How does Q change in an Edge-triggered D-type Flip-flop?

A
• On the rising edge of the clock signal, Q and not Q are updated to hold D and not D respectively
• Output Q only takes on a new value if the value at D has changed at the point of a clock pulse
84
Q

How can an Edge-triggered D-type Flip-flop be used?

A

As a memory unit

85
Q

What is the name of the sequential circuit with a Data and Clock input that can be used as a memory unit?

A

Edge-triggered D-type flip-flop

86
Q

What is a function?

A

A mapping of values from a domain to a set of values from a co-domain. Not all of the co-domains members needs to be outputs.

87
Q

What is the domain?

A

The set from which the function’s input values are chosen

88
Q

What is the co-domain?

A

The set from which the function’s output values are chosen. Not all of the co-domains members needs to be outputs.