ABSTRACT
CONTENTS 15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914
15.1.1 What Is an Algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914 15.1.2 Characteristics of an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914 15.1.3 Complexity of an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915 15.1.4 Asymptotic Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916
15.1.4.1 Big-O Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916 15.1.4.2 Big-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917 15.1.4.3 Big- Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918
15.1.5 Algorithm-Design Paradigms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918 15.1.5.1 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 918 15.1.5.2 Greedy Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919 15.1.5.3 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919 15.1.5.4 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919
15.2 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919 15.2.1 General Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919
15.2.1.1 Examples on the Divide-and-Conquer Strategy . . . . . . . . . . . . . . . 920 15.2.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 920
15.2.2.1 Analysis of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 920 15.2.3 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922 15.2.4 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926
15.3 Greedy Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928 15.3.1 General Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928 15.3.2 Minimum Cost Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 930 15.3.3 Fractional Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 931
15.4 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 934 15.4.1 Binomial Coefficient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935 15.4.2 All-Pair Shortest Path Using Floyd-Warshall Algorithm . . . . . . . . . . . . . . . . 937 15.4.3 0-1 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 939 15.4.4 Challenges in Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945
15.5 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945 15.5.1 General Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945
15.5.1.1 Backtracking Algorithm: Recursive . . . . . . . . . . . . . . . . . . . . . . 947 15.5.1.2 Backtracking Algorithm: Nonrecursive Algorithm Using a Stack . . 948
15.5.2 Solving 4: Queen Problem by Backtracking . . . . . . . . . . . . . . . . . . . . . . . . 948 15.6 NP-Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 951
15.6.1 P-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952 15.6.2 NP-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952
15.6.3 NP-Complete Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 953 15.7 Approximation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 953
15.7.1 Example of an Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 954 15.8 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954
15.8.1 Example: Verification of Polynomial Identities . . . . . . . . . . . . . . . . . . . . . . 955 15.8.2 Advantage of a Randomized Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 955
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956
ABSTRACT An algorithm is a sequence of unambiguous instructions or steps to solve a particular problem. It is meant for obtaining a required output for any legitimate input in a finite amount of time. Algorithms are frequently expressed in the form of a pseudocode that can be converted into a program using a programming language. Hence, the concept of an algorithm is considered distinct from that of a program. This chapter discusses the basics about an algorithm. It defines the term “algorithm” formally and lists out various characteristics of an algorithm. It discusses the complexity analysis of an algorithm. It also presents various popular algorithms design paradigms such as divide and conquer, greedy algorithm, dynamic programming, and back tracking. Each of the algorithm design paradigm is discussed with several examples to illustrate the concept. This chapter briefly throws some light on the types of computational problems by presenting a discussion on the P-problem and NP-problem. These problems are very important in theoretical computer science and constitute the bulk of our practical computational problems. They have been central to the theory of computation for many years. A deterministic algorithm always gives the correct solution and the number of computational steps executed by the algorithm is the same for different executions of the algorithm with the same input data. However, it is practically realized many a times that for a given computational problem, it may be difficult to design a deterministic algorithm with a good execution time. Also, sometimes, it is observed that a deterministic algorithm performs reasonably well for a small size of input data; however, the execution time may go very high as the number of inputs increases. Approximation algorithms and randomized algorithms are the solutions to these problems. Approximation algorithms are the types of algorithms that are used to find approximate solutions to optimization problems whereas a randomized algorithm makes use of randomness in its logical steps to achieve a better performance in the average case. At the end of the chapter, a brief introduction of approximation and randomized algorithms is presented.
