2.1 Algorithms

Computational Thinking
1. Allows us to take a complex problem, understand what the problem is, and then develop possible solutions
2. The use of a computer to solve problems
3. 4 Key Areas:
  1. Decomposition
    1. Breaking down a complex problem or system into smaller, more manageable parts
  2. Abstraction
    1. Gets rid of the irrelevant stuff in the program
    2. Allows to only focus on the important information
  3. Pattern Recognition
    1. Looking for similarities among and within problems
  4. Algorithms
    1. Developing a step-by-step solution to solve the problem
    2. Algorithms must be detailed & easy to understand so it can be passed onto someone else and have them code it
Binary Search
1. List must be in order
2. Middle Value is taken
  1. Search is stopped if it is the value is the one you're looking for
  2. If middle value is larger than the desired one: Take the values to the left of the middle value
    1. Then repeat with the new list
  3. If middle value is smaller than the desired one: Take the values to the right of the middle value
LInear Search
1. List does not have to be in order
2. First value of list is checked
  1. Search is stopped if it is the value is the one you're looking for
  2. If not desired value: Check next value on the list
    1. Process is repeated until desired value is attained
Bubble Sort
1. A method for sorting out unordered lists
2. Take the first and second elements from the list and compare them
  1. If element 1 > element 2: Swap
    1. Else: Leave it
      1. 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
3. Worst case scenario: n*n (n = number of elements) Average number of swaps: n^2
Merge Sort
1. A list is split into individual lists, these are then combined (2 lists at a time)
2. Split all elements into individual lists
  1. Compare the first element into first two lists
    1. Put the smallest at the start of a new list
      1. 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
1. Comparing unsorted elements in an individual list and sorting then out in order
  1. In a list, the starting element is a 'sorted' list
    1. The rest of the elements are an 'unsorted' list
      1. 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
1. Can be used to represent an algorithm
2. It shows the data that is inputted and outputted
  1. It shows the processes (actions) that take place
    1. It shows the decisions and repetitions that take place
      1. 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
1. 'Fake code'
2. Part way between English sentences, and programming code
3. It is language neutral (it can be read by programmers who are able to use any language)
4. Dry Run - Walking through an algorithm which sample data, running each step manually
5. Trace Table - A table that follows the values of variables to check for accuracy

Next up

Description

Resource summary

Similar

	Created by 2402 2003 about 6 years ago