Report

FUNDAMENTALS OF ALGORITHMS MCS - 2 LECTURE # 1 PREREQUISITES • Data Structures • Discrete Mathematics COURSE RESOURCES Compulsory Reading Material • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein (3rd Edition) Recommended Reading • Fundamentals of Computer Algorithms by Eillies Horowitz & Sahni Sartaj (1990) • Fundamentals of Algorithms by Gilles Brassard & Paul Bratley (1995) • Algorithms; Fourth Edition by Robert Sedgewick & Kevin Wayne. THE ROLE OF ALGORITHMS IN COMPUTING PROBLEM SOLVING • Programming is a process of problem solving • Problem solving techniques • Analyze the problem • Outline the problem requirements • Design steps (algorithm) to solve the problem • Algorithm: • Step-by-step problem-solving process • Solution achieved in finite amount of time PROBLEM SOLVING PROCESS • Step 1 - Analyze the problem • Outline the problem and its requirements • Design steps (algorithm) to solve the problem • Step 2 - Implement the algorithm • Implement the algorithm in code • Verify that the algorithm works • Step 3 - Maintenance • Use and modify the program if the problem domain changes ANALYZE THE PROBLEM • Thoroughly understand the problem • Understand problem requirements • Does program require user interaction? • Does program manipulate data? • What is the output? • If the problem is complex, divide it into subproblems • Analyze each subproblem as above DEFINITION • In simple terms, an algorithm is a series of instructions to solve a problem (complete a task) • Problems can be in any form • Business • Allocate manpower to maximize profit • Real Life • If I go 10 steps forward, I will reach my mailbox. • I am hungry. How do I order pizza? • Explain how to tie shoelaces to a five year old child APPLICATION OF ALGORITHM IN COMP. SCIENCE AREAS • Compiler construction • Operating system • Databases • AI • Graphics • Networking ALGORITHM & PROGRAMMING • The idea behind the computer program • It is a mathematical entity of a program. • Stays the same independent of • Which kind of hardware it is running on • Which programming language it is written in • Solves a well-specified problem in a general way • Is specified by • Describing the set of instances (input) it must work on • Describing the desired properties of the output WHAT IS AN ALGORITHM? (CONT’D) • Before a computer can perform a task, it must have an algorithm that tells it what to do. • Informally: “An algorithm is a set of steps that define how a task is performed.” • Formally: “An algorithm is an ordered set of unambiguous executable steps, defining a terminating process.” • Ordered set of steps: structure! • Executable steps: doable! • Unambiguous steps: follow the directions! • Terminating: must have an end! GOOD VS. BAD ALGORITHMS • All algorithms will have input, perform a process, and produce output. A good algorithm should be: • • Simple - relative • Complete – account for all inputs & cases • Correct (Right) • should have appropriate levels of Abstraction. – grouping steps into a single module • Precise • Mnemonic - SCRAP SIMPLICITY • Simple can be defined as having no unnecessary steps and no unnecessary complexity. (You may lose points if your algorithm contains unnecessary steps) • Each step of a well developed algorithm should carry out one logical step of the process. • Avoid something like: “Take 2nd right after you exit at King Street” IT HAS LEVELS OF ABSTRACTION. • Example: Add all the scores then divide the sum by the number of students to get the average. PRECISION • Precision means that there is only one way to interpret the instruction. Unambiguous • Words like “maybe”, “sometimes” and business in a well developed algorithm. “occasionally” have no • Instead of “maybe”, we can specify the exact circumstances in which an action will be carried out. ALGORITHM AS TOOL • It can be viewed as tool for solving “Computational Problem” • The algorithm describes a specific Computational Procedure for achieving that relationship between Input and Output. • Input<32,22,45,66,12,44> sorting algorithm returns output<12,22,32,44,45,66> • Input instance (Satisfying constraints , compute solution) • Correct Algorithm provides correct Output OTHER ALGORITHM ATTRIBUTES • A good algorithm should be correct. • A good algorithm should be complete. • “To be correct, an algorithm must produce results that are correct and complete given any and all sets of appropriate data.” • And to be correct, an algorithm must proceed through to a conclusion. • Correct IMPORTANT PROPERTIES OF ALGORITHMS / (CRITERION FOR ANALYZING ALGORITHMS) • always returns the desired output for all legal instances of the problem. • Unambiguous • Precise • Efficient • Can be measured in terms of • Running Time • Memory Space • Sometimes tends to be more important PROBLEM SOLVED BY ALGORITHMS • The Human Genes Project(HGP); sorting info in database, developing tools for analyzing data).enabling Scientists to accomplish tasks efficiently. • Manipulating and managing large volume of data on internet sites with Clever algorithms. • Numerical algorithms and number theory is helping E-Commerce to ensure the privacy of personal info. • Manufacturing and commercial enterprises use algorithms. For example politician, oil company, airline. • Model of Road map(shortest path) • Mechanical designs ASSIGNMENT # 1 • Write an algorithm to call your friend. • Give a real world example that requires Sorting for its solution? • Write an algorithm for searching ‘Algorithm’s text book’ from Library? • How does one get to see the film “THREE IDIOTS” in cinema? GOOD LUCK ! ☻