Design and Analysis of Algorithms (Chopra, RajivRaheja, Shipra) (z-library.sk, 1lib.sk, z-lib.sk)

This page intentionally left blank

Copyright © 2020, New Age International (P) Ltd., Publishers Published by New Age International (P) Ltd., Publishers All rights reserved. No part of this ebook may be reproduced in any form, by photostat, microfilm, xerography, or any other means, or incorporated into any information by retrieval system, electronic or mechanical, without the written permission of the publisher. All inquiries should be emailed to rights@newagepublishers.com This ebook has been given to EBSCO for hosting on non-exclusive basis. ISBN: 978-81-224-5709-4 PUBLISHING GLOBALLY NEW AGE INTERNATIONAL (P) LIMITED, PUBLISHERS 7/30A, Daryaganj, New Delhi - 110002 Visit us at www.newagepublishers.com

Preface “Computing is an art form. Some programs are elegant, some are exquisite, some are sparkling. My claim is it is possible to write grand programs, noble programs, truly magnificent programs.” —Donald E. Knuth We believe that a course on Design and Analysis of Algorithms (DAA) should focus on imparting to students the knowledge and skills that are needed to successfully develop and execute an algorithm that is efficient in terms of its space and memory requirements. It is worth pointing out that according to Niklaus Wirth, DATA STRUCTURES + ALGORITHMS = PROGRAMS If data structures form a back bone of a program then algorithm answers to ‘how’ part of the program. Thus, an efficient design of algorithms is a must for a better program. Hence, this book. Recently, AICTE New Delhi revised the syllabus of B. Tech. at all India level. Keeping this in mind, we decided to write a book on this core subject of “Design and Analysis of Algorithms” for the students of B. Tech. (CSE/IT/ECE/EEE), MCA, BCA, B. Sc. and M. Sc. Computer Science courses of All Indian Universities. We believe in writing of the book that can be easily grasped by a student and used by the professors. We believe that hard work is the only investment that never fails. By reading this book, a student will think as if a teacher is sitting behind him and teaching him. This textbook on Design and Analysis of Algorithms (DAA) essentially embodies the art and science of algorithm development. It aids the learner to develop a computer algorithm rather than learning only the semantics and syntax of programming languages. The theory gices content that is learner-centric. The depth of this book focusses on the kinds of problems that the students stumble across. This book illustrates in a practical way a variety of methods, from simple to complex, to help you analyse data algorithms. This book has been designed to be very example-based and practical. We strongly believe that the student learns best by working through examples. This book has two new approaches: - • Large conceptual development to give students an understanding of algorithms development. So, students get more intuition and understand the concepts and applications. • Emphasis on time and space complexities. The biggest forte of this book is inclusion of several examples and practicals of laboratory. This book has 11 chapters. A small walkthrough is given.

Chapter -1 focusses on the properties of an algorithm, its space and time complexities. It also performs mathematical analysis of different types of algorithms. It also discusses about different sorting applications and analyses them. Chapter-2 shreds the light on the core technique of algorithm development i.e. divide-and- conquer. It also lists the applications of this technique. Several examples are solved in order to explain this technique of algorithm development. Chapter-3 explains another very popular algorithm development technique named as Greedy Method. Using this technique, various problems like job sequencing, activity selection, optimal tape storages, Knapsack problem, single source shortest path problem and minimum spanning trees problem have been discussed and solved. Chapter-4 stresses on yet another algorithm development technique coined as Dynamic Programming. It has a stepwise approach of dynamic programming. Problems like 0/1 Knapsack problem, all pair shortest path, matrix chain multiplication, longest common subsequence, optimal binary search trees problem and binomial coefficient computations are also solved using this dynamic programming approach. Chapter-5 includes the topics related to backtracking approach. Several problems like n-queen’s problem, sum of subset problem, graph colouring and Hamiltonian cycle has been dealt with. Chapter-6 emphasizes on the most useful Branch and Bound technique. It solves Travelling Salesman Problem (TSP) and Knapsack problem using this method. Chapter-7 includes all the topics of pattern matching on strings like Rabin-Karp method, finite automate method, Boyer-Moore pattern matching algorithm and Knuth-Morris-Pratt pattern matching algorithm. Chapter-8 provides a full knowledge on very popular data structure—trees. It classifies, traverses and searches a tree using the tree traversal algorithms like LNR, NLR and LRN. Also, it throws light on binary search trees, AVL trees, 2-3 trees as well as on 2-3-4 trees. It also gives Kruskal’s and Prim’s algorithm on trees. Topological sorting and network flow algorithms also form the part of this chapter. Chapter-9 throws light on another data structure—graphs. It discusses about the basic terminology related to graphs, it’s representation in memory and graph traversals in a systematic and organized way. Chapter-10 covers the most difficult part of algorithms i.e. NP-Completeness. It classifies the class of problems, non-deterministic algorithm for 0/1 Knapsack problem. Also, it discusses properties of NP-Complete and NP-Hard problems and proves them. Case studies like Vertex– Cover problem and Clique problems are also discussed in this chapter. Chapter-11 shreds the light on the advanced selected topics of algorithms like approximation algorithms, algorithm simplification and transformation, Cooley/Turkey Algorithm, Randomized algorithms maximum flow problem as well as on parallel algorithms. Last but not the least, it is hoped that this book that covers the new syllabus prescribed by AICTE for technical courses all over India, will prove to be beneficial for both students as well as the professors alike. Dr. Rajiv Chopra Shipra Raheja vi PREFACE

Acknowledgements No one walks alone and when one is walking on the journey of life just where you start to thank those that joined you, walked beside you and helped you along the way. Over the years, those that we have met and worked with have continuously urged us to write a book, to put our thoughts down on paper and to share our insights together with the secrets to our persistent, encouraging approach to life. So, we would like to express our appreciation of those persons who encouraged, helped and provoked us to write this book. First of all, we would like to thank GOD who showered his blessings to write such a manuscript on design and analysis of algorithms. We would like to thank the Director (Dr. Rominder Kaur), the Manager (S. Harjit Singh) and the Chairman (S. Avtar Singh Hit) of our college Guru Tegh Bahadur Institute of Technology (GTBIT) for their constant support and motivation. Also we would like to thank the entire staff of GIBIT. We would like to thank, Mr. Saumya Gupta, Managing Director of M/s New Age International Publishers, Delhi, and his entire team who despite then busy schedule got the book printed in a nice format. Thanks, are also due for Mr. Vipin Nautiyal. Shipra Raheja would like to thank, her parents, her husband, Mr. Akhil Raheja and her tiny- tot-Dhreya who has to be given chocolates in turn. Last but not the least, this book would not have been possible without all love and untiring support of Dr. J.R. Chopra and Mrs. Sushma Chopra of Dr. Rajiv Chopra along with his spouse Shakti Chopra and his twin babies—Arjeesh Chopra and Arshitha Chopra, who cooperated for this project. Dr. Rajiv Chopra Associate Professor (CSE Dept.) Guru Tegh Bahadur Institute of Technology (GTBIT) (Aff. to GGSIPU Delhi) Shipra Raheja Assistant Professor (IT Dept.) Guru Tegh Bahadur Institute of Technology (GTBIT) (Aff. to GGSIPU Delhi)

AICTE New Syllabus PCC-CS-404 Design and Analysis of Algorithms 3L:0T:4P 5 Credits Pre-requisites. ESC 201 Objectives of the course • Analyze the asymptotic performance of algorithms. • Write rigorous correctness proofs for algorithms. • Demonstrate a familiarity with major algorithms and data structures. • Apply important algorithmic design paradigms and methods of analysis. • Synthesize efficient algorithms in common engineering design situations. Detailed Contents: Module 1: Introduction: Characteristics of algorithm, Analysis of algorithm: Asymptotic analysis of complexity bounds–best, average and worst-case behaviour; Performance measurements of Algorithm, Time and space trade-offs, Analysis of recursive algorithms through recurrence relations: Substitution method, Recursion tree method and Masters’ theorem. Module 2: Fundamental Algorithmic Strategies: Brute-Force, Greedy, Dynamic Programming, Branch-and-Bound and Backtracking methodologies for the design of algorithms; Illustrations of these techniques for Problem-Solving, Bin Packing, Knap Sack TSP, Heuristics–characteristics and their application domains. Module 3: Graph and Tree Algorithms: Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS); Shortest path algorithms, Transitive closure, Minimum Spanning Tree, Topological sorting, Network Flow Algorithm. Module 4: Tractable and Intractable Problems: Computability of Algorithms, Computability classes—P, NP, NP-complete and NP-hard. Cook’s theorem, Standard NP-complete problems and Reduction techniques. Module 5: Advanced Topics: Approximation algorithms, Randomized algorithms, Class of problems beyond NP-P space.

Contents Preface v Acknowledgements vii AICTE New Syllabus viii MODULE–1 1. Introduction to Algorithms 1 1.0 Introduction 1 1.1 Characteristics of Algorithm 9 1.2 Analysis of Algorithms 10 1.2.1 Space Complexity 13 1.2.2 Time Complexity 15 1.2.3 Measuring an Input Size 15 1.2.4 Measuring the Running Time 15 1.3 Growth of Functions 17 1.4 Asymptotic Analysis of Complexity Bounds 19 1.4.1 Big Oh Notation (Asymptotic Upper Bound) 19 1.4.2 Omega Notation (Asymptotic Lower Bound) 26 1.4.3  Notation (Tightly Bound) 31 1.4.4 Properties of Order of Growth 40 1.4.5 Little Oh Notation (Loose Upper Bound) 41 1.4.6 Little Omega Notation (Loose Lower Bound) 43 1.5 Best Case, Worst Case and Average Case Behavior (Performance Measurements) 46 1.5.1 Amortized Analysis 48 1.5.2 Importance of Average Case Analysis 48 1.6 Analysis of Recursive Algorithms 49 1.6.1 General Plan for Analyzing Efficiency of Recursive Algorithms 49 1.6.2 Examples 49 1.7 Formulas for Efficiency Analysis 54 1.8 Analysis through Recurrence Relations, Substitution, Recursive Tree Method and Master’s Theorem 54 1.8.1 Solving Recurrence Equations 55 1.8.1.1 Substitution Method 56 1.8.1.2 Tree Method (Recursive) 63 1.8.1.3 Master’s Method (With Proofs) 67 1.9 Data Structures for Disjoint Sets, Medians and Order Statistics 74

1.10 Sorting—Analysis (Time and Space) 76 1.10.1 Shell Sort 77 1.10.2 Quick Sort and Randomized Quick Sort 82 1.10.3 Merge Sort 95 1.10.4 Heap Sort-properties, Heap Property and its Building 101 1.10.5 Method of Heap Sort 117 1.11 Comparisons of Sorting Algorithms 126 1.12 Sorting in Linear Time 126 1.12.1 Comparison Sort using Decision Trees 126 1.12.2 Decision Trees for Sorting Algorithms 129 1.12.3 Counting Sort 131 1.12.4 Radix Sort 136 1.12.5 Bucket Sort 138 1.13 Useful Proofs 140 1.14 Strassen’s Algorithm for Matrix Multiplication 141 1.15 Hashing and its Resolution 145 Summary 157 Multiple Choice Questions 157 Conceptual Short Questions with Solutions 158 Exercise Questions 166 MODULE–2 2. Divide-and-Conquer 172 2.0 Introduction 172 2.1 Brute Force 172 2.2 Efficiency Analysis of Divide-and-Conquer 175 2.3 Applications of Divide and Conquer 176 2.4 Sorting 176 2.5 Matrix Multiplication–Algorithm and Analysis 176 2.6 Convex Hull 180 2.7 Binary Search 181 Summary 189 Multiple Choice Questions 189 Conceptual Short Questions with Answers 190 Exercise Questions 194 3. Greedy Algorithms 195 3.0 Introduction 195 3.1 General Method (Algorithm) and Applications of Greedy Method 195 3.2 Job Sequencing with Deadlines 196 3.3 Activity Selection Problem 198 3.4 Optimal Storage on Tapes 200 3.5 Knapsack Problem and Knapsack 0/1 Problem— Algorithm and Analysis 201 3.5.1 Huffman’s Code 207 3.5.2 Task Scheduling Problem–A Multi-processor Case 210 3.6 Single Source Shortest Path Algorithm 212 3.6.1 Bellman Ford Algorithm 213 3.6.2 Djikstra’s Algorithm 215 3.7 Minimum Spanning Trees 223 3.7.1 Kruskal’s Algorithm 226 x CONTENTS

3.7.2 Prim’s Algorithm 230 3.7.3 Proof of Uniqueness 235 3.8 Bin Packing Problem 236 3.9 Heuristics–Characteristics and their Application Domains 240 Summary 241 Multiple Choice Questions 241 Conceptual Short Questions with Solutions 242 Exercise Questions 246 4. Dynamic Programming 249 4.0 Introduction 249 4.1 Differences Between Divide-and-Conquer and Dynamic Programming 249 4.2 Differences Between Greedy Algorithm and Dynamic Programming 250 4.3 Steps of Dynamic Programming 251 4.4 Principle of Optimality 251 4.5 Applications of Dynamic Programming 251 4.5.1 0/1 Knapsack Problem 252 4.5.2 All Pair Shortest Path-Floyd-Warshall Algorithm 257 4.5.3 Matrix Multiplications 263 4.5.4 Longest Common Subsequence (LCS) 272 4.5.5 Optimal Binary Search Tree Problem 276 4.5.6 Binomial Coefficient Computations through Dynamic Programming 287 Summary 290 Multiple Choice Questions 290 Conceptual Short Questions with Solutions 291 Exercise Questions 295 5. Backtracking 297 5.0 Introduction and General Method in Backtracking 297 5.1 Some Terminologies used in Backtracking and its Algorithms 298 5.2 Applications of Backtracking 300 5.3 N-Queens Problem 300 5.4 Sum-of-Subsets Problem 306 5.5 Graph Coloring Problem 307 5.6 Hamiltonian Cycle 308 5.7 TSP Using Backtracking 309 5.8 Knapsack Using Backtracking 311 Summary 313 Multiple Choice Questions 313 Conceptual Short Questions with Solutions 314 Exercise Questions 318 6. Branch and Bound (B & B) 319 6.0 Introduction 319 6.1 General Algorithm for Branch and Bound 319 6.2 Travelling Salesman Problem (TSP)—Row Minimization, Column Minimization, Full Reduction and Dynamic Reduction Using B & B 321 6.3 Knapsack Problem using B & B 328 Summary 331 Multiple Choice Questions 331 Conceptual Short Questions with Solutions 332 Exercise Questions 341 CONTENTS xi

7. Pattern Matching (Strings) 343 7.0 Introduction 343 7.1 String Matching 343 7.1.1 The Naive Pattern Matching Algorithm 344 7.1.2 The Rabin–Karp Algorithm 348 7.1.3 String Matching with Finite Automata 354 7.1.4 Boyer–Moore Pattern Matching Algorithm 355 7.1.5 Knuth-Morris-Pratt Pattern Matching Algorithm 359 Summary 363 Multiple Choice Questions 363 Conceptual Short Questions with Solutions 364 Exercise Questions 371 MODULE–3 8. Trees 372 8.0 Introduction 372 8.1 Terminology Related to Trees 372 8.2 Binary Tree 376 8.3 Types of Binary Trees 376 8.4 Binary Tree Representation 379 8.5 Traversal Algorithms 380 8.6 Binary Search Tree (Properties, Construction and Operations) 383 8.7 Balanced Tree 386 8.8 AVL Trees 387 8.9 B Tree 389 8.10 B+ Tree 392 8.11 2-3 Tree 393 8.12 2-3-4 Tree 394 Summary 396 Multiple Choice Questions 396 Conceptual Short Questions with Solutions 399 Exercise Questions 405 9. Graphs 407 9.0 Graphs 407 9.1 Types of Graphs 407 9.1.1 Weighted and Unweighted Graphs 408 9.1.2 Directed and Undirected Graphs 408 9.2 Basic Terminology of Graphs 409 9.3 Representations of Graph 413 9.4 Graph Traversal 415 9.5 MST (Minimum Spanning Tree) 419 9.6 Shortest Path Algorithm 422 9.7 Topological Sorting 425 9.8 Network Flow 429 Summary 430 Multiple Choice Questions 431 Conceptual Short Questions with Solutions 432 Exercise Questions 450 xii CONTENTS

MODULE–4 10. Tractable and Intractable Problems 452 10.0 Introduction 452 10.1 Computability Classes (P, NP, Complete and NP-hard) 453 10.1.1 Example of P Class and NP Class Problem 454 10.2 Non-Deterministic Algorithm (For 0/1 Knapsack Problem) 455 10.3 Proving NP Problems 456 10.4 Properties of NP-Complete and NP-hard Problems 459 10.5 Case Study on NP-Complete Problems 461 10.5.1 Cook’s Theorem and Circuit Satisfiability Problem 461 10.5.2 Clique Problem 462 10.5.3 Vertex Cover Problem 464 10.5.4 Hamiltonian Cycle Problem 466 10.5.5 Travelling Salesman Problem (TSP) 468 Summary 469 Multiple Choice Questions 469 Conceptual Short Questions with Solutions 471 Exercise Problems 472 11. Advanced Topics 473 11.0 Introduction 473 11.1 Approximation Algorithms 474 11.1.1 Approximation Algorithm for TSP 475 11.1.2 Approximation Algorithms for Knapsack Problem 477 11.1.3 Approximation Algorithms for Vertex Cover Problem 478 11.1.4 Approximation Algorithms for Set-Cover Problem 479 11.2 Algorithms Simplification and Transformation 481 11.3 Algebraic Computation—Transformation, Evaluation and Interpolation 481 11.4 FFT—Cooley/Tukey Algorithm 483 11.5 Randomized Algorithms (Randomizers) 483 11.5.1 Las Vegas Algorithm with Randomized Quick Sort 484 11.5.2 Monte Carlo Algorithm 485 11.5.3 Randomized Min Cut Algorithm 486 11.5.4 Randomized Algorithm for 2-Sat 489 11.5.5 Randomized Algorithm for n-Queens Problem 492 11.5.6 Advantages and Disadvantages 493 11.6 Maximum Flow Problem-Ford-Fulkerson Method 493 11.7 Parallel Algorithms 495 Summary 496 Multiple Choice Questions 496 Conceptual Short Questions with Solutions 497 Exercise Questions 503 Appendices 504 1. DAA Practical Lab. Programs 504 DAA Lab. Manual 592 Viva Voce (DAA Lab) 608 2. Design Analysis of Algorithm 618 3. Biblography 621 Index 623 CONTENTS xiii

This page intentionally left blank

Introduction to Algorithms CHAPTER 1 1.0 INTRODUCTION According to Niklaus Wirth, DATA STRUCTURES + ALGORITHMS = PROGRAMS So, it can be inferred that:- ALGORITHMS = PROGRAMS – DATA STRUCTURES If data structures form a back bone of a program then algorithm answers to ‘how’ part of the program. That is, how to solve a given problem? The steps that are followed to solve a particular problem form an algorithm. And its pictorial representation becomes a flowchart. The term “algorithm” was named after the 9th century (780–850) Persian Mathematician Abu Ja’far Muhammad ibn-i Musa al-Khwarizm. The term was widely used during mathematical calculations but today it is being used in the field of computer science. Please understand that algorithms are converted into the programming language instructions so as to run them on computer. Also understand that the program is a specific method while the algorithm is a general method. The algorithm remains same whether it is C/C++/JAVA or any other programming language. Computers are a dead piece of hardware if they are not loaded with software(s). It may be an application software, system software, embedded software and so on. The basic operations of a computer system form the computer’s instruction set. Now in order to solve a problem using computer, you will have to express the solution to the problem in terms of the instructions of the particular computer. So, we define a computer program as a collection of the instructions necessary to solve a specific problem. The approach or method that is used to solve the problem is known as an algorithm. For example, if you want to find the factorial of a number then the set of statements that solves the problem becomes a program. You first express the solution to the problem in terms of an algorithm and then develop a program that implements that algorithm. A program may be written in any programming language of your choice like C/C++, JAVA2, and Visual Basic 9 and so on. The concept is as follows:- MODULE–1

2 DESIGN AND ANALYSIS OF ALGORITHMS Fig. 1.1: Role of an algorithm for problem solving From figure 1.1, it is clear that the algorithms are the ideas behind programs. The algorithms should be concise and compact to facilitate verification of their correctness. Verification involves observing the performance of an algorithm with a good quality set of test cases. For example, we write an algorithm to find the maximum from a set of n positive numbers. We assume that the numbers are stored in an array, X. Algorithm to find the maximum from an array, X is as follows:- INPUT: An array, X, with n-elements. OUTPUT: Finding the largest element, MAX, from the array, X. Step-1: Set MAX=0 /* Initial value of MAX */ Step-2: for j=1 to n do Step-3: if(X[j] > MAX) then MAX = X[j] end for Step-4: Stop As a problem-solving tool, programmers usually introduce at least one intermediate step between English-like problem definition and C. This intermediate step is actually what is known as a pseudocode (pseudo=false). Please understand that pseudocode is a restatement of the problem as a list of steps, in an English-like format, describing what must be done to solve it. Using the pseudocode, a programmer then writes the actual program. In nutshell we can say that pseudocode consists of statements which are a combination of English and C, pseudocode is not quite C code but can be easily translated. It can be refined and made more precise gradually. The practicality is that the pseudocode used at one stage of the development process will often be a comment at the next stage. Characteristics of Pseudocode 1. It is an intermediary between English and the programming language code. 2. It is more structured than usual English. 3. It is free of any programming language constructs. 4. It specifies the main ideas behind a generic implementation of a data structure or an algorithm. 5. Exact definition is not important.

INTRODucTION TO ALGORITHMS 3 For example, for the above algorithm, Max, we now write its pseudocode as follows:- Initialize a variable, MAX to 0. Check through the entire set of elements If any element from the set is greater than the Max then MAX is that element. Print the MAX number. Before we discuss further, let us solve some examples. EXAMPLE 1 Write an algorithm to find the greatest of three numbers and then validate your algorithm by giving it dry runs. SOLUTION The algorithm to find the greatest of three number (a, b and c) is as follows:- Step-1: Input three numbers from the user: a, b, c. Step-2: Check, if (a > b) Step-3: do if (a > c) Step-4: then Print ‘a’ and go to step-12. Step-5: else Step-6: Print ‘c’ and go to step-12. Step-7: else Step-8: do if (b > c) Step-9: then Print ‘b’ and go to step-12. Step-10: else Step-11: Print ‘c’ and go to step-12. Step-12: Stop Let us validate this algorithm now. Dry Run-1: Input: a = 10 b = 20 c = 30 Expected Output: 30 Process: Is (a > b) ? Is (10 > 20) = false Is (b > c) ? Is (20 > 30) = false Observed Output: 30

4 DESIGN AND ANALYSIS OF ALGORITHMS Dry Run-2: Input: a = 10 b = 20 c = 30 Expected Output: 30 Process: Is (a > b) ? Is (10 > –20) = true Is (a > c) ? Is (10 > 30) = false Observed Output: 30 EXAMPLE 2 Write an algorithm to read a, b and c as the coefficients of a given quadratic equation, to find its roots and then validate your algorithm by giving it dry runs. SOLUTION The algorithm to find the roots of a given quadratic equation is as follows:- Quad_equation (a, b, c) Step-1: Input three numbers: a, b, c. Step-2: if (a= =0) Step-3: Then Print ‘Not a quadratic equation’ and go to step-11. Step-4: else Step-5: D = b2 – 4ac Step-6: check if (D > 0 or D < 0) Step-7: then ROOTS = (–b ± sqrt (d)) / 2a Step-8: and Print ‘ROOTS’ and go to step 12. Step-9: else do ROOTS = –b/2a Step-10: and Print ‘ROOTS’ and go to step 12. Step-11: Stop. Let us validate this algorithm now. Dry Run-1: Input: a = 1 b = 2 c = 3 Expected output: ROOTS = –1 ± sqrt(2) / 1 Process: Is a= =0 ? Is 1 = = 0 is false

INTRODucTION TO ALGORITHMS 5 D = b2 – 4ac = 22 – 4 × 1 × 3 = 4 – 12 = –8 D = –8 Is D > 0 or D < 0 ? D < 0 is true ROOTS = (–b ± sqrt(b2 – 4ac)) /2a Observed Output: –1 ± sqrt(2) / 1 Dry Run-2: Input: a = 4 b = 2 c = 14 Expected output: ROOTS = –1 ± sqrt(3) / 4 Process: Is a= =0 ? Is 4 = = 0 is false D = b2 – 4ac D = –12 Is D > 0 or D < 0 ? D < 0 is true ROOTS = (–b ± sqrt(b2 – 4ac)) /2a Observed Output: –1 ± sqrt(3) / 4 Dry Run-3: Input: a = 0 b = 2 c = 1 Expected output: Not a quadratic equation. Process: Is a= =0 ? Is 0 = = 0 is true Observed Output: Not a quadratic equation. Note: In all these dry runs, we observe that Observed Output = Expected Output. A flowchart is defined as a pictorial representation of an algorithm. It serves as a means of recording, analyzing and communicating problem information. Programmers often use a flowchart before writing a program. It is not always mandatory to draw a flowchart. Practically speaking, sometimes drawing of the flowchart and writing of the code in a high-level language go side by side.