Design and Analysis of Algorithms PDF

Algorithm is a step-by-step procedure, which is well-defined. That is, we should know the defines a set of instructions to be executed in a problem domain, for which we are designing a certain order to get the desired output. Algorithms solution. are generally created indepen...

Algorithm is a step-by-step procedure, which is well-defined. That is, we should know the defines a set of instructions to be executed in a problem domain, for which we are designing a certain order to get the desired output. Algorithms solution. are generally created independent of underlying languages, i.e. an algorithm can be implemented in Example more than one programming language. Let's try to learn algorithm-writing by using an example. From the data structure point of view, following are some important categories of algorithms − Problem − Design an algorithm to add two numbers and display the result. Search − Algorithm to search an item in a data structure. Step 1 − START Sort − Algorithm to sort items in a certain order. Step 2 − declare three integers a, b & c Insert − Algorithm to insert item in a data structure. Step 3 − define values of a & b Update − Algorithm to update an existing item in a Step 4 − add values of a & b data structure. Step 5 − store output of step 4 to c Delete − Algorithm to delete an existing item from a Step 6 − print c data structure. Step 7 – STOP Characteristics of an Algorithm Algorithms tell the programmers how to code the Not all procedures can be called an algorithm. An program. Alternatively, the algorithm can be algorithm should have the following characteristics written as – – Step 1 − START ADD Unambiguous − Algorithm should be clear and Step 2 − get values of a & b unambiguous. Each of its steps (or phases), and Step 3 − c ← a + b their inputs/outputs should be clear and must lead Step 4 − display c to only one meaning. Step 5 – STOP Input − An algorithm should have 0 or more well- defined inputs. In design and analysis of algorithms, usually the Output − An algorithm should have 1 or more well- second method is used to describe an algorithm. It defined outputs, and should match the desired makes it easy for the analyst to analyze the output. algorithm ignoring all unwanted definitions. He can Finiteness − Algorithms must terminate after a observe what operations are being used and how finite number of steps. the process is flowing. Feasibility − Should be feasible with the available resources. Types of Algorithms: Independent − An algorithm should have step-by- There are several types of algorithms available. step directions, which should be independent of Some important algorithms are: any programming code. 1. Brute Force Algorithm: How to Write an Algorithm? It is the simplest approach to a problem. A brute There are no well-defined standards for writing force algorithm is the first approach that comes to algorithms. Rather, it is problem and resource finding when we see a problem. dependent. Algorithms are never written to support a particular programming code. 2. Recursive Algorithm: A recursive algorithm is based on recursion. In this As we know that all programming languages share case, a problem is broken into several sub-parts basic code constructs like loops (do, for, while), and called the same function again and again. flow-control (if-else), etc. These common constructs can be used to write an algorithm. 3. Backtracking Algorithm: The backtracking algorithm builds the solution by We write algorithms in a step-by-step manner, but searching among all possible solutions. Using this it is not always the case. Algorithm writing is a algorithm, we keep on building the solution process and is executed after the problem domain following criteria. Whenever a solution fails we trace back to the failure point build on the next Types of Algorithms: solution and continue this process till we find the solution or all possible solutions are looked after. 1. Brute Force Algorithm - Definition: A straightforward approach to 4. Searching Algorithm: solving a problem by trying all possible solutions Searching algorithms are the ones that are used for until a satisfactory one is found. searching elements or groups of elements from a - Example: Searching for an item in an unsorted particular data structure. They can be of different list by examining each element sequentially. types based on their approach or the data structure in which the element should be found. 2. Recursive Algorithm - Definition: Solves a problem by breaking it into 5. Sorting Algorithm: smaller sub-problems and applying the same Sorting is arranging a group of data in a particular algorithm to solve each sub-problem. manner according to the requirement. The - Example Calculating the factorial of a number or algorithms which help in performing this function solving the Tower of Hanoi problem. are called sorting algorithms. Generally sorting algorithms are used to sort groups of data in an 3. Backtracking Algorithm increasing or decreasing manner. - Definition Explores all possible solutions incrementally and abandons a path (backtracks) as 6. Hashing Algorithm: soon as it determines the path cannot lead to a valid Hashing algorithms work similarly to the searching solution. algorithm. But they contain an index with a key ID. - Example: Solving a maze or placing N queens on In hashing, a key is assigned to specific data. an N×N chessboard (N-Queens problem). 7. Divide and Conquer Algorithm: 4. Searching Algorithm This algorithm breaks a problem into sub- - Definition: Algorithms designed to retrieve problems, solves a single sub-problem, and merges information stored within a data structure. the solutions to get the final solution. It consists of - Example: Binary Search, Linear Search, Depth- the following three steps: First Search (DFS), Breadth-First Search (BFS). Divide 5. Sorting Algorithm Solve - Definition Rearranges elements in a specific Combine order, such as ascending or descending. 8. Greedy Algorithm: - Example: QuickSort, MergeSort, BubbleSort, and In this type of algorithm, the solution is built part HeapSort. by part. The solution for the next part is built based on the immediate benefit of the next part. The one 6. Hashing Algorithm solution that gives the most benefit will be chosen - Definition Uses a hash function to map data to a as the solution for the next part. fixed-size value (hash code), enabling efficient data retrieval. 9. Dynamic Programming Algorithm: - Example: Hash tables and dictionaries in This algorithm uses the concept of using the already programming. found solution to avoid repetitive calculation of the same part of the problem. It divides the problem 7. Divide and Conquer Algorithm into smaller overlapping subproblems and solves - Definition: Divides the main problem into them. smaller independent sub-problems, solves them recursively, and combines their solutions. 10. Randomized Algorithm: - Example: MergeSort, QuickSort, and the Fast In the randomized algorithm, we use a random Fourier Transform (FFT). number so it gives immediate benefit. The random number helps in deciding the expected outcome. 8. Greedy Algorithm - Definition: Makes the locally optimal choice at To learn more about the types of algorithms refer to each stage in hopes of finding a global optimum. the article about “Types of Algorithms“. - Example: Dijkstra's algorithm for shortest paths, Kruskal's algorithm for minimum spanning trees.  Purpose: Provides a generalized measure of 9. Dynamic Programming Algorithm algorithm performance, regardless of - Definition: Breaks down a problem into smaller implementation specifics. sub-problems, solves them once, and stores their solutions to avoid redundant calculations. 2. Posterior Analysis - Example: Fibonacci sequence calculation, Definition: Analysis performed after Knapsack problem, and Matrix Chain Multiplication. implementation of the algorithm. Key Characteristics: 10. Randomized Algorithm Algorithm is implemented in a programming - Definition Uses random numbers at least once language and executed. during the computation to make a decision. Dependent on hardware specifications and the - Example: Randomized QuickSort and Monte compiler used. Carlo algorithms. Provides actual performance data, including: Correctness: Checks if the algorithm produces Advantages of Algorithms correct output for all possible inputs. 1. Easy to understand and follow. Time Complexity: Measures the time consumed 2. Provides a step-wise representation of the during execution. solution to a problem. Space Complexity: Measures the memory required 3. Breaks the problem into smaller, manageable for execution. pieces, making it easier for programmers to convert Purpose: Gives a real-world evaluation of the into code. algorithm’s performance. Disadvantages of Algorithms 1. Writing an algorithm can be time-consuming. 2. Understanding complex logic through an algorithm can be challenging. 3. Difficult to represent branching and looping statements in algorithms effectively. How to Design an Algorithm To design an algorithm, the following prerequisites are essential: 1. Clear Problem Definition: Understand the problem that needs to be solved. 2. Constraints: Identify the constraints that must be adhered to. 3. Input: Specify the data required to solve the problem. 4. Output: Define the expected result after solving the problem. 5. Solution: Ensure the solution is achievable within the given constraints. Priori Analysis Definition: Analysis performed before implementation of the algorithm. Key Characteristics: Focuses on the theoretical steps of the algorithm. Assumes external factors like processor speed are constant and have no effect. Independent of hardware, programming language, and compiler type. Performed by the algorithm designer to estimate time and space complexity approximately.