Algorithms Analysis PDF

Algorithms analysis ​ determination of the amount of time and space resources required ​ important part of computational complexity theory Importance of Algorithm Analysis ​ predict the behavior of an algorithm without implementing ​ much more convenient to have simple measures ​ impo...

Algorithms analysis ​ determination of the amount of time and space resources required ​ important part of computational complexity theory Importance of Algorithm Analysis ​ predict the behavior of an algorithm without implementing ​ much more convenient to have simple measures ​ impossible to predict the exact behavior ​ analysis is thus only an approximation ​ can compare them to determine the best one for our purpose Asymptotic Analysis ​ defined as the big idea that handles the issues ​ evaluate the performance of an algorithm ​ don’t measure the actual running time ​ calculate, how the time (or space) taken by an algorithm Why we measure performance ​ we can have all the above things only if we have performance Studying the efficiency of algorithm ​ implement it and experiment by running the program on various test inputs Challenges of Experimental Analysis ​ difficult to directly compare unless the experiments are performed ​ can be done only on a limited set of test inputs Advantages ​ Provides a high-level understanding ​ useful tool for comparing the efficiency of different algorithms ​ helps in predicting how an algorithm will perform on larger input sizes ​ easy to perform Disadvantages ​ Does not provide an accurate running time ​ assumes that the input size is the only factor that affects an algorithm’s performance ​ sometimes be misleading ​ not always straightforward Asymptotic notation ​ describe the running time or space complexity ​ commonly used in complexity analysis AN: Big-O Notation ​ worst-case time complexity ​ determines the set of functions grows slower than or same rate AN: Omega Notation ​ best case of an algorithm’s time complexity ​ defines whether the set of functions will grow faster ​ explains the minimum amount of time AN: Theta Notation  ​ average case of an algorithm’s time complexity ​ defines when the set of functions lies in both O(expression) and Omega(expression), then Theta notation is used Worst-Case Analysis ​ Mostly-Used ​ which algorithm takes a long time or maximum time. ​ calculate the upper bound Best-Case Analysis ​ Rarely used ​ takes less time or minimum time. ​ calculate the lower bound Average-Case Analysis ​ Rarely used ​ all random inputs and calculate the computation time for all inputs. ​ Sum all the calculated values and divide the sum by the total number of inputs. Dynamic Programming ​ computer programming technique where an algorithmic problem is first broken down into subproblems, the results are saved, and then the sub-problems are optimized to find the overall solution ​ finding the maximum and minimum range ​ Richard Bellman 1950s - came up with the idea for dynamic programming, method of mathematical optimization as well as a methodology for computer programming Characteristics of DP ​ most powerful techniques for solving a certain class of problems ​ elegant way to formulate the approach ​ if the given problem can be broken up into smaller sub-problems ​ can be constructed from the solutions to the subproblems. ​ can be implemented using a recursive algorithm Top-Down (Memoization) ​ Break down the given problem in order to begin solving it ​ Memorandum - memo (to remember), to transform the results of a function into something to remember ​ used to speed up computer programs by eliminating the repetitive computation of results ​ specific form of caching that is used in dynamic programming ​ 1D Memoization: only one argument whose value was not constant ​ 2D Memoization: only two arguments whose value was not constant ​ 3D Memoization: only three arguments whose values were not constant Bottom-Up (Tabulation) ​ Analyze the problem and see in what order the subproblems are solved, and work your way up from the trivial subproblem to the given problem ​ bottom-up approach where we store the results of the subproblems in a table ​ we can define the problem as a sequence of subproblems and the subproblems do not overlap. ​ Tabulation: I will study the theory of DP, then I will practice some problems on classic DP and hence I will master DP.  ​ Memoization: To Master DP, I would have to practice Dynamic problems – Firstly, I would have to study some theories of DP Overlapping Subproblems ​ solutions to the same subproblems are needed repetitively for solving the actual problem. Optimal Substructure Property ​ can be obtained by using optimal solutions of its subproblems Steps to Solve a DP problem 1. Identify if it is a Dynamic programming problem. 2. Decide a state expression with the least parameters. 3. Formulate state and transition relationships. 4. Do tabulation (or memorization) State - collection of characteristics that can be used to specifically describe a given position or standing in a given challenge Real-World Application of DP ​ Google Maps - identify the shortest path ​ Search engines - degree of similarity ​ Plagiarism software - detection of the level similarity ​ Networking - Transfer of data ​ Spell checkers - edit distance algorithm Applications of DSA ​ Online Shopping and Finance - binary search help online stores ​ Social Media - Hashing algorithms ​ Web Browsing - complex algorithms to crawl and index the web ​ Traffic Routing - algorithms to find the fastest route ​ Streaming Services - algorithms suggest content you're likely to enjoy ​ Delivery Services - utilize algorithms to optimize delivery routes ​ Databases - trees and hash tables enable efficient storage and retrieval of information ​ Compression Algorithms - Huffman coding help compress files and images ​ File Systems - data structures to organize and manage files ​ Image Recognition - n large datasets of images can identify objects and faces  ​ Natural Language Processing - Chatbots and virtual assistants rely on algorithms to understand and respond to your questions ​ Predictive Analytics - analyze vast amounts of data to predict future trends or events case study ​ detailed study of a specific subject ​ Commonly used in social, educational, clinical, and business research. ​ qualitative methods, but quantitative methods ​ good for describing, comparing, evaluating and understanding Importance of Case Studies in DSA ​ Bridging the Gap between Theory and Practice ​ Deepening Comprehension ​ Problem-Solving Skills Development ​ Creativity and Innovation ​ Motivation and Confidence ​ Communication and Collaboration