Your browser **doesn't support the features required** by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest **Chrome**, **Safari** or **Firefox** browser.

*Mission to Mars*

USD 383 STEM Camp - Day 2

**Sorting Network**

Image Source: CS Unplugged

**How do you shuffle cards?**

- What items do you need?
- What tools do you need?
- What skills do you need?
- What prior knowledge do you need?

**Algorithm**

A finite list of specific instructions for carrying out a procedure or solving a problem

**Euclid**

Image Source: Wikipedia

**Euclid's Algorithm (GCD)**

- Start with 2 numbers, A and B
- If either one is zero, the answer is the other number
- Subtract the smaller number from the larger number
- Repeat steps 2 - 4 until an answer is found

**Example: GCD of 1071 & 462**

**Example: GCD of 1071 & 462**

- 1071, 462
- 609, 462
- 147, 462
- 147, 315
- 147, 168
- 147, 21
- 126, 21
- 105, 21
- 84, 21
- 63, 21
- 42, 21
- 21, 21
- 21, 0
**21**

**Sorting Algorithms**

- Insertion Sort
- Bubble Sort
- Merge Sort
- Quicksort

**Insertion Sort**

Image Source: Wikipedia

- Choose an element from the source
- Place it in the correct place in the destination
- Repeat until source is emtpy

**Bubble Sort**

Image Source: Wikipedia

- Compare the first two elements
- If they are out order, swap them
- Move one element over and repeat
- When the end is reached, start over
- Continue until no more swaps are made

**Big O Notation**

- A way to express the complexity of an algorithm
- Approximates the number of steps needed based on the size of the input
- Assumes the input is a "worst case" input

**Bubble Sort - Worst Case?**

- 3, 2, 5, 4, 7, 6, 9, 8, J, 10, K, Q, A
- A, 2, K, 3, Q, 4, J, 5, 10, 6, 9, 7, 8
- A, Q, K, 10, J, 8, 9, 6, 7, 4, 5, 3, 2
- A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2
- 2, 4, 6, 8, 10, Q, A, 3, 5, 7, 9, J, K

**Bubble Sort - Worst Case?**

- 3, 2, 5, 4, 7, 6, 9, 8, J, 10, K, Q, A - 6
- A, 2, K, 3, Q, 4, J, 5, 10, 6, 9, 7, 8 - 42
- A, Q, K, 10, J, 8, 9, 6, 7, 4, 5, 3, 2 - 73
- A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2
**- 78** - 2, 4, 6, 8, 10, Q, A, 3, 5, 7, 9, J, K - 21

**Bubble Sort - Worst Case?**

**Sorting Algorithms**

- Insertion Sort - O(n
^{2}) - Bubble Sort - O(n
^{2}) - Merge Sort
- Quicksort

**Merge Sort**

Image Source: Wikipedia

**Merge Sort**

- Split the items into two halves
- Repeat step 1 until each has 1 item
- Choose 2 parts and merge them together by choosing the smallest item repeatedly from the front of each part
- Continue merging parts together until no more remain

**Quicksort**

Image Source: Wikipedia

**Quicksort**

- Choose an item from the list as a "pivot"
- Put all items less than that item to its left, and put all items greater to its right
- Repeat these steps for the items on each side of the pivot.

**Sorting Algorithms**

- Insertion Sort - O(n
^{2}) - Bubble Sort - O(n
^{2}) - Merge Sort - O(n log n)
- Quicksort - O(n
^{2}) - avg. O(n log n)

**Hydrazine - N _{2}H_{4}**

Image Source: Wikipedia

**Chemistry**

- Hydrazine → N
_{2}H_{4} - N
_{2}H_{4}+*Iridium Ionizer*→ 2N + 4H - Oxygen Reclaimer → O
- Plant Respiration → O
- 2H + O +
*Fire*→ H_{2}O