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 in the amount of detail required in an algorithm.

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

Use precise language.
Break problems into smaller pieces.
Learn common problem-solving approaches.
Practice, 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 arrive
 at the halfway stage before it arrives
 at 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't
know how to solve and turn it into
one 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 the
method a post office typically uses to route
mail: letters are sorted into separate bags
for different geographical areas, each of
these bags is sorted into batches for
smaller sub-regions, and so on until they
are 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 the middle number
    • If there are an odd count of numbers, take the middle.
    • If there are an even count of numbers, average 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 easy

• Solving a problem with one input is typically easy

• Solving a problem with a few inputs is typically easy due to our natural intuition

• Solving a problem with a huge amount of input challenges our intuition and assumptions

• See 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.