Computational Thinking, Searching & Sorting Algorithms Flashcards

All 19 cards in this deck

What are the three principles of computational thinking?

Abstraction, decomposition and algorithmic thinking.

What is abstraction?

Removing or ignoring unnecessary detail from a problem so only the key features needed to solve it remain.

What is decomposition?

Breaking a problem down into smaller sub-problems that are easier to solve.
e.g. a quiz program splits into: store questions, ask questions, check answers, keep score.

What is algorithmic thinking?

Working out the sequence of steps needed to solve a problem, so the solution can be written as an algorithm.

In a route-planning app, give one detail abstraction keeps and one it removes.

Keeps: roads and distances between places. Removes: colours of buildings, names of shops, scenery.

True or false? Abstraction means breaking a problem into smaller sub-problems.

False. That is decomposition; abstraction is removing unnecessary detail.

What are the main steps of a linear search?
e.g. search 4, 9, 2, 7 for the value 2

1. Compare the first value to the value searched for: $4 \neq 2$.
2. If they match, stop — the item is found.
3. If not, move to the next value and repeat: $9 \neq 2$, then $2 = 2$ → found.

What are the main steps of a binary search?
e.g. find 10 in 1, 2, 5, 6, 7, 10, 20

1. Pick out the middle value: 6.
2. If it is not the value searched for, discard the half it cannot be in: $6 < 10$, so discard 1, 2, 5, 6 and keep 7, 10, 20.
3. Repeat on the remaining list: middle value is 10 → found.

State one pre-requisite for a binary search.

The data must be sorted / in order.

True or false? A linear search can only be used on data that is in order.

False. A linear search works on unsorted data; only a binary search needs sorted data.

Other than finding the value, what condition stops a linear search?

The end of the list is reached / every value has been checked (and the value was not found).

Which search would you choose for a large list that is already sorted, and why?

Binary search — it halves the list each time, so it needs far fewer comparisons than a linear search.

What are the main steps of a bubble sort?
e.g. sort 3, 1, 2

1. Compare the first pair and swap them if they are in the wrong order: 1, 3, 2.
2. Move along one place and repeat to the end of the list (one pass): 1, 2, 3.
3. Repeat passes until a pass makes no swaps: list is sorted as 1, 2, 3.

What are the main steps of an insertion sort?
e.g. sort 5, 2, 4

1. Treat the first item as the sorted part and take the next item: 2.
2. Compare it back through the sorted part and insert it in the correct place: 2, 5.
3. Repeat for every remaining item: insert 4 → 2, 4, 5.

What are the main steps of a merge sort?
e.g. sort 4, 1, 3, 2

1. Split the list in half repeatedly until each list holds one item: 4 | 1 | 3 | 2.
2. Merge pairs of lists, comparing values so each merged list is in order: 1, 4 and 2, 3.
3. Keep merging until one list remains: 1, 2, 3, 4.

Which sorting algorithm splits the data into individual items before recombining them in order?

Merge sort.

Which sorting algorithm uses an array with a sorted part and an unsorted part?

Insertion sort.

True or false? A bubble sort always swaps the pair of values it compares.

False. It swaps them only if they are in the wrong order.

True or false? Each comparison in a binary search discards about half of the remaining items.

True. The middle item is compared, then one half of the list is discarded, which makes it faster than a linear search on large sorted lists.