Introduction

Algorithms are the recipes that make efficient programming possible. They explain how to sort records, search for items, calculate numeric values such as prime factors, find the shortest path between two points in a street network, and determine the maximum flow of information possible through a communications network. The difference between using a good algorithm and a bad one can mean the difference between solving a problem in seconds, hours, or never.

Studying algorithms lets you build a useful toolkit of methods for solving specific problems. It lets you understand which algorithms are most effective under different circumstances so that you can pick the one best suited for a particular program. An algorithm that provides excellent performance with one set of data may perform terribly with other data, so it is important that you know how to pick the algorithm that is the best match for your scenario.

Even more important, by studying algorithms you can learn general problem-solving techniques that you can apply to other problems even if none of the algorithms you already know is a perfect fit for your current situation. These techniques let you look at new problems in different ways so that you can create and analyze your own algorithms to solve your problems and meet unanticipated needs.

In addition to helping you solve problems while on the job, these techniques may even help you land the job where you can use them! Many large technology companies, such as Microsoft, Google, Yahoo!, IBM, and others, want their programmers to understand algorithms and the related problem-solving techniques. Some of these companies are notorious for making job applicants work through algorithmic programming and logic puzzles during interviews.

The better interviewers don't necessarily expect you to solve every puzzle. In fact, they will probably learn more when you don't solve a puzzle. Rather than wanting to know the answer, the best interviewers want to see how you approach an unfamiliar problem. They want to see whether you throw up your hands and say the problem is unreasonable in a job interview. Or perhaps you analyze the problem and come up with a promising line of reasoning for using algorithmic approaches to attack the problem. “Gosh, I don't know. Maybe I'd search the Internet,” would be a bad answer. “It seems like a recursive divide-and-conquer approach might work” would be a much better answer.

This book is an easy-to-read introduction to computer algorithms. It describes a number of important classical algorithms and tells when each is appropriate. It explains how to analyze algorithms to understand their behavior. Most importantly, it teaches techniques that you can use to create new algorithms on your own.

Here are some of the useful algorithms this book describes:

• Numerical algorithms such as randomization, factoring, working with prime numbers, and numeric integration
• Methods for manipulating common data structures such as arrays, linked lists, trees, and networks
• Using more-advanced data structures such as heaps, trees, balanced trees, and B-trees
• Sorting and searching
• Network algorithms such as shortest path, spanning tree, topological sorting, and flow calculations

Here are some of the general problem-solving techniques this book explains:

• Brute-force or exhaustive search
• Divide and conquer
• Backtracking
• Recursion
• Branch and bound
• Greedy algorithms and hill climbing
• Least-cost algorithms
• Constricting bounds
• Heuristics

To help you master the algorithms, this book provides exercises that you can use to explore ways you can modify the algorithms to apply them to new situations. This also helps solidify the main techniques demonstrated by the algorithms.

Finally, this book includes some tips for approaching algorithmic questions that you might encounter in a job interview. Algorithmic techniques let you solve many interview puzzles. Even if you can't use algorithmic techniques to solve every puzzle, you will at least demonstrate that you are familiar with approaches that you can use to solve other problems.

Algorithm Selection

Each of the algorithms in this book was included for one or more of the following reasons:

• The algorithm is useful, and a seasoned programmer should be expected to understand how it works and use it in programs.
• The algorithm demonstrates important algorithmic programming techniques you can apply to other problems.
• The algorithm is commonly studied by computer science students, so the algorithm or the techniques it uses could appear in a technical interview.

After reading this book and working through the exercises, you will have a good foundation in algorithms and techniques you can use to solve your own programming problems.

Who This Book Is For

This book is intended primarily for three kinds of readers: professional programmers, programmers preparing for job interviews, and programming students.

Professional programmers will find the algorithms and techniques described in this book useful for solving problems they face on the job. Even when you encounter a problem that isn't directly addressed by an algorithm in this book, reading about these algorithms will give you new perspectives from which to view problems so that you can find new solutions.

Programmers preparing for job interviews can use this book to hone their algorithmic skills. Your interviews may not include any of the problems described in this book, but they may contain questions that are similar enough that you can use the techniques you learned in this book to solve them.

Programming students should be required to study algorithms. Many of the approaches described in this book are simple, elegant, and powerful, but they're not all obvious, so you won't necessarily stumble across them on your own. Techniques such as recursion, divide and conquer, branch and bound, and using well-known data structures are essential to anyone who has an interest in programming.

Getting the Most Out of This Book

You can learn some new algorithms and techniques just by reading this book, but to really master the methods demonstrated by the algorithms, you need to work with them. You need to implement them in some programming language. You also need to experiment, modify the algorithms, and try new variations on old problems. The book's exercises and interview questions can give you ideas for new ways to use the techniques demonstrated by the algorithms.

To get the greatest benefit from the book, I highly recommend that you implement as many of the algorithms as possible in your favorite programming language or even in more than one language to see how different languages affect implementation issues. You should study the exercises and at least write down outlines for solving them. Ideally you should implement them, too. Often there's a reason why an exercise is included, and you may not discover it until you take a hard look at the problem.

Finally, look over some of the interview questions available on the Internet, and figure out how you would approach them. In many interviews you won't be required to implement a solution, but you should be able to sketch out solutions. And if you have time to implement solutions, you will learn even more.

Understanding algorithms is a hands-on activity. Don't be afraid to put down the book, break out a compiler, and write some actual code!

This Book's Websites

Actually, this book has two websites: Wiley's version and my version. Both sites contain the book's source code.

The Wiley web page for this book is http://www.wiley.com/go/essential-algorithms. You also can go to http://www.wiley.com and search for the book by title or ISBN. Once you've found the book, click the Downloads tab to obtain all the source code for the book. Once you download the code, just decompress it with your favorite compression tool.

To find my web page for this book, go to http://www.CSharpHelper.com/algorithms.html.

How This Book Is Structured

This section describes the book's contents in detail.

Chapter 1, “Algorithm Basics,” explains concepts you must understand to analyze algorithms. It discusses the difference between algorithms and data structures, introduces Big O notation, and describes times when practical considerations are more important than theoretical runtime calculations.

Chapter 2, “Numerical Algorithms,” explains several algorithms that work with numbers. These algorithms randomize numbers and arrays, calculate greatest common divisor and least common multiple, perform fast exponentiation, and determine whether a number is prime. Some of the algorithms also introduce the important techniques of adaptive quadrature and Monte Carlo simulation.

Chapter 3, “Linked Lists,” explains linked-list data structures. These flexible structures can be used to store lists that may grow over time. The basic concepts are also important for building other linked data structures, such as trees and networks.

Chapter 4, “Arrays,” explains specialized array algorithms and data structures, such as triangular arrays and sparse arrays, that can save a program time and memory.

Chapter 5, “Stacks and Queues,” explains algorithms and data structures that let a program store and retrieve items in first-in-first-out (FIFO) or last-in-first-out (LIFO) order. These data structures are useful in other algorithms and can be used to model real-world scenarios such as checkout lines at a store.

Chapter 6, “Sorting,” explains sorting algorithms that demonstrate a wide variety of useful algorithmic techniques. Different sorting algorithms work best for different kinds of data and have different theoretical run times, so it's good to understand an assortment of these algorithms. These are also some of the few algorithms for which exact theoretical performance bounds are known, so they are particularly interesting to study.

Chapter 7, “Searching,” explains algorithms that a program can use to search sorted lists. These algorithms demonstrate important techniques such as binary subdivision and interpolation.

Chapter 8, “Hash Tables,” explains hash tables—data structures that use extra memory to allow a program to locate specific items quickly. They powerfully demonstrate the space-time trade-off that is so important in many programs.

Chapter 9, “Recursion,” explains recursive algorithms—those that call themselves. Recursive techniques make some algorithms much easier to understand and implement, although they also sometimes lead to problems, so this chapter also describes how to remove recursion from an algorithm when necessary.

Chapter 10, “Trees,” explains highly recursive tree data structures, which are useful for storing, manipulating, and studying hierarchical data and have applications in unexpected places, such as evaluating arithmetic expressions.

Chapter 11, “Balanced Trees,” explains trees that remain balanced as they grow over time. In general, tree structures can grow very tall and thin, and that can ruin the performance of tree algorithms. Balanced trees solve this problem by ensuring that a tree doesn't grow too tall and skinny.

Chapter 12, “Decision Trees,” explains algorithms that attempt to solve problems that can be modeled as a series of decisions. These algorithms are often used on very hard problems, so they often find only approximate solutions rather than the best solution possible. However, they are very flexible and can be applied to a wide range of problems.

Chapter 13, “Basic Network Algorithms,” explains fundamental network algorithms such as visiting all the nodes in a network, detecting cycles, creating spanning trees, and finding paths through a network.

Chapter 14, “More Network Algorithms,” explains more network algorithms, such as topological sorting to arrange dependent tasks, graph coloring, network cloning, and assigning work to employees.

Chapter 15, “String Algorithms,” explains algorithms that manipulate strings. Some of these algorithms, such as searching for substrings, are built into tools that most programming languages can use without customized programming. Others, such as parenthesis matching and finding string differences, require some extra work and demonstrate useful techniques.

Chapter 16, “Cryptography,” explains how to encrypt and decrypt information. It covers the basics of encryption and describes several interesting encryption techniques, such as Vigenère ciphers, block ciphers, and public key encryption. This chapter does not go into all the details of specific encryption algorithms such as DES (Data Encryption Standard) and AES (Advanced Encryption Standard), because they are more appropriate for a book on encryption.

Chapter 17, “Complexity Theory,” explains two of the most important classes of problems in computer science: P (problems that can be solved in deterministic polynomial time) and NP (problems that can be solved in nondeterministic polynomial time). This chapter describes these classes, ways to prove that a problem is in one or the other, and the most profound question in computer science: Is P equal to NP?

Chapter 18, “Distributed Algorithms,” explains algorithms that run on multiple processors. Almost all modern computers contain multiple processors, and computers in the future will contain even more, so these algorithms are essential for getting the most out of a computer's latent power.

Chapter 19, “Interview Puzzles,” describes tips and techniques you can use to attack puzzles and challenges that you may encounter during a programming interview. It also includes a list of some websites that contain large lists of puzzles that you can use for practice.

Appendix A, “Summary of Algorithmic Concepts,” summarizes the ideas and strategies used by the algorithms described in this book. Using these, you can build solutions to other problems that are not specifically covered by the algorithms described here.

Appendix B, “Solutions to Exercises,” contains the solutions to the exercises at the end of each chapter.

The Glossary defines important algorithmic concepts that are used in this book. You may want to review the Glossary before going on programming interviews.

What You Need to Use This Book

To read this book and understand the algorithms, you don't need any special equipment. If you really want to master the material, however, you should implement as many algorithms as possible in an actual programming language. It doesn't matter which language. Working through the details of implementing the algorithms in any language will help you better understand the algorithms' details and any special treatment required by the language.

Of course, if you plan to implement the algorithms in a programming language, you need a computer and whatever development environment is appropriate.

The book's websites contain sample implementations written in C# with Visual Studio 2012 that you can download and examine. If you want to run those, you need to install C# 2012 on a computer that can run Visual Studio reasonably well.

Running any version of Visual Studio requires that you have a reasonably fast, modern computer with a large hard disk and lots of memory. For example, I'm fairly happy running my Intel Core 2 system at 1.83 GHz with 2 GB of memory and a spacious 500 GB hard drive. That's a lot more disk space than I need, but disk space is relatively cheap, so why not buy a lot?

You can run Visual Studio on much less powerful systems, but using an underpowered computer can be extremely slow and frustrating. Visual Studio has a big memory footprint, so if you're having performance problems, installing more memory may help.

The programs will load and execute with C# Express Edition, so there's no need to install a more expensive version of C#. You can get more information on C# Express Edition and download it at http://www.microsoft.com/visualstudio/eng/downloads#d-express-windows-desktop.

Conventions

To help you get the most from the text and keep track of what's happening, I've used several conventions throughout the book.

As for styles in the text:

• New terms and important words are italicized when they are introduced. You also can find many of them in the Glossary.
• Keyboard strokes look like this: Ctrl+A. This one means to hold down the Ctrl key and then press the A key.
• URLs, code, and email addresses within the text are shown in monofont type, as in http://www.CSharpHelper.com, x = 10, and [email protected].

We present code in one of two ways:

Email Me

If you have questions, comments, or suggestions, please feel free to email me at [email protected]. I can't promise to solve all your algorithmic problems, but I do promise to try to point you in the right direction.