What is an Algorithm?

/
fundamentals

This tutorial is a part of the Data Structures and Algorithms class:

The importance of information

  • Nowadays and certainly into the far future, no business can operate without the help of software.
  • Software stores (a lot of) information, processes it then returns useful information that will help business save money or time or both.
  • Examples: farming, managing money (banking), transportation, ...

importance of software

The only software problem

  • Software stores (a lot of raw) information that represents something in real life. The only problem is to try extracting useful information that can drive actions to make/save time/money from raw information. And doing it efficiently in terms of computer resources: CPU/RAM/bandwidth.
  • Example: Going from San Jose -> San Francisco. The shortest path saves traveling time and saves gas money.

best route sj sf

Typical classes of the software problem

The software problem is to find the useful information from existing information. Useful is key here. Typical classes of useful information (software problem) are:

  1. Maximization (profit, gain, ...)
  2. Minimization (loss, time, …)
  3. Finding all available options with given restrictions (list of choices on solutions, paths, …)
  4. Finding most optimal solution with given restrictions (travel path given time and cost restriction)
  5. Finding a truth (binary tree height, material volume of a hollow sphere, ...)

What is an algorithm?

  • Your algorithm: simply your solution for a software problem you are asked to solve.
  • A popular algorithm you'll learn: is a well-defined solution for a particular class of software problem.
  • Why do you have to learn popular algorithms? Because those classes of problem are popular. And you'll most likely need to solve them if you work in software. To understand the algorithm, you must understand the class of the problem it solves first.
  • "I think I can come up with an algorithm myself to solve the problem". Yes, but can you do it within 30 minutes? Will your algorithm be more efficient than the one humankind has been perfected for the last 70 years?
  • Example: shortest path from point A to point B -> breadth first search.
  1. Understand the class of problem it solves clearly.
  2. Quickly identify if the given problem (by its special characteristics) is solvable with a learnt algorithm.
  3. Quickly explain, code and calculate Big O complexity of the solution.
  4. ✅ Collected a new tool in your toolbox.

Common mistake while talking about an algorithm

  • Mistake: does not understand what class of problem the algorithm solves.
  • How humans came up with an algorithm: a very specific problem emerges, repeatedly -> understand the problem -> seek solutions -> choose the best optimal solutions to teach = the algorithm you learn. So understanding the problem clearly must be the first and important part of learning an algorithm.

Do learning algorithms kill creativity?

No, because:

  • Adapting a non-conformed problem into the algorithm you already learnt requires creativity.
  • Many problems require a combination of a few algorithms to solve.
  • These algorithms you'll learn are basic lego pieces. What you can build with these pieces is an endless possibility.

Real life interview questions

  1. Why do you want to learn algorithms?
  2. How do you know if a problem is solvable by a learnt algorithm?
  3. What is the only software problem?
  4. How does algorithms help in the big picture of doing software engineering?