Algorithms Analysis and Design Lecture 2 PDF

Faculty of Computers and Information Technology CS341 ALGORITHMS ANALYSIS AND DESIGN Lecture 2 Dr. Ahmed Hamza Recap: Algorithm Problem Statement Relationship b/w input and output Algorithm Procedure to achieve the relationship Definition...

Faculty of Computers and Information Technology CS341 ALGORITHMS ANALYSIS AND DESIGN Lecture 2 Dr. Ahmed Hamza Recap: Algorithm Problem Statement Relationship b/w input and output Algorithm Procedure to achieve the relationship Definition A sequence of steps that transform the input to output Instance The input needed to compute solution Correct Algorithm 2 for every input it halts with correct output Brief History The study of algorithms began with mathematicians and was a significant area of work in the early years. The goal of those early studies was to find a single, general algorithm that could solve all problems of a single type. Named after 9th century Persian Muslim mathematician Abu Abdullah Muhammad ibn Musa al-Khwarizmi who lived in Baghdad and worked at the Dar al-Hikma Dar al-Hikma acquired & translated books on science & philosophy, particularly those in Greek, as well as publishing original research. The word algorism originally referred only to the rules of 3 performing arithmetic using Hindu-Arabic numerals, but later evolved to include all definite procedures for solving problems. Al-Khwarizmi’s Golden Principle (1) All complex problems can be and must be solved using the following simple steps: 1. Break down the problem into small, simple sub-problems 2. Arrange the sub-problems in such an order that each of them can be solved without effecting any other 3. Solve them separately, in the correct order 4. Combine the solutions of the sub-problems to form the solution of the original problem 4 Al-Khwarizmi’s Golden Principle (2) 5 Al-Khwarizmi’s Golden Principle (3) 6 Why Algorithms are Useful? Once we find an algorithm for solving a problem, we do not need to re-discover it the next time we are faced with that problem Once an algorithm is known, the task of solving the problem reduces to following (almost blindly and without thinking) the instructions precisely All the knowledge required for solving the problem is present in the algorithm 7 Why Write an Algorithm Down? For your own use in the future, so that you don’t have spend the time for rethinking it Written form is easier to modify and improve Makes it easy when explaining the process to others 8 Why Analysis of Algorithms? For real-time problems, we would like to prove that an algorithm terminates in a given time. Algorithmics may indicate which is the best and fastest solution to a problem without having to code up and test different solutions Many problems are in a complexity class for which no practical algorithms are known better to know this before wasting a lot of time trying to develop a ”perfect” solution: verification 9 But Computers Are So Fast These Days?? Do we need to bother with algorithmics and complexity any more? computers are fast, compared to even 10 years ago... Many problems are so computationally demanding that no growth in the power of computing will help very much. Speed and efficiency are still important 10 So Algorithms Must Be Analyzed 11 Importance of Analyzing Algorithms (1) Need to recognize limitations of various algorithms for solving a problem Need to understand relationship between problem size and running time When is a running program not good enough? Need to learn how to analyze an algorithm's running time without coding it Need to learn techniques for writing more efficient code Need to recognize bottlenecks in code as well as which parts of 12 code are easiest to optimize Importance of Analyzing Algorithms (2) An array-based list retrieve operation takes at most one operation, a linked-list-based list retrieve operation at most “n” operations. But insert and delete operations are much easier on a linked-list- based list implementation. When selecting the implementation of an Abstract Data Type (ADT), we have to consider how frequently particular ADT operations occur in a given application. For small problem size, we can ignore the algorithm’s efficiency. 13 We have to weigh the trade-offs between an algorithm’s time requirement and memory requirements. What do we Analyze about Algorithms? Algorithms are analyzed to understand their behavior and to improve them if possible Correctness Does the input/output relation match algorithm requirement? Amount of Work Done Basic operations to do task Amount of Space Used Memory used Simplicity & Clarity Verification and implementation. Optimality 14 Is it impossible to do better? The End Questions? 15