Chapter 1 - Algorithm Analysis & Design 2021

Chapter 1 - Algorithm Analysis & Design 2021

• 1.
  CSC645 – ALGORITHMANALYSIS & DESIGN CHAPTER 1 – INTRODUCTION Nur Azmina Mohamad Zamani Edited by Nursyahidah Alias
• 2.
  COURSE OUTCOME  Understandingthe 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
• 3.
  Chapter Overview  Introductionto algorithm and data structures.  Characteristics of algorithms.  Solving fundamentals problems using pseudocode and flowchart.
• 4.
  What is anAlgorithm?  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.
• 5.
  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.
• 6.
  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.
• 7.
  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.
• 8.
  Algorithm Importance THEORETICAL PRACTICAL Thecore of computer science. A practitioner’s toolkit of known algorithm. Framework for designing and analyzing algorithms for new problems.
• 9.
  Algorithm vs DataStructures vs Program ALGORITHM DATA STRUCTURES PROGRAM A detailed step by step method for solving a problem. A technique of organizing and storing related data items for efficient access and modification. An implementation of one or more algorithm. Represented by pseudocodes or flowcharts. Eg. Array List, Linked List, Stack, Queue, Tree Represented by programming languages. PROGRAM = Algorithm + Data Structures The way in which the data is organized will have an effect on how the algorithm performs.
• 10.
  Algorithm Characteristics FINITENESS • Terminate aftera finite number of steps DEFINITENESS • Precise definition of each step Input • Valid input Output • Given some valid input; produce correct output Effectiveness • Steps are sufficiently simple and basic
• 11.
  Steps in SolvingComputational 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
• 12.
  Problem Types inComputer Science Searching for an element (keyword) in an array or list. Searching Sorting elements in an array or list following increasing or decreasing order. Sorting Any problem that is related to graph traversal (edges and nodes). Graph Problem Mathematical or geometry problem such as distance. Geometric Problem Any string manipulation. String Processing Related to mathematical combinatorial problem using combination or permutation. Combinatorial Problem Problems that involve mathematical objects of continuous nature: solving equations and system equations, computing definite integrals, evaluating functions, etc. Numerical Problem
• 13.
  Algorithm Design • Provethat the algorithm yields a required result for every legitimate input in a finite amount of time. • Common technique: mathematical induction because algorithm’s iterations provide a natural sequence of steps needed for such proofs. Proving Algorithm Correctness • Pseudocode • A mixture of a natural language and programming language- like constructs. • Flowchart • A method of expressing an algorithm by a collection of geometric shapes containing descriptions of the algorithm’s steps. Specifying an Algorithm • A general approach to solve problems algorithmically that is applicable to various problems from different areas of computing Algorithm Design Technique
• 14.
  Algorithm Design Techniques(ADTs) Brute Force Divide-and- Conquer Greedy Technique Dynamic Programming Decrease- and-Conquer Iterative Improvement Transform- and-Conquer Backtracking Space and Time Tradeoffs Branch and Bound
• 15.
  Pseudocode Example: Euclid’sAlgorithm 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
• 16.
  Pseudocode Example: Euclid’sAlgorithm (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
• 17.
  Flowchart Symbols &Meaning
• 18.
  Flowchart Example
• 19.
  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.
• 20.
  EXERCISES