This page is a work in progress.You can help improve it. →

theme: Next, 1

# 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.

• 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

Who knows it?

 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] 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.

# [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]1 + 2 + 3 + ... + 998 + 999 + 1000

[.column]

1 2 3

[.column]

1000 999 998

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

[.column]

1 2 3

[.column]

+ + +

[.column]

1000 999 998

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

[.column]

1 2 3

[.column]

+ + +

[.column]

1000 999 998

[.column]

= 1001 = 1001 = 1001

# [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 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

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

© 2017 - 2021; Built with ♥ in St. Petersburg, Florida.