Introduction to Algorithms - Chapter 1

• Introduction
• So, What are Algorithms?
• Interesting Algorithms / Problems
  • Shortest Paths

Introduction

I will be posting my study notes that I made while reading the book Introduction to Algorithms. I hope it’ll be just as good as reading the original book. There’ll be quotations from the book, but more often than not, I’ll be leaving some ideas of my own, as blatantly copying parts of a book doesn’t make good notes.

If there is any question you would want to ask, just comment about it in the comments section below.

So, What are Algorithms?

We have seen programs. They take input, do some work on it, and then give out output. We could call the program that does this an algorithm, if it does the same thing for all inputs given, and gives the right output.

Or, in the words of the authors themselves:

An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

Let’s take a sorting algorithm as an example, as the authors themselves have:

The input would be a set of numbers $\langle a_1 , a_2 , a_3 , \ldots , a_n \rangle$ and the output is some permutation of the same, i.e., another set of the same n numbers $\langle a'_1 , a'_2 , a'_3 , \ldots a_n \rangle$

An algorithm, in this case would be the steps required to get the output from the input.

Interesting Algorithms / Problems

Interesting Algorithms will be a section that will occur frequently in this series, and it will list all the Algorithms listed in this chapter that I found interesting,

In this chapter, we have the Shortest Paths problem.

Shortest Paths

This Problem, as the title says, is to find the shortest path from a place A, to another place B. I’m sure you would be able to think of lots of applications of this. In case you aren’t sure, you can think of the problem where there are multiple ways to get to a destination and you don’t really know how to get there in the least amount of distance. Since, on road, least distance usually means least time, you will be able to get there faster.

So, you go to Google Maps, or some other mapping software and find the shortest route. The way these maps find the distance is proprietary, but it is usually some form of a shortest paths algorithm, and is usually a form of Dijkstra, or the A* algorithm (both of which will be discussed later).