This textbook explains the concepts and techniques required to write programs that can handle large amounts of data efficiently. Project-oriented and classroom-tested, the book presents a number of important algorithms supported by examples that bring meaning to the problems faced by computer programmers. The idea of computational complexity is also introduced, demonstrating what can and cannot be computed efficiently so that the programmer can make informed judgements about the algorithms they use. Features: includes both introductory and advanced data structures and algorithms topics, with suggested chapter sequences for those respective courses provided in the preface; provides learning goals, review questions and programming exercises in each chapter, as well as numerous illustrative examples; offers downloadable programs and supplementary files at an associated website, with instructor materials available from the author; presents a primer on Python for those from a different language background.

the size of a problem space grows, how does a program or algorithm behave? In terms of this analogy, as the number of post office boxes grows, how much longer does it take to store or retrieve a value? The RAM of a computer does not behave like a post office. The computer does not need to find the right RAM location before the it can retrieve or store a value. A much better analogy is a group of people, each person representing a memory location within the RAM of the computer. Each person is

turns. The minimax algorithm is simple. The idea is that when it is the computer’s turn it should pick the move that will be best for the computer. Each possible move is analyzed to find the value that would be best for the computer. We’ll let a 1 represent the best move for the computer. The worst move the computer could make will be represented by a −1. Move values can range between 1 and −1. When it is the computer’s turn it will pick the move that results in the maximum move value. That’s the

important concept in Computer Science because it is a very efficient method of searching for a value. To begin the chapter we’ll motivate our interest in hashing, then we’ll develop a hashing algorithm for finding values in a set. We’ll also apply hashing to the building of sets and maps. Then we’ll look at an important technique that uses hashing called memoization and we’ll apply that technique to a couple of problems. 5.1 Chapter Goals In this chapter you learn how to implement a couple of

a tree is accomplished by doing a recursive traversal of the tree. The eval methods together are the recursive function in this example. We say that the eval methods are mutually recursive since all the eval methods together form the recursive function. 6.3 Prefix and Postfix Expressions Expressions, as we normally write them, are said to be in infix form. An infix expression is an expression written with the binary operators in between their operands. Expressions can be written in other forms

different languages and each language has its own grammar. Prefix expressions make up a language. We call them the language of prefix expressions and they have their own grammar, called a context-free grammar. A context-free grammar for prefix expressions is given in Sect. 6.4.1. 6.4.1 The Prefix Expression Grammar G = (N N T P , T , P ,E) where = {E} = {identifier, number, +, ∗} is defined by the set of productions E → + E E | ∗ E E | number A grammar, G, consists of three sets: a set of