Algorithms Analysis And Design Lecture 1 PDF

Faculty of Computers and Information Technology CS341 ALGORITHMS ANALYSIS AND DESIGN Lecture 1 Dr. Ahmed Hamza Solving Problems (1) When faced with a problem: 1. First clearly define the problem 2. Think of possible solutions 3. Select the one...

Faculty of Computers and Information Technology CS341 ALGORITHMS ANALYSIS AND DESIGN Lecture 1 Dr. Ahmed Hamza Solving Problems (1) When faced with a problem: 1. First clearly define the problem 2. Think of possible solutions 3. Select the one that seems the best under the prevailing circumstances 4. And then apply that solution 5. If the solution works as desired, fine; else go back to step 2 2 Solving Problems (2) It is quite common to first solve a problem for a particular case Then for another And, possibly another And watch for patterns and trends that emerge And to use the knowledge from these patterns and trends in coming up with a general solution And this general solution is called ……………. “Algorithm” 3 Algorithm Definition An algorithm is a step-by-step procedure for solving a particular problem in a finite amount of time. More generally, an algorithm is any well defined computational procedure that takes collection of elements as input and produces a collection of elements as output. Input ALGORITHM Some mysterious Output X processing F: X→Y Y = F(X) 4 Algorithm -- Examples Repairing a lamp A cooking recipe Calling a friend on the phone The rules of how to play a game Directions for driving from A to B A car repair manual Human Brain Project Internet & Communication Links (Graph) Matrix Multiplication 5 Why Study Algorithms? (1) 6 Why Study Algorithms? (2) For real-time problems, we would like to prove that an algorithm terminates in a given time. Algorithm 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 7 develop a ”perfect” solution: verification Why Study Algorithms? (3) 8 Why Study Algorithms? (4) 9 Algorithm vs. Program A computer program is an instance, or concrete representation, for an algorithm in some programming language Set of instructions which the computer follows to solve a problem Problem Algorithm: A sequence of instructions describing how to do a task 10 High Level Language Program  One Problem, Many Algorithms (1) Problem The statement of the problem specifies, in general terms, the desired input/output relationship. Binary relation from problem inputs to correct outputs. Usually don’t specify every correct output for all inputs (too many!). Provide a verifiable property that correct outputs must satisfy. Not general: Small input instance, i.e., Is there a pair of students with same birthday in this room? General: Arbitrarily large inputs, i.e., Given any set of n students, is there a pair of students with same birthday? If birthday is just one of 365, for n > 365, answer always true by pigeon-hole. Assume resolution of possible birthdays exceeds n (include year, 11 time, etc.)  One Problem, Many Algorithms (2) Algorithm The algorithm describes a specific computational procedure for achieving input/output relationship. Procedure mapping each input to a single output (deterministic). Solves a problem if it returns a correct output for every input. Problem Example Sorting a sequence of numbers into non-decreasing order. Solution Algorithms Various algorithms e.g. merge sort, quick sort, heap sorts etc. 12 Problem Instances An input sequence is called an instance of a Problem A problem has many particular instances An algorithm must work correctly on all instances of the problem it claims to solve Many interesting problems have infinitely many instances – Since computers are finite, we usually need to limit the number and/or size of possible instances in this case – This restriction doesn’t prevent us from doing analysis in the abstract 13  Problem-Algorithm Example Problem: Given the students in your class, return either the names of two students who share the same birthday and year, or state that no such pair exists. Algorithm: Solve birthday matching 1. Maintain a record of names and birthdays (initially empty). 2. – Interview each student in some order. I. If birthday exists in record, return found pair! II. Else add name and birthday to record. 3. – Return None if last student interviewed without success. The same algorithm can search for a birthday-matching pair in any set of students. But how can we determine whether the 14 algorithm is correct and efficient? Properties of Algorithms It must be composed of an ordered sequence of precise steps. It must have finite number of well-defined instructions /steps. The execution sequence of instructions should not be ambiguous. It must be correct. It must terminate. 15 Syntax & Semantics An algorithm is “correct” if its: WARNINGS: Semantics are correct Syntax is correct 1. An algorithm can be syntactically correct, yet semantically incorrect – Semantics: dangerous situation! The concept embedded in an algorithm (the soul!) 2. Syntactic correctness is easier to check as compared to semantic Syntax: correctness The actual representation of an algorithm (the body!) 16 Algorithm Summary 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 17 for every input it halts with correct output The End Questions? 18