3.1- Fundamentals of Algorithms

Algorithm

An algorithm is a sequence of steps that can be followed to complete a task.

Decomposition and an example of its use.

Decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.

Abstraction and an example of how it would be used.

Abstraction is the process of removing unnecessary detail from a problem. For example when designing a game, unnecessary information is removed in order to make it easier to play and easier to make

Which shape means a procedure

Rectangle

Which shape is used for start and end

Stadium (rounded rectangle)

Which shape is used for decisions

Diamond

Which shape is used for input/output

Parallelogram

What represents the direction of flow in flowcharts

Arrow

Define Sequence

Stand-alone lines in code, that don't apply to selection or iteration. E.g count=0

Define Selection

A decision or question in a statement. E.g an if statement

Define iteration

Repetition. Can be indefinite if the statement is conditional, and definite if the amount is specified. E.g a while loop

Boolean Operators:
<
>
<=
>=
==
!=

Less than
Greater than
Less than or equal to
Greater than or equal to
Equal to
Not equal to

Describe how a binary search works

The list must be in order, and it is then halved repeatedly until the value is found

Which of these would be examined in a binary search for 4

1 2 4 12 21 33 44 57 61 73

21 2 4

Describe how a linear search works

• Starts at the beginning of the list

• Iterates sequentially through the list

• Compares the contents of each position with the data being searched

• If it matches, the item has been found, and the search ends

• If the end of the list is reached without finding the data being searched for, the item is not in the list

Which of these will be examined in a linear search for 44
1 2 4 12 21 33 44 57 61 73

1 2 4 12 21 33 44

Describe how a bubble sort works

• Compare first two values in the list

• Swap numbers if they are in the wrong order- which ever is highest should be in front

• Continue on in the list, swapping values to get the highest value- the highest value is now at the end

• Go back to the start of the list and repeat

• Continue this until the list is in order

Show the steps of a bubble sort for this list
21 15 34 9 57 61 77 45

15 21 9 34 57 61 45 77
15 9 21 34 57 45 61 77
9 15 21 34 45 57 61 77

Describe how a merge sort works

• Lists are continuously divided in half, until each list has one component

• Adjacent lists are compared- whichever has the lower value goes first, then the higher- the lists are merged into ordered lists with two components

• This continues, repeating this pattern, of merging the lists by comparing the first values of each list and seeing which is smaller, then moving onto the next component, until the list has been fully merged into an ordered list

Show the steps of a merge sort for this list
21 15 34 9 57 61 77 45

21 15 34 9 57 61 77 45
21 15 34 9 / 57 61 77 45
21 15 / 34 9 / 57 61 / 77 45
21 / 15 / 34 / 9 / 57 / 61 / 77 / 45
15 21 / 9 34 / 57 61 / 45 77
15 21 9 34 / 57 61 45 77
9 15 21 34 / 45 57 61 77
9 15 21 34 45 57 61 77

Compare the advantages and disadvantages of merge sort and bubble sort

Merge Sort
Adv- Its generally faster
Dis- It takes up more memory, due to making new lists

Bubble Sort
Adv- It takes up less space, due to only editing the same list
Dis- Its generally slower