T6 - Computational Thinking/ Searching/ sorting algorithms

Question 1

Algorithms

Answer 1

set of instructions for solving a problem or completing a task

Question 2

Abstraction

Answer 2

involves removing unnecessary detail from a problem so that you can focus on the essential components

Question 3

Algorithmic thinking

Answer 3

– an approach to solving problems by the use of algorithms (sequences of steps that lead to a solution)

Question 4

Structure diagram

Answer 4

– a hierarchical diagram that shows how a problem is broken down into sub-sections/sub-tasks

Question 5

Decomposition

Answer 5

• involves breaking down a large problem into smaller sub-problems
  Then the sub-problems can be broken down further until each small task is manageable

Question 6

Advantages of decomposition

Answer 6

• easier to solve
  -reusable
  -saving development time

Question 7

A structure diagram

Answer 7

is used to show how a problem is broken down

Question 8

Linear search:

Answer 8

requires checking through each item in the list, one by one
very slow
Don’t have to be sorted

Question 9

Binary search:

Answer 9

List must be sorted
Examine the middle one first
the size of the list is halved each time an item is examined

Question 10

The data sets could be sorted as follows:

Answer 10

Count order (which will be the same as the rank order)
Alphabetical order
Reverse alphabetical or count order

Question 11

The bubble sort:

Answer 11

Start with the leftmost item
Compare this item with the one next to it
If the one next to it is less, swap the items
Repeat for all the other items
At the end of one pass through the list, the largest item is at the end of the list
Repeat the process until the items are sorted

Question 12

Bubble sort - saving data:

Answer 12

When data is swapped, it is saved to a temporary variable
Then it is copied from the variable

Question 13

Insertion sort:

Answer 13

sorts one data item at a time
One item is taken from the list, and placed in the correct position
This is repeated until there are no more unsorted items
Faster than bubble sort

Question 14

Merging two lists:

Answer 14

Read item from list A; Read item from list B
Write smaller to output list.
Read next item from the list that held the smaller value
Repeat until all items written to output list

Question 14

Merge sort pros:

Answer 14

More efficient than bubble sort and insertion sort

Question 15

Merge sort

Answer 15

Divide the unsorted list in two
Continue to divide these lists into two until there is just one item in each list
Now merge each list back until there is only one
list remaining – which will be the fully sorted list