Algorithms Design and Analysis Ch.1 PDF

Algorithms Design and Analysis Ch.1: Introduction to Algorithms  The Goals of this Course In this course we will learn: – To think algorithmically and get the spirit of how algorithms are designed. – To get to know a toolbox of classical algorithms. – The various ways of writin...

Algorithms Design and Analysis Ch.1: Introduction to Algorithms  The Goals of this Course In this course we will learn: – To think algorithmically and get the spirit of how algorithms are designed. – To get to know a toolbox of classical algorithms. – The various ways of writing an algorithm – The concept of designing an algorithm – A number of algorithm design techniques (such as divide-and-conquer). – To reason (in a precise and formal way) about the efficiency and the correctness of algorithms.  Outline  Introduction  Importance of Algorithms  Algorithm: Definition  Characteristics of an Algorithm  Ways of Writing an Algorithm  Design and Analysis vs Analysis and Design  Present and Future  Points to Remember  Key Terms  Why Study Algorithms? Reasons why one should study algorithms :  The study of algorithms helps in enhancing the thinking process. They are like brain stimulants that will give a boost to your thinking process.  The study of algorithms helps in solving many problems in Computer Science, Computational Biology and Economics.  Without the knowledge of algorithms you can become a coder but not a programmer.  Algorithm  Algorithms : refer to the steps to be carried out in order to accomplish a particular task.  A good algorithm should use the resources like the CPU time and memory judiciously ‫ بحرص‬. It should also be unambiguous and understandable.  The five most essential things are to be considered while writing an algorithm are as follows: Time taken Memory usage Input Process Output.  Characteristics of an Algorithm  An algorithm is a sequence of steps in order to carry out a particular task.  It can have zero or more inputs (pseudorandom number generator (PRNG)).  It must have at least one output.  It should be efficient both in terms of memory and time.  It should be finite(the algorithm should have countable number of steps).  Every statement should be unambiguous. An example to demonstrate the importance of algorithms  Nowadays, algorithms have become important even for biological endeavours.  Governments across the world want to make a global database of DNAs to combat the menace of terrorism. This would be possible only if sorting and searching algorithms are developed, which can extract information from billions of DNAs.  Ways of Writing an Algorithm English like Algorithm: It can be written in simple English but this methodology comes with its package. i.e. this methodology also has some demerits. Natural languages can be ambiguous and therefore lack the characteristic of being definite. Since, each step of an algorithm should be clear and should not have more than one meaning, English language like algorithms are not considered good for most of the tasks.  Ways of Writing an Algorithm  However, Algorithm 1.1, in spite of being simple, is not commonly used.  Ways of Writing an Algorithm Flowchart: Flowcharts pictorially depict a process. They are easy to understand and are commonly used in case of simple problems. Flowchart of linear search Ways of Writing an Algorithm  Ways of Writing an Algorithm Pseudo Code : The pseudo code has an advantage of being easily converted into any programming language. This way of writing algorithm is most acceptable and most widely used. In order to be able to write a pseudo code, one must be familiar with the conventions of writing it.  Ways of Writing an Algorithm 5. a>b 6. a= b 8. a