3.1 Fundamentals Of Algorithms

Question 1

Algorithm definition:

Answer 1

= sequence of steps followed to complete a task

Question 2

Decomposition definition:

Answer 2

= breaking complex problem down into smaller sub-problems & solving each one individually

Question 3

Abstraction definition:

Answer 3

= removing unnecessary detail from a problem (picking out important bits)

Question 4

Two ways to write an algorithm:

Answer 4

• pseudo-code

- flowcharts

Question 5

Pseudo-code purpose & advantages:

Answer 5

= clearly shows an algorithms steps without the finer details

• quick to write
• easy to understand
• easily converted into any programming language

Question 6

Pseudo-code signs:

Answer 6

Assigning a variable: _

Question 7

Flowchart commands

Answer 7

Oval = start/stop
Parallelogram = outputs/inputs
Rectangle = processes (instructions/calculations)
Diamond = decision
Rectangle with added vertical lines = subroutine
Arrow = shows direction

Question 8

Types of flowcharts

Answer 8

• sequences (Straight from start to end)
• iteration (Contains a loop, allows tasks to be repeated)
• selections (Multiple ways from start to stop, includes decision)

Question 9

Types of search algorithms:

Answer 9

= to find items in a list

• binary search
• linear search

Question 10

Binary search

Answer 10

1) find middle item in ordered list
2) if this is the item you’re looking for, stop
3) if not, compare middle term with desired item (if it comes before the middle term, get rid of 2nd half of list, if it comes after, get rid of 1st half)
4) repeat steps 1-3 until the desired item is found
(Divide-and-conquer algorithm)

Question 11

Advantages & disadvantages of binary search:

Answer 11

+
Faster/more efficient on large datasets

-
Dataset must be sorted(ordered) before

Question 12

Linear search:

Answer 12

1) check first item in dataset
2) if this is the item you are looking for, stop
3) if not look a next item in list
4) repeat steps 2-3 until desired item found, or every item checked

Question 13

Advantages & disadvantages of linear search

Answer 13

+
Very easy to implement (simple)
List doesn’t need to be sorted/ordered (used on any type of list)

• Slow/not efficient on long lists

Question 14

Types of sort algorithms:

Answer 14

= sorts lists into numerical/alphabetical order

• bubble sort
• merge sort

Question 15

Bubble sort:

Answer 15

1) look at first 2 items in list
2) if in right order, don’t do anything, if in wrong order, swap them
3) move onto next pair of items
4) repeat steps 2-3 until end of list = 1 pass
5) repeat steps 1-4 until no swaps in a pas (include last pass with 0 swaps)

Question 16

Advantages & disadvantages of bubble sort

Answer 16

+
Simple algorithm, easily implemented on computer
Efficient to check if list is already in order
Doesn’t use much memory

-
Inefficient = slow for large lists

Question 17

Merge sort

Answer 17

1) split list in half (into sub-lists) until all lists only contain 1 item
2) merge pairs of sub-lists, sorting items into right order each time
3) repeat step 2 until merged all sub-lists together

Question 18

Advantages & disadvantages of merge sort

Answer 18

+
More efficient/quicker (than bubble) for large lists but similar for small lists
Very consistent running time regardless of how ordered original list is

• Even if list is already sorted, will still go through whole process
  Uses more memory (creates additional lists)