algorithms

Question 1

what is abstraction

Answer 1

picking out unnecessary details leaving only the important information.

Question 2

what is decomposition

Answer 2

breaking down a task into smaller pieces.

Question 3

what is an algorithm

Answer 3

a series of instructions to complete a task

Question 4

which is easier to code

a) binary search
b) linear search

Answer 4

b)linear search

Question 5

which is more efficient

a) binary search
b) linear search

Answer 5

a)binary search

Question 6

What is the precondition that must be true before we can use a binary search

Answer 6

the data must be ordered

Question 7

how does a linear search work

Answer 7

Each item in turn from the data set is compared with the target until either the target item is found or the end of the list is reached

Question 8

how does a binary search work

Answer 8

The data set MUST be ordered. The middle item (round down if an even number of items) is compared to the target. If the item is not the target then a check is run to see whether the target would appear ‘above’ (further forward in the list) or ‘below’ (further back in the list) - if it is present at all, which it may not be.
If the item would appear above the original mid point then a new mid point at the centre of the upper-half (all items above the original mid-point) is chosen.
Else if the item would appear below the original mid point a new mid point at the centre of the lower-half (all items below the original mid point) is chosen.
The process is then repeated with the new mid point until either the target is found OR the last item has been checked and the item has been proven not to be in the data set

Question 9

Which search algorithm is represented by the following pseudocode?

found = False 
number = 0 
target = value 

WHILE found == False AND number < LEN(book) 
IF data[number] == target 
found = True 
number = number + 1 
END WHILE 

IF found == True 
PRINT “target found” 
ELSE 
PRINT “target not data” 
END IF

Answer 9

linear search

Question 10

Which search algorithm is represented by the following pseudocode?

found = False 
left = 0 
right = LEN(data) - 1 
target = value 

WHILE found == False and left <= right
mid = (left + right) DIV 2

IF data[mid] == target 
found = True 
ELSE 
IF target > data[mid]: 
left = mid + 1 
ELSE 
right = mid - 1 
END IF 
END IF 
END WHILE 

IF found == True 
print("target found") 
ELSE 
print("target not in data") 
END IF

Answer 10

binary search

Question 11

Which search algorithm is most efficient if the target item is near the start of the data set

Answer 11

linear search

Question 12

Which sort algorithm makes repeated passes of the data set and guarantees to move one item at a time to the end of the data set

Answer 12

bubble sort

Question 13

What is the effect of this snippet of pseudocode?

items = ["y", "x"] 
i = 1 
if items [ i - 1 ] > items [ i ]: 
temp = items [ i - 1 ] 
items [ i - 1 ] = items [ i ] 
items [ i ] = temp

Answer 13

it swaps and items become x,y

Question 14

Why is temp used in this snippet of pseudocode?

items = ["y", "x"] 
i = 1 
if items [ i - 1 ] > items [ i ]: 
temp = items [ i - 1 ] 
items [ i - 1 ] = items [ i ] 
items [ i ] = temp

Answer 14

otherwise i - 1 would be lost

Question 15

how does a merge sort work

Answer 15

1. The set of unsorted data is split into two
2. Step 1 is repeated with each new unsorted data set until we have single items (so 16 unsorted items is split into 2 sets of 8 unsorted items, then 4 sets of 4 unsorted items then 8 sets of 2 unsorted items and finally 16 sets of 1 item each - 1 item is considered sorted)
3. Pairs of sorted data sets (started with single items) are merged into a new sorted data set
4. Step 3 is repeated until 1 fully sorted data set exists (so 16 sets of 1 sorted item becomes 8 sets of 2 sorted items then 4 sets of 4 sorted items etc.)

Question 16

what is pseudocode

Answer 16

a programming language that is in English to make it easier understood