2.1 Algorithms

2.1 Algorithms

1. computational thinking

   • Abstraction
     • getting rid of irrelevant information and focusing on important information
     • using symbols and variables to represent "real world" problems
   • decomposition
     • big problem ==> smaller problems
       • easier to solve
       • independent of others
     • problems can be decomposed in different methods
   • Algorithmic thinking
     • identifying steps in solving problems

2. linear search

   • doesn't need to be in order
   • goes through one by one
   • IF correct, stop
   • ELSE carry on to next value
   • simpler to write

3. binary search

   • list needs to be in order
   • take middle value
   • compare to required value
   • IF correct then stop
   • ELSEIF it is larger, take values on the left
   • IF smaller, take values to the right
   • longer, more complex

4. sorts

   • bubble
     • goes through list repeatedly swapping elements until in correct order
   • merge
     • list is split in two and combined two at a time
   • insertion
     • each item is taken in turn compared to an ordered list. it is placed in correct position

5. flowchart

   • input / output data
   • processes
   • decisions
   • shapes rep functions
   • lines show flow control

6. pseudocode

   • 'fake' code
   • partway between sentences and coding

7. dry run

   • walking through and running each step manually
   • trace table
     • table that follows the values of variables to check for accuracy