Chapter 1. Getting Started with Algorithms: A Modern Approach
What are algorithms and why are they important?
An algorithm is a finite, deterministic, and effective problemsolving method suitable for implementation as a computer program. Algorithms are the stuff of computer science  they are central objects of study in the field.
Algorithms are essential tools in computer programming and software development. Every nontrivial computer program contains algorithms that specify the steps to follow to solve a problem or accomplish a task. Some examples of where algorithms play a critical role include:

Scientific computing  algorithms power computational models and simulations used in fields like physics, biology, and engineering to tackle complex problems. For example, Nbody simulation algorithms predict the motions of particles under physical forces.

Artificial intelligence and machine learning  algorithms underlie the models used for tasks like computer vision, natural language processing, and predictive analytics. Deep learning algorithms have enabled breakthroughs in AI capabilities.

Optimization and operations research  algorithms are used to optimize complex systems and processes, such as airline flight scheduling, supply chain logistics, financial portfolios, and telecommunication networks. Linear programming and other optimization algorithms provide decision support.

Computer graphics and simulation  algorithms generate realistic images, animations, and interactive virtual worlds in video games and computergenerated movies. Ray tracing and physics simulation algorithms produce lifelike scenes.

Cybersecurity and cryptography  algorithms secure computer systems by encrypting sensitive data, detecting intrusions, and verifying identities. Publickey cryptography algorithms enable secure online communication and commerce.

Bioinformatics and computational biology  algorithms are used to analyze biological data like DNA sequences, predict protein structures, and model biochemical systems. Genome sequencing and alignment algorithms have revolutionized the life sciences.

Databases and information retrieval  algorithms power the storage, indexing, and querying of massive datasets. Search engines use web crawling, indexing, and ranking algorithms to provide instant access to online information.
As computing power grows and new applications emerge, the importance of algorithms will only increase. Algorithms provide the problemsolving power to tackle the hardest computational challenges and realize the potential of new computing technologies. Advances in algorithms can provide dramatic improvements in the efficiency and capabilities of computer systems.
While modern programming languages and tools hide many implementation details, a strong understanding of algorithms remains essential for writing efficient, scalable, and robust software. Programmers need to know how to select appropriate algorithms for a problem, analyze algorithmic efficiency, recognize algorithmic patterns, and adapt existing algorithms to new uses.
The study of algorithms encompasses the theoretical foundations, design techniques, and mathematical analysis of computational problemsolving methods. It is a rich intellectual field with deep connections to mathematics and many important practical applications. Every computer scientist and software engineer should have a working knowledge of the essential algorithms in use today.
Overview of the book and its approach
This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many of the most important algorithms used in computer science and software engineering, with an emphasis on practical applications and scientific performance analysis.
The book surveys fundamental algorithms for sorting, searching, graphs, strings, and other core computer science topics. It shows how to analyze algorithms to understand their efficiency, design effective algorithms using established techniques, and apply algorithms to solve realworld problems.
A distinctive feature of the book is its focus on the scientific method in the study of algorithms. The book presents each algorithm using complete implementations in Java, mathematical models for analyzing performance, and empirical studies that test the predictive power of the models on real inputs. Through this scientific approach, the book teaches how to understand the salient characteristics of an algorithm and predict its performance in practical applications.
The Java implementations covered in the book provide complete, wellengineered solutions suitable for use in real programs. However, the book's primary goal is not just to teach how to implement specific algorithms in Java, but to promote general techniques for designing and analyzing efficient algorithms in any language. The implementations serve to illustrate general algorithm design patterns and analysis methods that are applicable in many computational environments.
To keep the focus on essential concepts, the book uses a concise subset of Java and adheres to streamlined programming and analysis models. It covers the most important language mechanisms for algorithms and data abstraction, while avoiding esoteric features. The book also provides its own libraries for input/output, data generation, and mathematical functions to simplify examples.
The book is organized into six chapters that can support onesemester or twoquarter courses on algorithms. It is also suitable for selfstudy by practicing programmers or as a reference for researchers and professionals.
Chapter 1 introduces the foundations of algorithms and the scientific approach promoted by the book. It covers the Java programming model, data abstraction, basic data structures, abstract data types for collections, methods of analyzing algorithm performance, and a case study.
Chapter 2 covers sorting algorithms, including insertion sort, selection sort, shellsort, quicksort, mergesort, and heapsort. It also discusses related topics like priority queues, stability, and applications of sorting.
Chapter 3 focuses on searching algorithms and related data structures, including sequential search, binary search, binary search trees, balanced trees, and hash tables. It shows how to build efficient search structures for both sorted and unsorted data.
Chapter 4 presents fundamental graph algorithms for connectivity, directed graphs, minimum spanning trees, and shortest paths. It covers depthfirst search, breadthfirst search, topological sort, Prim's and Kruskal's algorithms, and Dijkstra's and BellmanFord algorithms.
Chapter 5 covers string processing algorithms, including string sorts, tries, substring search, regular expressions, and data compression. It demonstrates the importance of efficient algorithms on string data in modern computing applications.
Chapter 6 concludes the book with an overview of advanced algorithmic topics and their connections to other computer science fields. It discusses computational geometry, operations research, numerical methods, and intractability to motivate further study.
The extensive collection of exercises, programming problems, and experiments provided with the book enable readers to develop a deep understanding of algorithms through practice. The book's website supplies additional resources, including data files, test cases, and challenge problems.
By combining classic algorithms with scientific techniques for designing and analyzing them, this book prepares readers to confidently implement, evaluate, and deploy algorithms for a wide range of computational challenges. It equips them with the conceptual tools and practical skills to use algorithms effectively in building modern software systems.
Basic programming model and data abstraction
The book's programming model is based on the Java language, but it uses only a concise subset of Java to express algorithms clearly and succinctly. The book focuses on the language mechanisms most relevant to algorithms while avoiding obscure features.
The basic building blocks of the programming model are:

Primitive data types  the fundamental data types built into Java, including int, double, boolean, and char. These types have a fixed set of values and operations.

Statements  the commands that define a computation by creating and manipulating variables, controlling execution flow, and causing side effects. The book uses declarations, assignments, conditionals, loops, calls, and returns.

Arrays  sequences of values of the same type that allow random access by integer index. Arrays are the simplest data structures for storing and processing collections of data.

Static methods  named and parameterized computations that can be reused from multiple call sites. Static methods support modular programming by encapsulating algorithms as reusable functions.

Input/output  mechanisms for interacting with the outside world by reading input and writing output. These allow programs to communicate with the user and access data stored in files or on the web.

Data abstraction  extends encapsulation and reuse to allow us to define nonprimitive data types, thus supporting objectoriented programming. In this section, we will consider the first five of these in turn. Data abstraction is the topic of the next section.
Running a Java program involves interacting with an operating system or a program development environment. For clarity and economy, we describe such actions in terms of a virtual terminal, where we interact with programs by typing commands to the system. See the booksite for details on using a virtual terminal on your system, or for information on using one of the many more advanced program development environments that are available on modern systems.
For example, BinarySearch is two static methods, rank() and main(). The first static method, rank(), is four statements: two declarations, a loop (which is itself an assignment and two conditionals), and a return. The second, main(), is three statements: a declaration, a call, and a loop (which is itself an assignment and a conditional).
To invoke a Java program, we first compile it using the javac command, then run it using the java command. For example, to run BinarySearch, we first type the command javac BinarySearch.java (which creates a file BinarySearch.class that contains a lowerlevel version of the program in Java bytecode in the file BinarySearch.class). Then we type java BinarySearch (followed by a whitelist file name) to transfer control to the bytecode version of the program.
To develop a basis for understanding the effect of these actions, we next consider in detail primitive data types and expressions, the various kinds of Java statements, arrays, static methods, strings, and input/output.
Data Abstraction
Data abstraction extends encapsulation and reuse to allow us to define nonprimitive data types, thus supporting objectoriented programming. The basic idea is to define data types (classes) that encapsulate data values and operations on those data values. Clients can create and manipulate objects (instances of the data type) without knowing how the data is represented or how the operations are implemented.
The key components of a data type definition are:
 Instance variables  the data that each object contains
 Constructors  methods for creating objects and initializing instance variables
 Instance methods  methods that define operations on objects
 Scope  the visibility and lifetime of variables
Java provides mechanisms for precisely controlling access to instance variables and methods. The private keyword ensures that they can only be accessed from within the data type definition, not by clients.
Defining APIs, client code, and testing the implementation are essential steps in developing an abstract data type. The API serves to separate clients from implementations, enabling modular programming. Multiple implementations can be developed for the same API.
Several examples illustrate these concepts, including a data type for maintaining a counter, a data type for representing dates, and a data type for accumulating data values. Visual animations of data type operations help provide insight into their behavior.
Strings and input/output revisited from an objectoriented perspective show how multiple input streams, output streams, and drawing windows can be handled as objects within a single program.
Programming with Abstract Data Types
Abstract data types are essential for organizing and managing complex programs. They allow us to:
 Encapsulate related data and operations into modules
 Separate interface and implementation
 Develop client code and implementations independently
 Substitute improved implementations without changing client code
 Reuse code
Adhering to conventions and taking care with issues like scope, API design, testing, and naming are important for successful programming with abstract data types.
Summary

Primitive data types, expressions, statements, arrays, static methods, strings, and input/output are the basic building blocks for Java programs.

Abstract data types enable modular programming, separating clients from implementations.

Defining APIs, client code, and testing implementations are essential to programming with abstract data types.

Encapsulating data and operations in abstract data types facilitates organizing and managing complex programs.
This concludes our introduction to the fundamentals of programming in Java and abstract data types. With these conceptual tools we are ready to move on to considering fundamental algorithms and data structures.