Gate Data Structure & Algorithm Book

Transcript

DATA STRUCTURE & ALGORITHM www.the www .thegate gateacademy. academy.com com Syllabus DSA Programming in C; Functions, Recursion, Parameter passing, Scope, Binding; Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees, Binary search trees, Binary heaps. Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer; Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing, Sorti ng, Searching. th th th Contents DSA C  O O  N N  T T  E E  N N  T T  S S Chapters #1. Data Structure and Algorithm Analysis         #2.           1  –  5  5 5  –  10  10 10  –  14  14 14  –  17  17 18  –  23  23 24  –  27  27 28 28  –  32  32 Assymptotic Notation Algorithm Analysis  Notation of Abstract Data Types Recurrence Assignment 1 Assignment 2 Answer keys Explanations 33  –  55  55 33 34  –  36  36 36  –  40  40 40  –  41  41 41  –  45  45 45 46  –  48  48 49  –  51  51 51  –  52  52 53 53  –  55  55 Stacks Stack ADT Implementations The Stack Purmutation Running Time Analysis Binary Expression Tree Queue Different Type of Queue Implementations Assignment 1 Assignment 2 Answer keys Explanations Trees         #4. 1  –  32  32 Stacks and Queues  #3. Page No. 56  –  84  84 56 56  –  58  58 59  –  60  60 60  –  70  70 71  –  75  75 76  –  78  78 79 79 - 84 Extended Binary Tree Binary Tree Height Analysis Binary Tree Construction Using Inorder Assignment 1 Assignment 2 Answer keys Explanations + Height Balanced Trees (AVL Trees, B and B )     85  –  113  113 85  –  94  94 94  –  96  96 96  –  102  102 102  –  103  103 AVL Trees B  –  Tree  Tree Maximizing B-Tree Degree B+Tree th th th Contents      #5.                    Introduction Binary Heap Array Representation of Binary Heap MinHeap Vs MaxHeap Basic Heap Operation Building a Heap by Inserting Items One at the Time Sum of the Height of All Nodes of a Perfect Binary Tree Assignment 1 Assignment 2 Answer keys Explanations        136  –  137  137 137  –  139  139 139  –  140  140 140  –  141  141 141 141  –  142  142 143  –  144  144 145  –  146  146 147 147  –  149  149 Bubble Sort Insertion Sort Selection Sort Merge Sort Heap Sort Quick Sort Assignment 1 Assignment 2 Answer keys Explanations 150  –  170  170 150  –  151  151 151 151  –  154  154 154  –  159  159 160  –  163  163 163  –  166  166 167 167  –  170  170 Important Definitions Representation of Graphs Single Source Shortest Path Algorithm Minimum Spanning Tree Assignment 1 Assignment 2 Answer keys Explanations Dynamic Programming   114 114  –  118  118 118  –  119  119 119 119  –  121  121 121  –  125  125 125  –  126  126 127  –  129  129 130  –  131  131 132 132  –  135  135 136  –  149  149 Graph Algorithms  #8. 114  –  135  135 Sorting Algorithms  #7. 103  –  104  104 105  –  107  107 107  –  108  108 109 109  –  113  113 Maximizing B+ Tree Degree Assignment 1 Assignment 2 Answer keys Explanations Priority Queues (Heaps)  #6. DSA 171  –  194  194 171 171  –  172  172 Introduction Idea of Dynamic Programming th th th Contents      DSA 172  –  175  175 175  –  183  183 183  –  186  186 186  –  189  189 189  –  194  194 Matrix Chain Multiplication Algorithm Greedy Algorithm  NP-Completeness Other NP- Complete Problems Hashing 195  –  209  209 195  –  205  205 206 206  –  209  209 Module Test  Test Questions Answer Keys  Explanations  210 Reference Books th th th ChapterChapter-1 DSA Once an algorithm is given for a problem and decided to be correct, then an important step is to determine how much in the way of resources, such as time or space, the algorithm will be required. The analysis required to estimate use of these resources of an algorithm is generally a theoretical issue and therefore a formal framework is required. In this framework, we shall consider a normal computer as a model of computation that will have the standard repertoire of simple instructions like addition, multiplication, comparison and assignment, but unlike the case with real computer, it takes exactly one unit time unit to do anything (simple) and there are no fancy operations such as matrix inversion or sorting, that clearly cannot be done in one unit time. We also always assume infinite i nfinite memory. The asymptotic notations are used to represent the  between functions. Represent upper bound on the running time and the memory being consumed by the algorithms. O(n) essentially conveys that the growth rate of running time/memory consumption rate will not be more than “n” for all inputs of size n for a given algorithm. However, it may be less than this. More formally Big-Oh is defined as follows: The function  f  n   O g (n)   if and only if  f  n   c. g  n    for all n, n  n0   where c, n0   are positive constants. Thus, if  f  n   O g (n)   statement is said to be true then the growth rate of function g(n) is surely higher than/equal to f(n).  f  n   3n  2 3n  2  4n  for all n  2  3n  2  O  n   Here c  4,n0  2  f  n   n2  3n  5 n2  3n  5  2n2  for n  3 th th th ChapterChapter-1 DSA   n2  3n  5  O n2   Here c  2, n0  3  f  n   3.4n  n 2 3.4n  n2  5.4n   3.4n  n2  O 4n  for n  1 3n2  2n  4  O  n  Because here doesn’t exist any positive n0  and c so that Big-Oh equation gets satisfied. For the function 4n+3, 4n+3 is O  n   2   and O n3 4n+3 is also O n  2   and O n3  but the best answer for , 4n+3 is O  n   only, as Even though 4n+3 is O n O  n   shows most tighter upper bound than the other in the question.       1. If f  n   is O g  n   then a. f  n   is also O g  n  2. If f  n   is O g  n   and h  n   is O p  n   then  f  n   h  n   O max  g n  , p n     f n = n 2, h n = l o g n   n2  log n  O n2 3.     If  f  n   is O g  n   and h  n   is O p  n   then  f  n  .h  n   is O  g  n  . p  n   th th th  ChapterChapter-1    DSA   4. If  f  n   is O g  n   and  g  n   is O h  n   then  f  n   is also O h  n  5. log n k   is O  log n  6. If  f  n    is any polynomial of degree m ,   f  n  am.nm  am1nm1  ....a1n  a0 ,   O nm then  then  fn is In general one should remember order of the following functions which will help while solving the relative growth rate of more complicated functions.     , O n  ....O n  , O 2  2 O  1 , O lo logn  , O  n  , O nl n logn  , O n 3 k n All the functions are arranged in increasing order of growth rate. If an algorithm has the time complexity O 1 , then the time complexity is said to be constant, that means running time is independent of input size.  represents lower bound on the running time and the memory being consumed by the algorithms. Ωn  Ωn  essentially conveys that the growth rate of running time/memory consumption rate will not be less than “n” for all inputs of size n for a given algorithm. However, it may be greater than this. More formally Big-Omega is defined as follows:   If  f  x   and  g  x   are any two functions and  f  x   is   g  x  , If  f  x   c. g  x   for x  k  where  where c and k are any two positive constants. constants.   Thus, if  f  x   is   g  x   statement is said to be true then the growth rate of function g(x) is surely lower than/equal to f(x). f n   n   n    n for n   2n  y  2n  for n  1 2n  4  is Ω n here n here c  2, k   1 we can also say that 2n  4  n  for n  1 then c  1, k   1 th th th ChapterChapter-1    DSA  If  f  n   is O g  n  , then  g  n   is   f  n  .   3 n 2  is O n n3  is   n2   represents tightest bound on the running time and the memory being consumed by the algorithms. (n) essentially conveys that the growth rate of running time/memory consumption rate will be equal to “n” for all inputs of size n for a given algorithm. It act ually act ually conveys that both lower and upper bounds are equal. More formally is defined as follows: If  f  x   and  g  x   are two functions, and if  f  x   c. g  x  for  x  x0 , then  f  x     g  x    here c and x 0 are two positive constants. Thus, if  f  x     g  x    statement is said to be true then the growth rate of function g(x) is surely equal to f(x) and not less or not more than f(x). f(n) = n2 + n + 1; g(n) = 5n 2 + 1; h(n) = 2 logn + n2 Then, f(n) = (g(n)) because both have same degree and hence will have same growth rate. f(n) =  = (h(n)) (h(n)) statement is also true because both have same degree and hence will have same growth rates. h(n) can be simplified as follows: 2logn is n only, Let 2logn = n ---------> 1 By taking log on both sides in equation 1. logn*log e2 = logen th th th ChapterChapter-1 DSA Then, after simplifying the above equation logn = log en/ loge2 = logn. Therefore, h(n) = n + n 2.    If  f  x     g  x    then  g  x   is also   f  x   If  f  x     g  x     we can say that  f  x  is O g  x    and  f  x  is     g  x   and also gx is Ofx and gx is Ωfx An algorithm is a finite set of steps st eps or instructions to accomplish a particular task represented in a step by step procedure. Algorithm possesses the following basic properties:  An algorithm may have some input.  An algorithm should produce at least one output.  Each statement should be clear without any ambiguity.  An algorithm in contrast to a program should terminate in a finite amount of time. The following two components need to be analyzed for determining algorithm efficiency. If we have more than one algorithms for solving a problem then we really need to consider these two before utilizing one of them.  The time required for running an algorithm.  The amount of space required at run-time by an algorithm for solving a given problem. In general these measurements are expressed in terms of asymptotic notations, like Big-Oh, theta, Omega etc. th th th