2.1 Algorithms

Question 1

Abstraction

Answer 1

Removing unimportant parts of a problem in order to concentrate on those that are important

Question 2

Decomposition

Answer 2

Breaking down a problem into smaller more manageable ones

Question 3

Algorithmic thinking

Answer 3

An approach to solving problems by the use of algorithms (sequence of steps that lead to a solution)

Question 4

Structured diagram

Answer 4

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

Question 5

Why is a structured diagram used?

Answer 5

To show how a program is decomposed

Question 6

Linear search

Answer 6

1. Look at the first item in the list
2. Check if the item is equal to the search term
3. If the current item is the same as the search term, the item has been found. Otherwise, move to the next item in order.
4. Repeat from step 2 and 3 until the last item in the list has been reached
5. If the end of the list has been reached and the search term has not been found, then the search term is not in the list and the algorithm can stop.

Question 7

Binary search prerequisite

Answer 7

List must be ordered

Question 8

Binary search

Answer 8

1. Select the midpoint
2. Check if searched value is equal to midpoint value (not compare). If so, the search will stop
3. If the searched value is larger, discard the left half; if it is smaller, discard the right
4. Repeat steps 1-3 until item found or remaining list is of size 1 and item not found

Question 9

Bubble sort

Answer 9

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

Question 10

Merge sort

Answer 10

1. Divided the unsorted list in two
2. Continue to divide these lists into two until there is just one item in each list
3. Read item from list A
4. Read item from list B
5. Write smaller to output list
6. Read next item from the list that held the smaller value
7. Repeat until all items written to output list
8. Repeat 3-7 until only one list is remaining

Question 11

What does linear sort do?

Answer 11

• This algorithm sorts one data item at a time
• The list is split to sorted set/part and unsorted set/part

Question 12

Linear sort

Answer 12

1. One item is taken from the unsorted set, and placed in the correct position in the sorted set
2. This is repeated until there are no more unsorted items in the list