Algorithms

The following sections are included:

• Preface

• Contents

This part of the book is concerned with the study of the basic tools and prerequisites for the design and analysis of algorithms…

The following sections are included:

• Introduction

• Historical Background

• Binary Search
  • Analysis of the binary search algorithm

• Merging Two Sorted Lists

• Selection Sort

• Insertion Sort

• Bottom-Up Merge Sorting
  • Analysis of bottom-up merge sorting

• Time Complexity
  • Order of growth
  • The O-notation
  • The Ω-notation
  • The Θ-notation
  • Examples
  • Complexity classes and the o-notation

• Space Complexity

• Optimal Algorithms

• How to Estimate the Running Time of an Algorithm
  • Counting the number of iterations
  • Counting the frequency of basic operations
  • Using recurrence relations

• Worst Case and Average Case Analysis
  • Worst case analysis
  • Average case analysis

• Amortized Analysis

• Input Size and Problem Instance

• Exercises

• Bibliographic Notes

The following sections are included:

• Sets, Relations and Functions
  • Sets
  • Relations
    • Equivalence relations
  • Functions

• Proof Methods
  • Direct proof
  • Indirect proof
  • Proof by contradiction
  • Proof by counterexample
  • Mathematical induction

• Logarithms

• Floor and Ceiling Functions

• Factorial and Binomial Coefficients
  • Factorials
  • Binomial coefficients

• The Pigeonhole Principle

• Summations
  • Approximation of summations by integration

• Recurrence Relations
  • Solution of linear homogeneous recurrences
  • Solution of inhomogeneous recurrences
  • Solution of divide-and-conquer recurrences
    • Expanding the recurrence
    • Substitution
    • Change of variables

• Exercises

The following sections are included:

• Introduction

• Linked Lists
  • Stacks and queues

• Graphs
  • Representation of graphs
  • Planar graphs

• Trees

• Rooted Trees
  • Tree traversals

• Binary Trees
  • Some quantitative aspects of binary trees
  • Binary search trees

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Heaps
  • Operations on heaps
  • Creating a heap
  • Heapsort
  • Min and max heaps

• Disjoint Sets Data Structures
  • The union by rank heuristic
  • Path compression
  • The union-find algorithms
  • Analysis of the union-find algorithms

• Exercises

• Bibliographic Notes

This part of the book is concerned with a particular class of algorithms, called recursive algorithms. These algorithms turn out to be of fundamental importance and indispensible in virtually every area in the field of computer science. For many problems, the use of recursion makes it possible to solve complex problems using algorithms that are concise, easy to comprehend and efficient (from an algorithmic point of view). In its simplest form, recursion is the process of dividing the problem into one or more subproblems, which are identical in structure to the original problem and then combining the solutions to these subproblems to obtain the solution to the original problem. We identify three special cases of this general design technique: (1) Induction or tail-recursion. (2) Nonoverlapping subproblems. (3) Overlapping subproblems with redundant invocations to subproblems, allowing trading space for time. The higher numbered cases subsume the lower numbered ones. The first two cases will not require additional space for the maintenance of solutions for continued reuse. The third class, however, renders the possibility of efficient solutions for many problems that at first glance appear to be time-consuming to solve…

The following sections are included:

• Introduction

• Two Simple Examples
  • Selection sort
  • Insertion sort

• Radix Sort

• Integer Exponentiation

• Evaluating Polynomials (Horner's Rule)

• Generating Permutations
  • The first algorithm
  • The second algorithm

• Finding the Majority Element

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Binary Search

• Mergesort
  • How the algorithm works
  • Analysis of the mergesort algorithm

• The Divide and Conquer Paradigm

• Selection: Finding the Median and the kth Smallest Element
  • Analysis of the selection algorithm

• Quicksort
  • A partitioning algorithm
  • The sorting algorithm
  • Analysis of the quicksort algorithm
    • The worst case behavior
    • The average case behavior
  • Comparison of sorting algorithms

• Multiplication of Large Integers

• Matrix Multiplication
  • The traditional algorithm
  • Recursive version
  • Strassen's algorithm
  • Comparisons of the three algorithms

• The Closest Pair Problem
  • Time complexity

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• The Longest Common Subsequence Problem

• Matrix Chain Multiplication

• The Dynamic Programming Paradigm

• The All-Pairs Shortest Path Problem

• The Knapsack Problem

• Exercises

• Bibliographic Notes

When a solution to a problem is sought, perhaps the first strategy that comes to one's mind is the greedy method. If the problem involves graphs, then one might consider traversing the graph, visiting its vertices and performing some actions depending on a decision made at that point. The technique used to solve that problem is usually specific to the problem itself. A common characteristic of both greedy algorithms and graph traversal is that they are fast, as they involve making local decisions…

The following sections are included:

• Introduction

• The Shortest Path Problem
  • A linear time algorithm for dense graphs

• Minimum Cost Spanning Trees (Kruskal's Algorithm)

• Minimum Cost Spanning Trees (Prim's Algorithm)
  • A linear time algorithm for dense graphs

• File Compression

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Depth-First Search
  • Time complexity of depth-first search

• Applications of Depth-First Search
  • Graph acyclicity
  • Topological sorting
  • Finding articulation points in a graph
  • Strongly connected components

• Breadth-First Search

• Applications of Breadth-First Search

• Exercises

• Bibliographic Notes

In this part of the book, we turn our attention to the study of the computational complexity of a problem as opposed to the cost of a particular algorithm to solve that problem. We define the computational complexity of a problem to be the computational complexity of the most efficient algorithm to solve that problem…

The following sections are included:

• Introduction

• The Class P

• The Class NP

• NP-Complete Problems
  • The satisfiability problem
  • Vertex cover, independent set and clique problems
  • More NP-complete Problems

• The Class co-NP

• The Class NPI

• The Relationships Between the Four Classes

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Model of Computation: The Turing Machine

• k-tape Turing Machines and Time Complexity

• Off-Line Turing Machines and Space Complexity

• Tape Compression and Linear Speed-Up

• Relationships Between Complexity Classes
  • Space and time hierarchy theorems
  • Padding arguments

• Reductions

• Completeness
  • NLOGSPACE-complete problems
  • PSPACE-complete problems
  • P-complete problems
  • Some conclusions of completeness

• The Polynomial Time Hierarchy

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Trivial Lower Bounds

• The Decision Tree Model
  • The search problem
  • The sorting problem

• The Algebraic Decision Tree Model
  • The element uniqueness problem

• Linear Time Reductions
  • The convex hull problem
  • The closest pair problem
  • The Euclidean minimum spanning tree problem

• Exercises

• Bibliographic Notes

In the previous part of the book, we have seen that many practical problems have no efficient algorithms, and the known ones for these problems require an amount of time measured in years or centuries even for instances of moderate size…

The following sections are included:

• Introduction

• The 3-Coloring Problem

• The 8-Queens Problem

• The General Backtracking Method

• Branch and Bound

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Las Vegas and Monte Carlo Algorithms

• Randomized Quicksort

• Randomized Selection

• Testing String Equality

• Pattern Matching

• Random Sampling

• Primality Testing

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Basic Definitions

• Difference Bounds
  • Planar graph coloring
  • Hardness result: the knapsack problem

• Relative Performance Bounds
  • The bin packing problem
  • The Euclidean traveling salesman problem
  • The vertex cover problem
  • Hardness result: the traveling salesman problem

• Polynomial Approximation Schemes
  • The knapsack problem

• Fully Polynomial Approximation Schemes
  • The subset-sum problem

• Exercises

• Bibliographic Notes

In this part of the book, we study an algorithm design technique that we will refer to as iterative improvement. In its simplest form, this technique starts with a simple-minded (usually a greedy) solution and continues to improve on that solution in stages until an optimal solution is found. One more aspect of problem-specificity characterizes this technique. Some marking characteristics of the iterative improvement technique are in order. First, devicing new data structures to meet the data access requirements of the algorithm effectively, e.g. splay trees and Fibonacci heaps. Second, the introduction of innovative analysis techniques to carefully account for the true cost of the computation. This will be evident when, for example, counting the number of phases or augmentations in network flow and matching algorithms. Third, exploiting the problem specific observations to improve upon the existing solution…

The following sections are included:

• Introduction

• Preliminaries

• The Ford-Fulkerson Method

• Maximum Capacity Augmentation

• Shortest Path Augmentation

• Dinic's Algorithm

• The MPM Algorithm

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Preliminaries

• The Network Flow Method

• The Hungarian Tree Method for Bipartite Graphs

• Maximum Matching in General Graphs

• An O(n^2.5) Algorithm for Bipartite Graphs

• Exercises

• Bibliographic Notes

Computational geometry is defined as the study of problems that are inherently geometric in nature. There are several techniques to solve geometric problems, some of them we have already covered in the previous chapters. There are, however, standard techniques that are specific to solving geometric problems. It is important to have fast geometric algorithms in many fields like computer graphics, scientific visualization and graphical user interfaces. Also, speed is fundamental in real time applications in which the algorithm receives its input dynamically…

The following sections are included:

• Introduction

• Geometric Preliminaries

• Computing the Intersections of Line Segments

• The Convex Hull Problem

• Computing the Diameter of a Set of Points

• Exercises

• Bibliographic Notes

The following sections are included:

• Introduction

• Nearest-Point Voronoi Diagram
  • Delaunay triangulation
  • Construction of the Voronoi diagram

• Applications of the Voronoi Diagram
  • Computing the convex hull
  • All nearest neighbors
  • The Euclidean minimum spanning tree

• Farthest-Point Voronoi Diagram
  • Construction of the farthest-point Voronoi diagram

• Applications of the Farthest-Point Voronoi Diagram
  • All farthest neighbors
  • Smallest enclosing circle

• Exercises

• Bibliographic Notes

The following sections are included:

• Bibliography

• Index