Lecture 1: Introduction to Algorithms

Algorithms:

Your friend tells you about a great science fiction book you should read, Ender’s Game by Orson Scott Card. You tell your friend you have not read or seen the book but will try to pick up a copy at a garage sale you will be at later that afternoon. Later, at the garage sale, you are shocked to find the sale has more than 1000 books displayed in various unorganized stacks along the driveway. You begin your search for Ender’s Game.

How many books will you need to inspect to determine if they have Ender’s Game?

You will need to keep inspecting books until either 1) you find Ender’s Game, or 2) you have ensured that the book is not among those for sale. If you stop searching a few books short, or you skip some books along the way, you can never be certain that Ender’s Game was not among the collection of books on the driveway.

Write down a numbered sequence of steps to search for Ender’s Game:

 

The steps you listed above form an algorithm. An algorithm is a step-by-step procedure (with a finite number of steps) that, when followed from beginning to end, solves a particular problem. Note that these steps should be well-defined steps that can be easily and correctly followed every time the algorithm is executed; for example, you can’t use the following step: “3) guess randomly at whether the book is in the stack” as a legitimate step.

Here is my algorithm for finding a book at the garage sale:

  1. Start at the first book in the collection of books; call this your “current book”; goto step 2.
  2. Look at the title of “current book” to see if it is Ender’s Game. If it is, go to step 6; otherwise go to step 3.
  3. If your “current book” is the last book in the collection, then you have not found the book you are searching for and will go to step 5, otherwise go to step 4.
  4. Find the next book in the stack after “current book” and make that book now be your “current book”. Go back to step 2.
  5. It is confirmed that no book in the collection has the title Ender’s Game. Since we have now checked every book in the collection, stop.
  6. You have found the book you are looking for. Congratulations. Stop.

Note that you may execute step 2 through step 4 many times, depending on the number of books in the collection and whether you are able to find the book. There are two conditions for which you will stop, 1) if you reach the end of the collection and have not found the book (Step 5), or 2) if you find the book among the collection (Step 6).

This type of search is called a linear search because one needs to exhaustively inspect every element of a collection, one-at-a-time (in a linear fashion), to determine if an object is among the collection, or not.

After about 20-minutes, the garage sale proprietor observes you searching through all the books. She interrupts you to say “If it helps, the books on the north side of the driveway are all mysteries, those by the garage are biographies, the south side are trashy novels, and the stack at the end of the driveway are science fiction."

Does this information make the search for Ender’s Game easier?

How?

 

Is there any additional type of information the proprietor may reveal that would help your search?

What might that be?

 

Even this small nugget of information about the organization of the books is very helpful. Since your friend told you Ender’s Game is a sci-fi book, you can now limit your search to the stacks of books at the end of the driveway containing only the science fiction books, and disregard all the other books.

Will you need to look through all the science fiction books to determine if Ender’s Game is in the sale?

If the only information you have about the book is that it is science fiction, you will need to inspect every one of the science fiction books to determine if Ender’s Game is among the collection. You will need to apply the linear search algorithm to the subset of books in the science fiction stack, but thankfully, only that science fiction stack.

After completing your search of the garage sale, you determine that Ender’s Game is not among the books available for sale. How does this make you feel?

Later that day, you have time to visit the public library to find a copy of Ender’s Game. The library computer system is down, making it impossible to do an online search for books. (They should have hired an Illinois CS student to design it!) Luckily, you remember that libraries systematically organize their books using the Dewey Decimal System. The Dewey Decimal System is a classification of books by subjects into numbered categories. You, being a library rat, have the general category list memorized:

You head off toward the 800’s, Literature and Rhetoric, in search of Ender’s Game. On the way, you remember you are wearing your “i heart sci-fi” necklace, providing the more precise location of the science fiction section, 808.838. When you arrive at this section, you estimate about 30 books are shelved here and appear to be alphabetical by author’s last name. Just a few books into your search, you find Ender’s Game by Orson Scott Card.

It took 45 minutes at the garage sale to search approximately 1000 books. The public library has 40,000 books; 40 times the number at the garage sale.

Do you think it took 40 times as long to determine if the library had the book you were searching for?

Why?

 

At this point, you may be thinking, “Whoa, I think I enrolled in an ‘Introduction to literature or Library Sciences 101’ course.” You may be somewhat surprised to learn that the methods of thinking and the algorithms discussed above are computer science.

Computer science is not primarily about computers, but rather it is the study of computation. The subject of computation involves many subfields, one of which is algorithms. In the algorithms for finding a book described above, you hopefully noticed that the speed at which we can find a book depends on the organization of the books. Knowing that certain books are in certain areas of the driveway or library speeds up the search considerably. We say that the searching is more efficient. Having the books sorted alphabetically in the sci-fi section makes the search even easier or more efficient.

We humans are an inherently lazy bunch. If we can invent a machine to do work for us, we will. This is where computers come in. Ideally, we can have a machine find a book for us. While the machine is searching for the book, we can be doing some other important task, like playing Plants vs. Zombies. If a machine can find our book in a fraction of the time it takes a human, well, that’s even better. This is where we find ourselves along the timeline of human civilization, in a period where we are designing, building and optimizing machines to perform computing tasks that we are either less efficient at or entirely incapable of. In this course, we will begin our study in the development of algorithms and programs that will be executed by computers. In later courses in computer science, you will learn how to design and build these computing machines.

The important point about the examples above is that we cannot think about what work needs to be done without thinking of how that work needs to be done. In the first example, in searching for Ender’s Game among a collection of 1000 unsorted books, one needs to examine every single book to ensure that our book cannot be found in the collection. This is an inherent property of the problem. Even if you search the collection with a computer, the computer will still have to examine each book title to determine if our book is in the collection. If you use a different computer, one that is 100 times faster than your current computer, you will still need to look at all 1000 book titles to determine if your desired book is among the collection. A faster computer can only perform each individual step of an algorithm faster; it cannot eliminate any of the steps of the algorithm, since every one of those steps still needs to be performed in order for the algorithm to run correctly. If your fast computer only looks at the first 999 books, the last book could have been Ender’s Game and neither you or the program would have any way of knowing for certain if it is in the collection—except by continuing onward and inspecting that final book.

This course is not just about computer programming. We will be doing a fair amount of that, but we will also introduce you to some of the basic theoretical ideas in computer science, as well as introducing the skill of programming computers. You will be gaining a high-level understanding of how computers work as machines and you will be learning how to design high-quality and efficient software. We will address algorithm design and analysis and build up to program design techniques for larger software projects. These topics are important concepts and skills in computer science, but they are only the tip of the iceberg.