Algorithms (PAPER 2)

Question 1

What are the three key techniques for computational thinking
- Give a brief description of each

Answer 1

• Decomposition
• breaking a complex problem into smaller problems and solving each individually
• Abstraction
• picking out important information and ignore the specifics that do not matter
• Algorithmic Thinking
• a logical way of getting from the problem to the solution. If the steps taken follow an algorithm then they can be reused and adapted to solve similar problems in the future

Question 2

What is pseudocode

Answer 2

code that is not an actual programming language but follows a similar structure

Question 3

Why is using pseudocode helpful (2)

Answer 3

• don’t have to worry about syntax (finer details)
• easy to convert into code

Question 4

Why should pseudocode not be vague

Answer 4

so that it can be converted into code easily

Question 5

What are boxes with rounded corners used for in flow charts

Answer 5

terminals - beginning and end

Question 6

What are parallelogram boxes used for in flow charts

Answer 6

anything that is taken out or put into the algorithm

Question 7

What are rectangular boxes used for in flow charts

Answer 7

general instructions, processes and calculations

Question 8

What are diamond boxes used for in flow charts

Answer 8

decisions, usually yes or no questions

Question 9

What are arrows used for in flow charts

Answer 9

connects boxes and show the direction that should be followed

Question 10

What are sub programs in flow charts

Answer 10

references to other flow charts

Question 11

What is a sequence in a flow chart

Answer 11

a way to get from start to finish

Question 12

What is a selection in a flow chart

Answer 12

when there are multiple ways to get from start to finish

Question 13

What is an iteration

Answer 13

a loop that allows you to repeat a task

Question 14

What are the two common types of search algorithm
- do the terms have to be sorted or not

Answer 14

Binary Search - the terms must be sorted
Linear Search - the terms can be sorted or unsorted

Question 15

How does a binary search work

Answer 15

• find the middle item ( (n + 1) / 2 )
• If this is the item then stop
• If not compare the terms - if it is after, then delete the first half and vice versa
• repeat until the item is found

Question 16

How does a linear search work

Answer 16

• look at first item
• if this is the item then stop
• else look at the next term
• repeat until item is found

Question 17

What are the three common types of sorting algorithm

Answer 17

• Insertion Sort
• Bubble Sort
• Merge Sort

Question 18

What are the steps to bubble sorting

Answer 18

1 - Look at first two items
2a - If they are in the right order, leave them.
2b - If they are in the wrong order, swap them
3 - Move to the next pair and repeat step 2

4 - Repeat step 3 until the end of the list (1 pass)

5 - Repeat 1-4 until there are no swaps in a pass

Question 19

What is a pass

Answer 19

when you reach the end of a list during a bubble sort

Question 20

What are the pros of using bubble sort (3)

Answer 20

• simple algorithm that can be easily implemented on a computer
• efficient way to check if a list is already in order
• Doesn’t use much memory as all sorting is done using the original list

Question 21

What are the cons of using bubble sort (2)

Answer 21

• inefficient way to sort a list
• does not cope well with a large list of items

Question 22

What is the largest amount of comparisons that must be done when bubble sorting a list of ‘n’ items

Answer 22

n ( n - 1 ) / 2

Question 23

What two facts does merge sort capitalise on

Answer 23

• small lists are easier to sort than large lists
• It is easier to merge two sorted lists than two unsorted lists

Question 24

What are the steps to merge sorting

Answer 24

1 - Split the list in half (sub-lists)
2 - Keep repeating step 1 until all the lists have only 1 item
3 - Merge pairs of sub-lists so that each sub-list has twice as many items. Sort the items into the right order each time

4 - Repeat step 3 until all the sub-lists have formed one list

Question 25

In merge sorting, if a list has 9 items, how many items will be in each sub-list

Answer 25

4 in 1st 5 in 2nd

Question 26

What are the pros of using merge sort (2)

Answer 26

- much more efficient and quicker than bubble sort and insertion sort for large lists - consistent running time regardless of how ordered the items are originally

Question 27

What are the cons of using merge sort (3)

Answer 27

- slower than other algorithms for small lists - Even if the list is already sorted it still goes through the whole process - uses more memory than the other algorithms to create separate lists

Question 28

Which sorting algorithm is used by many programming languages such as Java, Python and Perl

Answer 28

merge sort

Question 29

How does insertion sort

Answer 29

1 - look at second item in a list 2 - Compare it to all items before it and insert the number into the right place 3 - Repeat step 2 for all remaining items until the last number has been inserted into the correct place

Question 30

What are the benefits and drawbacks of using a linear search over a binary search

Answer 30

BENEFITS - can be used on an unsorted list, much simpler DRAWBACKS - much less efficient, poor with large lists,

Question 31

What are the pros of using insertion sort (5)

Answer 31

- Easy to code - Copes well with small lists - does not require much additional memory - quick to add items to an already ordered list - quick at checking that a list is already sorted

Question 32

What is the main disadvantage of using insertion sort

Answer 32

doesn't cope well with large lists ( n ( n + 1 ) / 2 )