4 + 9. Data Representation and Algorithms

Question 1

What is a bit?

Answer 1

A binary digit (a bit) is the fundamental unit of data storage, and will have a value of 0 or 1.

Question 2

What is a byte?

Answer 2

A group of 8 bits.

Question 3

What is a word?

Answer 3

Word refers to the amount of data that can be handled at one time by the processor.

Question 4

Why is hexadecimal used as a shorthand for binary?

Answer 4

Long sequences of binary digits are hard to read and understand for humans.

Question 5

How is text represented?

Answer 5

In order to represent text, each individual letter or character must be represented a unique binary pattern. In order to consistently represent characters from many different languages, these patterns must universally understood (through ASCII and Unicode).

Question 6

How are numbers represented?

Answer 6

Numbers are represented using number base systems, which determine which digits are used to represent a number.

Question 7

What is a character set?

Answer 7

Character maps are used to represent each character. Each character is mapped to a binary number. Allows for standardised communication between computer systems

ASCII - Can only represent 128 characters (not sufficient to represent all languages/scripts)

Question 8

What is bubble sort?

Answer 8

The bubble sort algorithm works by repeatedly going through a list of items, comparing consecutive pairs of items and swapping the items if they are in the wrong order.

Each time the algorithm goes through the list a pass is complete.

The passes through the list are repeated until the items are sorted.

Bubble sort can be used on an ascending or descending list.

Question 9

What is an Insertion Sort?

Answer 9

The insertion sort algorithm works by building up a sorted sub list in the first part of the original list, while the remaining part of the list remains unsorted.

The algorithm goes through the unsorted sub list, item by item. As each item is examined, it is moved into the correct position (in ascending or descending order) in the sorted sub list. This progresses until the final item is correctly inserted and the list is sorted.

Question 10

What is binary search?

Answer 10

The algorithm calculates a midpoint and depending on if the list is ascending or descending will ignore a certain half of the list and focus on the half that contains the desired the item. It repeats this process until the item is found.

Question 10

What is linear search?

Answer 10

The algorithm for this process is called linear search, because it involves starting from the beginning of the list and checking one item at a time to see if it’s the right one.

Question 11

Describe appropriate circumstances for the use of binary and linear search?

Answer 11

• Requires input data to be sorted, linear doesn’t.
• Binary search requires an ordering comparison, linear search only requires an equality comparison
• Linear search would be slower than binary search on a larger list/

Question 12

Why do we need to data compress?

Answer 12

Data compression is used so large files can be transferred over a cable or wireless communications link easier and faster. Compression algorithms are used to store large files in limited storage, it saves space and money.

Question 13

What is lossy compression?

Answer 13

Lossy compression refers to loss of data (data is removed). When the file is decompressed, the data that was removed is re-created from the data that remains in the file. The re-created data will never be an exact copy of the original. Instead, it will be an approximation of the original data.

Question 14

What is lossless compression?

Answer 14

Lossless compression refers to no data is lost in the compression process. When the file is decompressed, the contents are identical to the original file.

Question 15

What is RLE?

Answer 15

Run length encoding (RLE) is a lossless compression technique. It works by finding runs of repeated binary patterns and replacing them with a single instance of the pattern and a number that specifies how many times the pattern is repeated

Question 16

What is Dictionary?

Answer 16

Dictionary-based compression is another lossless technique that relies on finding patterns in data. Instead of storing the pattern itself, a shorter code is substituted.

Question 17

What is a variable?

Answer 17

A variable is a named location in the computer’s memory that a programmer can use to store data whilst the program is still running

Question 18

What is a constant?

Answer 18

A constant is similar to a variable in sense it has an identifier and will store a value but the value will not change.

Question 19

What is a self-documenting identifier?

Answer 19

An identifier that conveys its purpose without requiring additional comments.

Question 20

What is a parameter (by value)?

Answer 20

A local copy of the data is created for the procedure (discarded later)

Question 21

What is parameter by reference?

Answer 21

When passing by reference, the address
of the required data is passed to the
procedure. Any changes made within the subroutine will also affect the variable outside.

Question 22

What is parameter?

Answer 22

A parameter is a variable that can be passed to/from the procedure

Question 23

What is the pseudocode for a linear search?

Answer 23

declare myArray[0 to 999] is integer
searchValue is integer
found is boolean

set found = FALSE

input searchValue

for i = 0 to len(myArray)
if searchValue = myArray[i] then
set found = TRUE
output “SearchValue found at position
end if
next i

if found = FALSE
output “SearchValue not found”
end if

Question 24

What is the pseudocode for a binary search?

Answer 24

declare myArray(0 to x) is integer
start is integer
end is integer
found is boolean
mid is integer

set start = 0
set end = len(myArray)
set found = FALSE

input searchValue

repeat
set mid = (start + end) DIV 2

if searchValue = myArray[mid] then
set found = TRUE
output”searchValue found at position”,mid
end if

if searchValue > myArray[mid} then
set start = mid + 1
end if

if searchValue < myArray[mid] then
set start = mid - 1
end if

until (found = TRUE) or (end<start)