cs paper 1

algorithm

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

computer program

an implementation of an algorithm

decomposition

breaking down a problem into a number of sub-problems

abstraction

the process of removing unnecessary detail from a problem

linear search algorithm

compares the search item against each item in the list one by one

advantages of linear search

simple, no sorting required, good for short lists

disadvantages of linear search

slow, inefficient for long lists

search algorithm

finding a value in a data structure

binary search algorithm

finds the position of the target value within a sorted array by checking the middle value and then discarding half the list each time

advantage of binary search

quick

disadvantages of binary search

list needs to be sorted before searching

Boolean logic

a data type with two values, true or false

sorting algorithm

to order an unordered list

bubble sort

compares each pair in a list and swaps them if they are in the wrong order, repeats until there are no more swaps to be made

advantage of bubble sort

very simple so easy to program

disadvantage of bubble sort

slow for long lists

maximum number of comparisons for bubble sort

n(n-1)/2 comparisons

merge sort

splits a list into sub lists and then merges them back together in order

recursive function

calls itself in its definition

advantage of merge sort

much faster than bubble sort

disadvantage of merge sort

more complex to understand and code because it is recursive