No history yet

Introduction to Algorithms

What Is an Algorithm?

Think about the last time you followed a recipe. You had a list of ingredients and a set of instructions. Follow the steps in order, and you end up with a cake. Change the order or skip a step, and you get a mess. An algorithm is just like that recipe: it’s a clear, step-by-step guide for solving a problem.

Algorithm

noun

A finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.

Computers need these precise instructions for everything they do, from sorting a playlist to recommending your next movie. Without algorithms, our digital world would grind to a halt. They are the fundamental building blocks of programming and the core of problem-solving in computer science.

Good vs. Bad Instructions

Not all recipes are created equal, and the same is true for algorithms. A good algorithm isn't just one that works; it's one that works well. So, what makes an algorithm effective?

First, it must be correct. It has to produce the right answer every single time. A navigation app that sometimes gives wrong directions isn't very useful.

Second, it must be finite. An algorithm has to eventually finish. It can't run forever in an infinite loop.

Finally, and most importantly, a good algorithm is efficient. It solves the problem without wasting resources, especially time and computing power. Imagine searching for a name in a phone book. You could start at the first page and read every single name until you find the one you're looking for. That would work, but it would be incredibly slow. A better way would be to open the book to the right section based on the first letter of the name. Both methods are correct, but one is vastly more efficient.

Three Ways to Solve a Problem

Programmers have developed many strategies for writing algorithms. These strategies, or techniques, provide a framework for tackling different types of problems. Let's look at three common approaches.

Brute Force: Try Everything

The brute-force method is the most straightforward approach. It relies on sheer computing power to try every single possibility until it finds the solution. Think of trying to unlock a 4-digit combination lock. The brute-force way is to start with 0000, then 0001, then 0002, and so on, until the lock opens.

This approach is simple to design and is guaranteed to find the solution. However, for many problems, it's just too slow to be practical. As the number of possibilities grows, the time it takes can become astronomical.

Divide and Conquer: Split it Up

This clever strategy tackles a big problem by breaking it into smaller, more manageable subproblems. It solves each subproblem individually and then combines their solutions to solve the original big problem.

Remember our phone book example? That's a classic use of divide and conquer. Instead of checking every name (the big problem), you open to the middle. You see if the name you want comes before or after the names on that page. You've just divided the problem in half. You discard one half of the book and repeat the process on the remaining section. You keep splitting the problem until you've narrowed it down to a single page and find the name.

This approach is often dramatically more efficient than brute force.

Greedy Algorithms: Take the Best Next Step

A greedy algorithm solves a problem by making the choice that seems best at that moment. It doesn't worry about the future; it just picks the locally optimal option at each step, hoping it will lead to a globally optimal solution for the whole problem.

Imagine you're a cashier giving change. If you need to give back 68 cents, your greedy approach would be to start with the largest coin possible (a quarter), then the next largest (another quarter), then a dime, then a nickel, and finally three pennies. In this case, the greedy method works perfectly to give the fewest number of coins.

However, this strategy doesn't always yield the best result. If you had a strange currency system with coins worth 1, 7, and 10 cents, and you needed to give 14 cents in change, the greedy choice would be one 10-cent coin and four 1-cent coins (five coins total). The better solution is two 7-cent coins (two coins total). Sometimes, the best immediate choice isn't part of the best overall solution.

Quiz Questions 1/6

Which of the following is the best analogy for an algorithm, as described in the text?

Quiz Questions 2/6

According to the text, what are the three essential properties of a good algorithm?

Understanding these basic techniques is the first step toward thinking like a programmer and solving problems in a structured, efficient way.