Algorithms=2.1 V2

Algorithms=2.1 V2

1. 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

2. 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

3. 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

4. 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

5. 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

6. 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