Topic 6 - Algorithms

Question 1

abstraction

Answer 1

• picking out the important bits of information from a problem
• removing unnecessary details

Question 2

decomposition

Answer 2

• breaking a complex problem into smaller problems and solving each one individually

Question 3

algorithmic thinking

Answer 3

• logical way of getting from problem to solution
• using steps and recycling them for similar questions
  input, process, output

Question 4

2 search algorithms:

Answer 4

1) Linear
2) Binary

Question 5

linear search

Answer 5

• iterates throughout the list in order
• until item is found

Question 6

binary search

Answer 6

• checks middle item in list
• is it value? is it larger or smaller?
• if not it discards all items in 1st half or 2nd half of list
• until value is found

Question 7

linear pros

Answer 7

• much simpler
• good for short lists
• can be used on ordered or unordered lists

Question 8

binary pros

Answer 8

• more efficient
• generally takes fewer steps
• more suitable for larger lists

Question 9

bubble sort

Answer 9

• look at 1st 2 items in list
• if they are in right order do nothing but if in wrong order swap them
• move to next pair ( 2nd and 3rd ) and repeat step 2
• repeat step 3 until you get to end of list, this is a pass
• in next pass don’t include last item
• repeat process until there are no swaps in a pass

Question 10

bubble sort pros

Answer 10

• simple to check if an list is already ordered
• simple algorithm that can easily be implemented on computer
• doesn’t use much memory

Question 11

bubble sort cons

Answer 11

• inefficient way, worst case scenario n(n-1)/2 comparisons
• doesn’t cope with large list of items

Question 12

insertion sort

Answer 12

• starts with 2nd item in list
• checks if it is smaller than value before it
• if it it is, it is swapped with item on left
• continues until we find smaller item in sorted list
• moves to next item and starts process again

Question 13

insertion pros

Answer 13

• all sorting is done on the original list
• can be easily coded
• doesn’t require much additional memory
• quick for checking if list is already ordered

Question 14

insertion cons

Answer 14

• inefficient, worst case scenario same as bubble
• doesn’t cope well with large lists

Question 15

merge sort

Answer 15

• split the list in half into sub lists
• repeat until each list until contains one list
• merge lists sub-lists together, ordering them
• repeat until you only have one list

Question 16

merge pros

Answer 16

• more efficient and quicker
• more suitable for large lists
• consistent running time

Question 17

merge cons

Answer 17

• slower for small lists
• even if list is ordered it still goes through whole process
• uses more memory in order to create separate lists

Question 18

flowcharts

Answer 18

• uses symbols and arrows to show order of algorithm
• and different paths the program could take
• visual approach, easy to understand

Question 19

pseudocode

Answer 19

• not an actual programming language but should read like one
• it shows an algorithm’s steps clearly without using syntax of a language

Question 20

pros of using pseudocode

Answer 20

• quick to write
• easily understood by all programers
• can be converted into any language

Question 21

3 programming constructs

Answer 21

1) Sequence
2) Selection
3) Iteration

Question 22

sequence

Answer 22

order in which steps are carried out

Question 23

selection

Answer 23

using conditions so programs can take differnet poaths depending on input

Question 24

iteration

Answer 24

• repeating a process a certain amount of times ( count controlled) or until a condition is met ( condition controlled )