Techniques for Designing and Analyzing Algorithms

Douglas R. Stinson

• Publisher: Chapman and Hall/CRC
• Year: 2021
• ISBN:
  9781000403701
• Edition: 1
• Topic: Mathematics
• Subtopic: Mathematics General
• Index: Mathematics

Techniques for Designing and Analyzing Algorithms

Design and analysis of algorithms can be a difficult subject for students due to its sometimes-abstract nature and its use of a wide variety of mathematical tools. Here the author, an experienced and successful textbook writer, makes the subject as straightforward as possible in an up-to-date textbook incorporating various new developments appropriate for an introductory course.

This text presents the main techniques of algorithm design, namely, divide-and-conquer algorithms, greedy algorithms, dynamic programming algorithms, and backtracking. Graph algorithms are studied in detail, and a careful treatment of the theory of NP-completeness is presented.

In addition, the text includes useful introductory material on mathematical background including order notation, algorithm analysis and reductions, and basic data structures. This will serve as a useful review and reference for students who have covered this material in a previous course.

Features

• 
  
  

• The first three chapters provide a mathematical review, basic algorithm analysis, and data structures

• 
  
  

• Detailed pseudocode descriptions of the algorithms along with illustrative algorithms are included

• 
  
  

• Proofs of correctness of algorithms are included when appropriate

• 
  
  

• The book presents a suitable amount of mathematical rigor

After reading and understanding the material in this book, students will be able to apply the basic design principles to various real-world problems that they may encounter in their future professional careers.

Chapter 1

Introduction and Mathematical Background

DOI: 10.1201/9780429277412-1

In this chapter, we discuss mathematical background, including terminology and basic concepts relating to algorithms, order notation (to specify the complexity of algorithms) and various relevant mathematical formulae. Finally, we provide a brief introduction to probability theory and the use of random variables. This chapter can be considered as a review or reference for readers familiar with this background material.

1.1 Algorithms and Programs

In this book, we are studying algorithms, concentrating on their design and analysis. In this section, we explain exactly what we mean by these terms, and we give some motivation for studying these aspects of computer science.

Our basic premise is that we have a problem that we wish to solve by writing a computer program. A computer program is simply a series of instructions that that will be performed by the computer, stated in a precise fashion in a particular programming language, e.g., C++. Yet the subject of this book is algorithms, which the dictionary defines as “a set of rules for solving a problem in a finite number of steps.” Expanding on this slightly, we will define an algorithm as a step-by-step p...