SLR 2.1 Algorithms Flashcards
In Computer Science what is ‘abstraction’?
‘abstraction’ means to ignore unnecessary details - e.g when giving instructions how to travel to somewhere we don’t mention every lamp-post and house you go past.
In Computer Science what is ‘decomposition’?
‘decomposition’ means breaking a problem down into smaller chunks that are more easily solved.
In Computer Science what is an ‘algorithm’?
An ‘algorithm’ is a series of instructions that combine to solve a problem.
Which of these two search algorithms is easier to code?
a. binary search
b. linear search
b. linear search
Which of these two search algorithms is usually more efficient?
a. binary search
b. linear search
a. binary search
What is the precondition that must be true before we can use a binary search?
The data must be ordered
How does a linear search work?
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.
How does a binary search work?
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.
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
a linear search
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
a binary search
Which search algorithm is most efficient if the target item is near the start of the data set?
The linear search
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?
A bubble sort
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
it swaps the items so that they become [“x”, “y”]
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
Because otherwise the value of items [ i - 1 ] would be lost (it would be overwritten by the value of items [ i ]
How does a merge sort work?
- The set of unsorted data is split into two
- 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)
- Pairs of sorted data sets (started with single items) are merged into a new sorted data set
- 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.)
