# Missing Document Title

theme: Next, 1

# Algorithms Continued

# So you've been challenged to come up with an algorithm!

Where do we start? What kind of language do we use? How detailed do we need to be?

# [fit] Algorithm Detail

The more details, the better!

New developers/algorithm-creators don't specify enough detail.

Typical new SDG student generates about a **third** to a **fourth** the amount of detail required in an algorithm.

# [fit] So, how do we learn and practice?

Use precise languageBreak problems into smaller piecesLearn common problem-solving approachesPractice, practice, practice ... and more practice.

It takes **time**

# [fit] Precise language

We will be using programming languages like

`C#`

and`SQL`

and`TypeScript`

to write our algorithms.For now, we will be using

**human**language,**English**specifically, which is an imprecise language.

# [fit] Use your imagination

- When creating algorithms, pretend that you are giving instructions to:
- A baby that just learned to speak
- A robot that only knows a few specific words or phrases
- The pickiest, pedantic person you know.
- ... then
**double**or**triple**the specificity and detail

# Break a problem down

# Zeno's Dichotomy Paradox

Who knows it?

# Zeno's Dichotomy Paradox

That which is in locomotion must arriveat the halfway stage before it arrivesat the goal.— as recounted by Aristotle, Physics VI:9, 239b10

# Mathematically, you **do** arrive at your goal

Curious students can see me after class to see how

# [fit] Take a significant problem and

# [fit] break it into (two?) smaller problems

# [fit] We might know this as "delegation"

# [fit] We may not know how to

# [fit] solve an entire problem.

# [fit] We can look at parts

# [fit] that we *can* solve

# [fit] Example: Spaghetti and Sauce

# [fit] Major Steps

- Make Sauce
- Make Spaghetti

# [fit] Break this down

[.column]

- Sauce:
- Garlic, Onion, Basil, Tomatoes

[.column]

- Spaghetti
- Eggs, flour, semolina, salt
- Make dough
- Rise
- Roll
- Cut
- Cook

# [fit] Even this is too simplistic

Anyone who cooks knows I've summarized many of these steps.

# Breaking down problems into manageable steps is an **art**

# [fit] Transform a problem

Take a problem in an area we don'tknow how to solve and turn it intoone that we do!

[.autoscale: true]

# [fit] Here is a simple to state problem.

# [fit] See if you can solve it (no computer usage)

# [fit] I'll give you thirty seconds

# [fit] Ready, set, go ...

# [fit] Add up the first 1000 numbers

# [fit] `1 + 2 + 3 + ... + 998 + 999 + 1000`

# [fit] Did you do it?

# [fit] Transforming the problem

# [fit] `1 + 2 + 3 + ... + 998 + 999 + 1000`

# [fit] Transforming the problem

# [fit] `1 + 2 + 3 + ... + 998 + 999 + 1000`

[.column]

`1`

`2`

`3`

[.column]

`1000`

`999`

`998`

# [fit] Transforming the problem

# [fit] `1 + 2 + 3 + ... + 998 + 999 + 1000`

[.column]

`1`

`2`

`3`

[.column]

`+`

`+`

`+`

[.column]

`1000`

`999`

`998`

# [fit] Transforming the problem

# [fit] `1 + 2 + 3 + ... + 998 + 999 + 1000`

[.column]

`1`

`2`

`3`

[.column]

`+`

`+`

`+`

[.column]

`1000`

`999`

`998`

[.column]

`= 1001`

`= 1001`

`= 1001`

# [fit] Transforming the problem

# [fit] `1 + 2 + 3 + ... + 998 + 999 + 1000`

There are 500 of these pairs.500 * 1001 = 500,500

[.column]

`1`

`2`

`3`

[.column]

`+`

`+`

`+`

[.column]

`1000`

`999`

`998`

[.column]

`= 1001`

`= 1001`

`= 1001`

# General formula

$$\frac{n(n + 1)}{2}$$

# Breaking problem down: Mail

As another example ... Donald Knuth gives themethod a post office typically uses to routemail: letters are sorted into separate bagsfor different geographical areas, each ofthese bags is sorted into batches forsmaller sub-regions, and so on until theyare delivered.

# Breaking problem down, one bit at a time.

`Find the largest number in a list.`

# Reduce the problem by ONE

The largest number in a list is either:

- The first number in a list
**or**- If other numbers are remaining in the list ... the largest number is in the remainder of the list

# Example:

Find largest number in:

`43,71,75,66,48`

# Example

- Largest number of
`43,71,75,66,48`

is either`43`

**or**- Largest number in
`71,75,66,48`

# Example

- Largest number of
`71,75,66,48`

is either`71`

**or**- Largest number in
`75,66,48`

# Example

- Largest number of
`75,66,48`

is either`75`

**or**- Largest number in
`66,48`

# Example

- Largest number of
`66,48`

is either`66`

**or**- Largest number in
`48`

# Example

- Largest number of
`48`

is`48`

- So largest number of
`66,48`

is`68`

- So largest number of
`75,66,48`

is`75`

- So largest number of
`71,75,66,48`

is`75`

- So largest number of
`43,71,75,66,48`

is`75`

# Example

Median number in a list

- First sort
- Then find middle number
- If there are an odd count of numbers, take the middle
- If there are even count of numbers, everage the two middle numbers.

# Example

`43,71,75,66,48`

sorted

`43,48,66,71,75`

Middle is 66

# Example

`4,56,97,25,21,2`

sorted

`2,4,21,25,56,97`

Middle is `21`

and `25`

, so median is: `23`

[.build-lists: true]

# 0, 1, few, $$ \infty $$

Solving a problem with

*zero*inputs is typically easySolving a problem with

*one*input is typically easySolving a problem with a

*few*inputs is typically easy due to our natural intuitionSolving a problem with a

*huge*amount of input challenges our intuition and assumptionsSee an example of adding up the first N numbers.

# [fit] Use "0, 1, few, $$ \infty $$" in your thinking process

- Perhaps start with an input size of "a few."
- Use your intuition to understand the problem
- Don't forget about
`0`

and`1`

inputs- (sometimes the problem has a curveball here)

- See if your intuition still works with $$ \infty $$

# [fit] Idea of conditions and loops in algorithms

- When thinking of an algorithm, it often helps to solve a smaller version of the problem
- Then, see if applying that process to each element of the input works.
- This is "looping."
- We'll work with looping
**often**in this class

# [fit] Idea of conditions and loops in algorithms

*"If something is true"* or *"If something is false"* help determine if or when we should do some smaller steps

# [fit] Loop with counting

- "Do the following X times"
- "Do the following until X is less-than/more-than/equal to Y"

# [fit] Computers are *very* good at conditions and loops.

Computers are primarily machines that work with conditions and loops.