02 Section 4 - Algorithms

Question 1

What are the three key techniques for computational thinking?

Answer 1

Decomposition
Abstraction
Algorithmic thinking

Question 2

Define decomposition:

Answer 2

Breaking a complex problem down into smaller problems and solving each one individually

Question 3

Define abstraction:

Answer 3

Picking out the important bits of information from the problem, ignoring the specific details that don’t matter

Question 4

Define Algorithmic thinking:

Answer 4

A logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solve similar problems in the future

Question 5

What is pseudocode?

Answer 5

Not an actual programming language but it should follow a similar structure and roughly read like one
-shows the algorithm’s steps, without worrying about the specific syntax of a programming language

Question 6

What are the features of pseudocode?

Answer 6

• quick to write
• can be easily converted into any programming language
• different ways to write pseudocode, priority is that the person reading it can follow and understand it

Question 7

What are aspects and rules to follow for pseudocode?

Answer 7

• VARIABLES -are named at the start
• INDENTATION -makes it more readable
• USE CAPITAL LETTERS FOR COMMAND AND KEY WORDS (e.g. PRINT, IF, ELSE, INPUT…)

Question 8

What is the symbol used for start/stop for flow diagrams?

Answer 8

The beginning and end of the algorithm are put into boxes with rounded corners

Question 9

What is the symbol used for inputs/outputs for flow diagrams?

Answer 9

Anything that is put into or taken out of the algorithm goes into a parallelogram box`

Question 10

What is the symbol used for processes for flow diagrams?

Answer 10

General instructions, processes and calculations go in rectangular boxes

Question 11

What is the symbol used for decisions for flow diagrams?

Answer 11

Decisions, often a ‘yes’ or ‘no’ question, are put in diamond boxes

Question 12

What is the symbol used for sub routines for flow diagrams?

Answer 12

Sub routines are like sub programs, they reference other flow diagrams
-a rectangle with extra lines at either end (splitting it up into a small vertical rectangle, a large horizontal rectangle then another small vertical rectangle)

Question 13

What is the symbol used for showing directions for flow diagrams?

Answer 13

Arrows connect boxes and show the direction you should follow. Some boxes might have multiple arrows coming in or going out of them

Question 14

What are the different ways you can write algorithms?

Answer 14

Pseudocode

Flow diagrams

Question 15

What are the three ways which a program can be written or features that they can contain?

Answer 15

Sequence
Selection
Iteration

Question 16

What is sequence?

Answer 16

When there is only one way from start to end

Question 17

What is selection?

Answer 17

When there are multiple ways to get from start to stop

Question 18

What is iteration?

Answer 18

When a program contains a loop that allows you to repeat a task

Question 19

What does a binary search do?

Answer 19

A binary search looks for items in an ordered list

Question 20

How do you find the middle item of a list?

Answer 20

(n + 1) / 2

-in a list of n items

Question 21

What is a binary search algorithm?

Answer 21

1) find the middle item in an ordered list
2) if this is the item you’re looking for, stop the search you have found it
3) if not, compare the item you’re looking for to the middle item. If it comes before the middle item get rid of the second half of the list, if it comes after get rid of the first half of the list
4) you’ll be left with a list half the size of the original list, repeat steps 1-3 on the smaller list until you find the item you are looking for

Question 22

What does a linear search do?

Answer 22

A linear search checks every item in an unordered list to see if it’s the correct one, it stops either when it finds the item or has checked every item

Question 23

What is a linear search algorithm?

Answer 23

1) look at the first item in the unordered list
2) if this is the item you’re looking for, stop the search
3) if not look at the next item in the list
4) repeat steps 2-3 until you find the item that you’re looking for or you have checked every item

Question 24

What are the pros and cons of linear search?

Answer 24

PROS
-simpler
-can be used on any type of list (no order needed)
-easy to code
CONS
-less efficient (worst case scenario, checking every item in list)
-not suitable for larger lists

Question 25

What are the pros and cons of binary search?

Answer 25

``` PROS -more efficient (takes fewer steps to find what you're looking for) -suitable for larger lists CONS -list has to be ordered -harder to code ```

Question 26

What searching algorithms are there?

Answer 26

Binary search | Linear search

Question 27

What sorting algorithms are there?

Answer 27

Bubble sort Merge sort Insertion sort

Question 28

What is bubble sort?

Answer 28

Bubble sort compare pairs of items and is used to sort unordered lists of items

Question 29

What is a bubble sort algorithm?

Answer 29

1) look at the first two items in a list 2) if they are in the right order, leave them. if they are in the wrong order, swap them 3) move onto the next pair of items(2nd and 3rd items) and repeat step 2 4) repeat step 3 until you get to the end of the list (this is called ONE PASS), the last item will now be in the correct place, so don't include it in the next pass 5) repeat steps 1-4 until there are no swaps in a pass

Question 30

What are the pros of bubble sort?

Answer 30

- simple algorithm that can be easily implemented on a computer - efficient way to check if a list is already in order, a list of n items,only have to do one pass of n-1 comparisons - doesn't use much memory, as all sorting is done using the original list

Question 31

What are the cons of bubble sort?

Answer 31

- an inefficient way to sort a list, for a list of n items the worst case scenario is (n(n+1))/2 comparisons - due to being inefficient, it does not cope with large lists of items well

Question 32

What is merge sort?

Answer 32

Merge sort is a divide and conquer algorithm that takes advantage of the fact the smaller lists are easier to sort and it is easier to merge two ordered lists than two unordered lists

Question 33

What is a merge sort algorithm?

Answer 33

1) split the list in half(small list are called sub-lists), the second sub-list should start with the middle item 2) repeat step 1 until all sub-lists only contain one item 3) merge pairs of sub-lists, and sort them into the right order each time you merge the sub-lists 4) repeat step 3 until all the sub-lists are together

Question 34

What are examples of where merge sort is used?

Answer 34

Due to its efficiency it is used by many programming languages such as Java, Python and Perl as the primary sorting algorithm

Question 35

What are the pros of merge sort?

Answer 35

- much more efficient and quicker the bubble or insertion for large lists - very consistent running time regardless of how ordered the items in the original list are

Question 36

What are the cons of merge sort?

Answer 36

- slower than other algorithms for small lists - even if a list is already sorted it still goes through the whole splitting and merging process - uses more memory than the other sorting algorithms in order to create separate lists

Question 37

What is insertion sort?

Answer 37

A sorting algorithm that takes each item in turn and puts it in the right place using the first item in the list as a starting point

Question 38

What is a insertion sort algorithm?

Answer 38

1) look at the second item in the list 2) compare it to all items before it and insert the number into the right place 3) repeat step 2 until you have the last number inserted into the correct place

Question 39

What are the pros of insertion sort?

Answer 39

- intuitive way of sorting things and can be easily coded - copes well with small lists - doesn't require much additional memory (as all sorting is done on the original list) - very quick to add items to an already sorted list - quick at checking that a list is already sorted

Question 40

What are the cons of insertion sort?

Answer 40

-doesn't cope very well with large lists (best case scenario - (n-1) comparisons) (worst case scenario - (n(n-1))/2 comparisons)