Please enable JavaScript.
Coggle requires JavaScript to display documents.
computer science paper 1 - Coggle Diagram
computer science paper 1
fundamentals of algorithms
an algorithm is a step-by-step set of instructions for solving a problem
decomposition is the process of breaking a complex problem down into a number of sub-problems, with each sub-problem accomplishing a task
abstraction is the process of removing unnecessary details from a problem
how to solve problems...
flow charts
the start/stop symbol is a box with rounded corners
inputs/outputs symbol is a parallelogram
general processes symbol is a rectangle
decisions are put in diamond boxes
pseudocode
pseudocode is not an actual programming language but it should follow a similar structure and read like one (roughly)
more than one algorithm can be used to save the same problem
search algorithms
binary search
this search method only works for ordered lists
you find the middle item in the list, if this is the item you were looking for then stop the search
if not, compare the item you're looking for to the middle item, if it comes before the middle item then get rid of the second half of the list and if it comes after the middle item then get rid of the first half of the list
you'll be left with a list that is half the size of the original list then repeat the first steps on this smaller list to get an even smaller one and keep going until you find the item you're looking for
linear search
this algorithm is used on an unordered list
look at the first item in the unordered list and if this is the item you're looking for, then you can stop the search
if not, then look at the next item in the list
after that, repeat them steps until you find the item that you're looking for or you've checked every item
a linear search is much simpler than a binary search but not as efficient - the biggest advantage of a linear search is that it can be used on any type of list, it doesn't have to be ordered
for small ordered lists, the difference in efficiency doesn't really matter so the run time of both algorithms will be similar
for large ordered lists, the run time of binary search will generally be much quicker than linear search