CSC645 Algorithm Analysis & Design: Chapter 1 - Introduction PDF

CSC645 – ALGORITHM ANALYSIS & DESIGN CHAPTER 1 – INTRODUCTION Nur Azmina Mohamad Zamani COURSE OUTCOME  Understanding the roles of algorithms and data structures in problem solving.  Analyzing the fundamentals of algorithm efficiency. ...

CSC645 – ALGORITHM ANALYSIS & DESIGN CHAPTER 1 – INTRODUCTION Nur Azmina Mohamad Zamani COURSE OUTCOME  Understanding the roles of algorithms and data structures in problem solving.  Analyzing the fundamentals of algorithm efficiency.  Constructing analysis on efficiency for recursive and non- recursive algorithms.  Understanding the Algorithm Design Techniques (ADTs):  Brute Force  Divide-and-Conquer  Greedy Algorithm  Dynamic Programming Chapter Overview  Introduction to algorithm and data structures.  Characteristics of algorithms.  Solving fundamentals problems using pseudocode and flowchart. What is an Algorithm?  An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. Notion of Algorithm  The non-ambiguity (clear) requirement for each step of an algorithm cannot be compromised.  The range of inputs for which an algorithm works has to be specified carefully.  The same algorithm can be represented in several different ways.  The same problem can be solved using several different algorithms and with different speed. Example of Algorithm (1) ALGORITHM: Calling a friend on the telephone  Input: The telephone number of your friend.  Output: None Steps: 1. Pick up the phone and listen for a dial tone 2. Press each digit of the phone number on the phone 3. If busy, hang up phone, wait 5 minutes, jump to step 2 4. If no one answers, leave a message then hang up 5. If no answering machine, hang up and wait 2 hours, then jump to step 2 6. Talk to friend 7. Hang up phone Assumptions:  Step 1 assumes that you live alone and no one else could be on the phone.  The algorithm assumes the existence of a working phone and active service.  The algorithm assumes you are not deaf or mute.  The algorithm assumes a normal corded phone. Example of Algorithm (2) ALGORITHM: Going to a friend’s house How many possible ways? 1) By taxi  Go to the taxi stand and wait for the taxi.  Get in the taxi  Give the address to the driver. 2) By carpool  Call another friend.  Pick up the friend.  Go to the specified address. 3) By bus  Go to the bus stand and catch the bus number 123.  Get off at the bus stop near the supermarket.  Walk about 1km and the house is on the left. Algorithm Importance THEORETICAL PRACTICAL The core of computer science. A practitioner’s toolkit of known algorithm. Framework for designing and analyzing algorithms for new problems. Algorithm vs Data Structures vs Program ALGORITHM DATA STRUCTURES PROGRAM A detailed step by step method A technique of organizing and An implementation of one or for solving a problem. storing related data items for more algorithm. efficient access and modification. Represented by pseudocodes or Eg. Array List, Linked List, Represented by programming flowcharts. Stack, Queue, Tree languages. PROGRAM = Algorithm + Data Structures The way in which the data is organized will have an effect on how the algorithm performs.  Algorithm Characteristics FINITENESS DEFINITENESS Input Output Effectiveness Terminate Precise Valid input Given some Steps are after a definition valid input; sufficiently finite of each produce simple and number of step correct basic steps output Steps in Solving Computational Problems Problem definition Development of a model Specification of an Algorithm Designing an Algorithm Checking the correctness of an Algorithm Analysis of an Algorithm Implementation of an Algorithm Program testing Documentation Problem Types in Computer Science Searching Searching for an element (keyword) in an array or list. Sorting Sorting elements in an array or list following increasing or decreasing order. Graph Problem Any problem that is related to graph traversal (edges and nodes). Geometric Problem Mathematical or geometry problem such as distance. String Processing Any string manipulation. Combinatorial Related to mathematical combinatorial problem using combination or Problem permutation. Problems that involve mathematical objects of continuous nature: solving Numerical Problem equations and system equations, computing definite integrals, evaluating functions, etc. Algorithm Design Algorithm Design Specifying an Proving Algorithm Technique Algorithm Correctness A general approach to Pseudocode Prove that the algorithm solve problems A mixture of a natural yields a required result algorithmically that is language and for every legitimate input applicable to various programming language- in a finite amount of problems from different like constructs. time. areas of computing Common technique: Flowchart mathematical induction because algorithm’s A method of expressing iterations provide a an algorithm by a natural sequence of steps collection of geometric needed for such proofs. shapes containing descriptions of the algorithm’s steps. Algorithm Design Techniques (ADTs) Divide-and- Greedy Dynamic Brute Force Conquer Technique Programming Decrease- Iterative Transform- Backtracking and-Conquer Improvement and-Conquer Space and Branch and Time Bound Tradeoffs Pseudocode Example: Euclid’s Algorithm Problem: Find gcd(m,n), the greatest common divisor of two nonnegative, not both zero integers m and n Examples: gcd(60,24) = 12, gcd(60,0) = 60, gcd(0,0) = ? Euclid’s algorithm is based on repeated application of equality gcd(m,n) = gcd(n, m mod n) until the second number becomes 0, which makes the problem trivial. Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12 Pseudocode Example: Euclid’s Algorithm (cont.) Step 1 If n = 0, return m and stop; otherwise go to Step 2 Step 2 Divide m by n and assign the value fo the remainder to r Step 3 Assign the value of n to m and the value of r to n. Go to Step 1. OR while n ≠ 0 do r ← m mod n m← n n←r return m Flowchart Symbols & Meaning Flowchart Example Reference  A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 8 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved. EXERCISES