About this Tutorial

1 I About this Tutorial An algorithm is a sequence of steps to solve a problem. Design and Analysis of algorithm is very important for designing algorithm to solve different types of problems in the branch of computer science and information technology. This Tutorial introduces the fundamental concepts of Designing Strategies, Complexity analysis of Algorithms, followed by problems on Graph Theory and Sorting methods. This Tutorial also includes the basic concepts on Complexity theory. Audience This Tutorial has been designed for students pursuing a degree in any computer science, engineering, and/or information technology related fields. It attempts to help students to grasp the essential concepts involved in algorithm design.

2 Prerequisites The readers should have basic knowledge of programming and mathematics. The readers should know data structure very well. Moreover, it is preferred if the readers have basic understanding of Formal Language and Automata Theory. Copyright & Disclaimer Copyright 2017 by Tutorials Point (I) Pvt. Ltd. All the content and graphics published in this e-book are the property of Tutorials Point (I) Pvt. Ltd. The user of this e-book is prohibited to reuse, retain, copy, distribute or republish any contents or a part of contents of this e-book in any manner without written consent of the publisher. We strive to update the contents of our website and tutorials as timely and as precisely as possible, however, the contents may contain inaccuracies or errors.

3 Tutorials Point (I) Pvt. Ltd. provides no guarantee regarding the accuracy, timeliness or completeness of our website or its contents including this Tutorial . If you discover any errors on our website or in this Tutorial , please notify us at ii Table of Contents About this Tutorial .. i Audience .. i Prerequisites .. i Copyright & Disclaimer .. i Table of ii BASICS OF ALGORITHMS .. 1 1. DAA Introduction .. 2 2. DAA Analysis of Algorithms .. 4 3. DAA Methodology of Analysis .. 5 Asymptotic Analysis .. 5 Solving Recurrence Equations .. 5 Amortized Analysis .. 6 4. DAA Asymptotic Notations & Apriori Analysis .. 8 Asymptotic Notations.

4 8 O: Asymptotic Upper Bound .. 9 : Asymptotic Lower Bound .. 9 : Asymptotic Tight Bound .. 9 O - Notation .. 10 Notation .. 10 Apriori and Apostiari Analysis .. 11 5. DAA Space Complexities .. 12 What is Space Complexity? .. 12 Savitch s Theorem .. 13 DESIGN STRATEGIES .. 14 6. DAA Divide & Conquer .. 15 7. DAA Max-Min Problem .. 16 Na ve Method .. 16 Divide and Conquer Approach .. 16 8. DAA Merge 18 9. DAA Binary Search .. 20 10. DAA Strassen s Matrix Multiplication .. 22 Na ve Method .. 22 Strassen s Matrix Multiplication algorithm .. 22 11. DAA Greedy Method .. 24 iii 12. DAA Fractional Knapsack .. 25 Knapsack Problem .. 25 Fractional Knapsack.

5 26 13. DAA Job Sequencing with Deadline .. 29 14. DAA Optimal Merge Pattern .. 31 15. DAA Dynamic Programming .. 34 16. DAA 0-1 Knapsack .. 35 Dynamic-Programming Approach .. 36 17. DAA Longest Common Subsequence .. 38 GRAPH THEORY .. 41 18. DAA Spanning Tree .. 42 minimum Spanning Tree .. 42 Prim s algorithm .. 43 19. DAA Shortest Paths .. 45 Dijkstra s algorithm .. 45 Bellman Ford algorithm .. 47 20. DAA Multistage Graph .. 51 21. DAA Travelling Salesman Problem .. 53 22. DAA Optimal Cost Binary Search Trees .. 56 HEAP ALGORITHMS .. 59 23. DAA Binary Heap .. 60 24. DAA Insert 63 25. DAA Heapify 65 26. DAA Extract Method .. 66 SORTING METHODS.

6 68 27. DAA Bubble Sort .. 69 28. DAA Insertion Sort .. 71 29. DAA Selection Sort .. 73 30. DAA Quick Sort .. 76 iv 31. DAA Radix Sort .. 78 COMPLEXITY THEORY .. 80 32. DAA Deterministic vs. Nondeterministic Computations .. 81 Deterministic Computation and the Class P .. 81 Nondeterministic Computation and the Class NP .. 81 33. DAA Max Cliques .. 83 34. DAA Vertex Cover .. 85 35. DAA P and NP Class .. 88 36. DAA Cook s Theorem .. 90 37. DAA NP Hard & NP-Complete Classes .. 92 38. DAA Hill Climbing algorithm .. 94 Hill Climbing .. 94 Problems of Hill Climbing Technique .. 95 Complexity of Hill Climbing Technique .. 95 Applications of Hill Climbing Technique.

7 96 5 Basics of Algorithms 6 An algorithm is a set of steps of operations to solve a problem performing calculation, data processing, and automated reasoning tasks. An algorithm is an efficient method that can be expressed within finite amount of time and space. An algorithm is the best way to represent the solution of a particular problem in a very simple and efficient way. If we have an algorithm for a specific problem, then we can implement it in any programming language, meaning that the algorithm is independent from any programming languages. algorithm Design The important aspects of algorithm design include creating an efficient algorithm to solve a problem in an efficient way using minimum time and space.

8 To solve a problem, different approaches can be followed. Some of them can be efficient with respect to time consumption, whereas other approaches may be memory efficient. However, one has to keep in mind that both time consumption and memory usage cannot be optimized simultaneously. If we require an algorithm to run in lesser time, we have to invest in more memory and if we require an algorithm to run with lesser memory, we need to have more time. Problem Development Steps The following steps are involved in solving computational problems. Problem definition Development of a model Specification of an algorithm Designing an algorithm Checking the correctness of an algorithm Analysis of an algorithm Implementation of an algorithm Program testing Documentation Characteristics of Algorithms The main characteristics of algorithms are as follows: 1.

9 DAA Introduction 7 Algorithms must have a unique name Algorithms should have explicitly defined set of inputs and outputs Algorithms are well-ordered with unambiguous operations Algorithms halt in a finite amount of time. Algorithms should not run for infinity, , an algorithm must end at some point Pseudocode Pseudocode gives a high-level description of an algorithm without the ambiguity associated with plain text but also without the need to know the syntax of a particular programming language. The running time can be estimated in a more general manner by using Pseudocode to represent the algorithm as a set of fundamental operations which can then be counted.

10 Difference between algorithm and Pseudocode An algorithm is a formal definition with some specific characteristics that describes a process, which could be executed by a Turing-complete computer machine to perform a specific task. Generally, the word " algorithm " can be used to describe any high level task in computer science. On the other hand, pseudocode is an informal and (often rudimentary) human readable description of an algorithm leaving many granular details of it. Writing a pseudocode has no restriction of styles and its only objective is to describe the high level steps of algorithm in a much realistic manner in natural language. For example, following is an algorithm for Insertion Sort.