Zusammenfassung der Ressource
2.1 Algorithms
- Computational Thinking
- Allows us to take a complex problem, understand what the
problem is, and then develop possible solutions
- The use of a computer to solve problems
- 4 Key Areas:
- Decomposition
- Breaking down a complex problem or system
into smaller, more manageable parts
- Abstraction
- Gets rid of the irrelevant
stuff in the program
- Allows to only focus on the important information
- Pattern Recognition
- Looking for similarities among
and within problems
- Algorithms
- Developing a step-by-step
solution to solve the problem
- Algorithms must be detailed & easy to
understand so it can be passed onto
someone else and have them code it
- Binary Search
- List must be in order
- Middle Value
is taken
- Search is stopped if it is the value
is the one you're looking for
- If middle value is larger than the desired one:
Take the values to the left of the middle value
- Then repeat with the new list
- If middle value is smaller than the desired one:
Take the values to the right of the middle value
- LInear Search
- List does not have to be in order
- First value of list
is checked
- Search is stopped if it is the value
is the one you're looking for
- If not desired value: Check
next value on the list
- Process is repeated until
desired value is attained
- Bubble Sort
- A method for sorting out unordered lists
- Take the first and second elements
from the list and compare them
- If element 1 >
element 2: Swap
- Else: Leave it
- Move along to the next
pair of elements (element
2 & 3) and repeat
- Repeat until you have moved through the
whole list and not made any changes
- Worst case scenario: n*n (n = number of
elements) Average number of swaps: n^2
- Merge Sort
- A list is split into individual lists, these
are then combined (2 lists at a time)
- Split all elements into individual lists
- Compare the first element into first two lists
- Put the smallest at the start of a new list
- Compare the next element of the 1st list
with the next element of the 2nd list
- Put the smallest into a new list
- Repeat until first two lists merged
- Then repeat with other lists
- If you have two values the same,
add one (it doesn't matter from
which list), and then add the second
- Insertion Sort
- Comparing unsorted elements in an
individual list and sorting then out in order
- In a list, the starting element is a 'sorted' list
- The rest of the elements are an 'unsorted' list
- Compare the first element in the 'unsorted'
list with all the elements in the 'sorted' list
- If the current unsorted element is smaller than the interacted sorted element,
put it in front of that element (move the other sorted elements along)
- If the unsorted element is larger,
compare it with the next
- If there are no more elements in the 'sorted' list, put it in the final position
- Repeat until all elements in the
'unsorted' list are in the 'sorted' list
- Flow Chart
- Can be used to represent an algorithm
- It shows the data that is inputted and outputted
- It shows the processes (actions) that take place
- It shows the decisions and repetitions that take place
- Lines are used to show the flow of control
- Set shapes are used to
represent different functions
- Diamond - Decision
- Oval - Start/End
- Rectangle - Process
- Parallelogram - Input/Output
- Rectangle with 2 interior
lines - Sub-Process
- Pseudocode
- 'Fake code'
- Part way between English
sentences, and programming code
- It is language neutral (it can be read by
programmers who are able to use any language)
- Dry Run - Walking through an algorithm which
sample data, running each step manually
- Trace Table - A table that follows the values
of variables to check for accuracy