Waste less time on Facebook — follow Brilliant.
×
Back to all chapters

Computer Science Algorithms

How to make a computer do what you want, with strategies for elegance and efficiency.

Algorithms

Chapter 1 of 5

Introduction to Algorithms

             

Computer science (CS) is often considered to be a flavor of math. In fact, some of the earliest CS founders were labeled mathematicians in their time!

CS is similar to math in that we can apply abstract methods to attack certain problems. For example, given a problem about solving for the roots of a polynomial, we can try a set of strategies ranging from factoring to Descartes' rule of signs.

There are systematic ways to approach CS problems, and algorithms are simply a generic name for how we approach CS topics.

In this course, we hope to clarify what algorithms are, and investigate some very common and important problems.

Algorithms by definition are simply sequences of actions.

Their relationship to functions? We take an input and terminate with some output.

However, the difference between functions and algorithms is that algorithms use a simple sequence of steps to iteratively make a problem easier. Furthermore, an algorithm gives a method for transitioning from any state to any other state and we can break problems down into many states.

For example, sorting a list takes a sequence of steps where, at any point, there are intermediate states where the list may be partially ordered.

Consider the concept of a dictionary.

We use dictionaries (or its digital counterpart) in real life frequently. With a dictionary, given a keyword, we are able to search for an entry.

Suppose we have a friend, Xander, and want to search for his phone number. We simply look at our contacts and find a phone number under the name Xander!

But, how do we store a series of objects such as pairs of names and phone numbers? And after we have stored them, how do we call upon them and get the phone numbers back?

These are the types of questions we will explore in the next few sections.

Let's simplify our previous problem.

How do we store just a set of names? The most common structure is an array, or a list of objects.

Suppose our friends' names are Gary, Ursula, Teresa, and Nigel. A list of these names is simply an ordered set where our \(1^\text{st}\) entry is Gary, the \(2^\text{nd}\) entry is Ursula, and so on to the \(4^\text{th}\) entry of Nigel.

In computer science, the ordering process is slightly different. We almost always start with the index \(0\). So our \(0^\text{th}\) entry is Gary, \(1^\text{st}\) entry is Ursula, and so on.

So we might store our list like this:

names = ['Gary', 'Ursula', 'Teresa', 'Nigel'].

What is this list when sorted in alphabetical order from least to greatest?

Suppose we have our list:

names = ['Gary', 'Ursula', 'Teresa', 'Earnest', 'Nigel'].

How do we search for our friend Earnest? If we do not know the order of our list, just that the list \(\verb !names!\) contains the name 'Earnest', the only thing we can do is simply start at the front of the list and look at each entry until we get to 'Earnest'. In the list above, how many entries will we look at using this process to find 'Earnest'?

Suppose we have a list of size \(N\), but we do not know anything about its structure. To check whether this list contains a certain element, what is the number of elements in the list we must check in the worst case?

As we saw before, if we have an unordered list of elements, we must go through all of them to check if it contains a certain element we're looking for. This is very expensive! Think about a company such as Google whose search engine indexes websites. There are over one billion websites on the internet. To find the ones that contain a certain keyword, do you think Google would run an algorithm that goes through every one?

Sorting lists therefore is a very powerful algorithm that rises from a very simple need: searching quickly.

This is an example of how studying algorithms goes... We are presented with a simple problem (such as finding a phone number), and then we figure out how to solve this problem quickly.

Before we start looking at specific algorithms, we will first learn how to judge whether a solution is acceptable.

×

Problem Loading...

Note Loading...

Set Loading...