Algorithms

What is an Algorithm?

• A set of instructions for solving a problem
• A sequence of steps that can be followed to complete a task
• A recipe

Examples

Bake a Cake

• Preheat oven to 350 degrees.
• Mix flour, sugar, and baking soda in a bowl.
• Add 2 eggs, 1 cup milk, and 1tsp vanilla.
• Mix well.
• Pour into a greased baking pan.
• Bake for 30 minutes.

Determine if Number is Even or Odd

• Divide the number by 2.
• If the remainder is 0, the number is even.
• Otherwise, the number is odd.

Find the Largest Number in a Set

• Set the largest number to the first number in the list.
• For each number in the list:
  • If the number is larger than the largest number, set the largest number to the current number.
  • Otherwise, do nothing.
  • Repeat for each number in the list.

Structured Programming

Structured programming forms the basis of all modern programming languages, and can be used to implement algorithms.

The three basic control structures are:

Sequence

• Execute instructions order, one after the other.
• (Not out of order).

Selection

• Choose between two or more logical branches based on a condition.
• "If-then-else"

Iteration

• Repeat a set of instructions until a condition is met.
• "Looping"

Where do we see these structures in the algorithms above?

Applications and Domains

Thinking algorithmically:

While human brains are often compared to computers, they are actually quite different. In order to understand how computers work, we need to think in "instructions", or discrete steps.

As we move through the applications below, let's think about the "humanlike" and "computerlike" ways of solving problems.

Sorting

"How do we arrange a set of items in a specific order?"

• Bubble sort
• Insertion sort
• Merge sort
• Quick sort

Searching

"How do we find a specific piece of information?"

• Linear search
• Binary search
• Depth-first search
• Breadth-first search

Encryption

"How do we encode/decode information to and from human readable?"

• RSA
• AES
• Triple DES

Compression

"How do we represent the same information with fewer bits?"

• Huffman coding
• Lempel-Ziv-Welch (LZW)
• Discrete cosine transform (DCT)

Pathfinding

"How do we find the optimal path between two points?"

• Dijkstra's algorithm

Flocking

"How do we simulate flock behavior?"

• Boids algorithm

Network Analysis / Search Ranking

• "How do we model the spread of a virus?"
• "How do we match text from an Internet search to relevant results?"
• "How do we recommend content on social media?"

Classification

"How do we categorize items from a set of data?"

• Naive Bayes
• Decision tree
• Random forest
• Support vector machine (SVM)
• K-nearest neighbors (KNN)
• Neural network

Prediction

"How do we predict a future value based on a set of data?"

• Linear regression
• Logistic regression
• Polynomial regression
• Markov chain
• Monte Carlo method
• Neural network

Reinforcement Learning

"How do we get a computer to learn on its own?"

• Q-learning
• Temporal difference (TD) learning

Critical Thinking Exercise