Unit 2.1 - Khang Duong

Unit 2.1 - Khang Duong

1. Computational Thinking

   • the use of computers to solve problems
     • This includes producing an algorithm to solve a problem After, using abstraction, decomposition and algorithmic thinking to solve a problem

2. Abstraction

   • Representing ‘real problems’ into a computer using variables and symbols and removing unneeded elements of the problem

3. Decomposition

   • breaking down a large problem into smaller sub problems
     • They can be independent from other tasks and can also be tested independently. After they have been tested with solutions produced, they can be put back together into the original problem to be solved. A problem can be decomposed in many different ways.

4. Algorithmic Thinking

   • identifying the steps in solving a problem

5. Binary Search

   • Ordered list is split into 2 with each comparison
     • The list needs to be IN ORDER. Take middle value Compare to value you are looking for IF value you are looking for, STOP. ELSEIF larger than value looking for, take values to left of middle value IF smaller than value looking for, take values to the right of middle value Repeat with a new list

6. Linear Search

   • Each item in a list is checked into order
     • Binary search ONLY works when IN ORDER Check its first value If is it value, stop ELSE check the next value Repeat until you have checked all elements and not the value you want

7. Bubble Sort

   • moving through a list repeatedly, swapping elements in wrong order
     • Take 1st element and 2nd element from the list Compare them IF element1 > element2, SWAP Else, do nothing Move along list to next pair and if no more elements, go to 1, ELSE go to 2

8. Merge sort

   • a list is split into individual lists and then combined 2 at a time
     • Split all into individual lists Compare first element in both lists Put smallest in new list Compare next element in 1st list with the 2nd element in 2nd list Put smallest in new list Re peat until merged Split a list into individual lists Merge list in pairs putting smallest first Merge lists Keep merging until in order

9. Insertion sort

   • each items is taken in turn, compare to the items in a sorted list and placed into the correct position
     • Element 1 is a sorted list Rest of elements are unsorted Compare first element unsorted with each element in sorted IF it is smaller, put it in front of element IF larger compare with rest IF no more in sorted, put it in final position Repeat until all in unsorted are in sorted.

10. LIST

    • a set of data
      • Ordered list
        • elements are arranged in a sequence
      • Unordered list
        • unarranged elements

11. .

    • Algorithm
      • the series of steps to solve a problem or perform an action
    • Flowchart
      • a diagram that shows the inputs, outputs and processes in an algorithm
    • Process
      • an action that takes place
    • Pseudocode
      • simplified programming code that is not language specific, used to design algorithms

12. Dry run

    • walking through an algorithm, running each step manually

13. Trace table

    • a table that follows the values of variables to check for accuracy