fundamentals of algorithms

Question 1

define the term algorithm

Answer 1

a sequence of steps that can be followed to complete a task

Question 2

define the term decomposition

Answer 2

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

Question 3

define the term abstraction

Answer 3

the process of removing unnecessary detail from a problem

Question 4

what shape is a decision in a flowchart?

Answer 4

diamond

Question 5

what shape is a process in a flowchart?

Answer 5

rectangle

Question 6

what shape is a input/output in a flowchart?

Answer 6

parallelogram

Question 7

what shape is a subroutine in a flowchart?

Answer 7

rectangle with a line at each side

Question 8

explain linear search

Answer 8

a linear search checks each item of the list in turn to see if it’s the correct one and stops when it either finds the item or has checked every item

Question 9

explain binary search

Answer 9

a binary search finds the middle item in the list (if this is the right item then it stops)

if not it compares the requested item with the middle item and gets rid of the half which the item isn’t in

this will repeat until the number is found
( in an odd list ( e.g 7 ) round down so ( item 3 would be half )

Question 10

what are the advantages of linear search over binary search?

Answer 10

works in an unordered list

for small lists the run time of both algorithms will be similar

Question 11

what are the advantages of binary search over linear search?

Answer 11

is much quicker at searching big lists
run time is similar for small lists
( but doesn’t work in an unordered list )

Question 12

explain the merge sort

Answer 12

split the list in half ( into sublists )
repeat until each sublist has one item
merge the sublists and sort the order each time
repeat until all the sublists are merged

Question 13

explain the bubble sort

Answer 13

the bubble sort looks at the first two items and swaps them if they are in the wrong order
this continues until the end of the list ( called a pass ( now the final number is in the correct place )
repeat until a pass has no swaps

Question 14

what are the advantages for a bubble sort over a merge sort?

Answer 14

much quicker for longer lists

very consistent run time no matter how unordered the list is

Question 15

what are the advantages of a merge sort over a bubble sort?

Answer 15

little memory is used
simple and can be easily implemented
efficient - for a list of n you only need to do n-1 comparisons to check if the list is ordered