Lesson 1: Introduction 1.1. Introduction Algorithmics is a branch of computer science that deals with the design and analysis of algorithms and data structures and constitutes the scientific foundation for reasoning about resources used in computing such as time and space. Its covers both the design and analysis of efficient algorithms solving concrete problems, and also with identifying common patterns of problems and associated algorithmic paradigms that can lead to efficient solutions for classes of problems. An algorithm is a finite sequence of instructions or steps for solving a problem. An algorithm must satisfy the following properties: a)Input: An algorithm requires finite number of inputs. b) Output: An algorithm must produce at least one output. c)Uniqueness: Each instruction/step must be clear and unambiguous. d) Finiteness: An algorithm must terminate after a finite number of steps. e) Effectiveness: The steps must be doable. 1.2. Lesson outline This lesson is organized as follows: 1.1. Introduction 1.2. Lesson outline 1.3. Lesson objectives 1.4. Designing algorithms 1.5. Flowchart 1.6. Pseudo code 1.7. Analysis of algorithms 1.8. Asymptotic notations 1.9. Growth rates 1.10.Working with big Oh 1.11.Dominance relations 1.12.Calculating running time of a program 1.13.Types of algorithms 1.14.Revision questions 1.15.Summary 1.16.Suggested reading 1.3.Lesson objectives: By the end of this topic, the students will be able to: i). Understand the definition and properties of an algorithm. ii). Compare and contrast different tools for developing an algorithms iii). Use pseudo code and/or flowchart to develop an algorithm iv). Use asymptotic notations such as big oh. v). Understand the time and space complexity of an algorithm vi). Classify algorithms based on design techniques 1.4.Designing an algorithm The same algorithm may be used in different programs. The same algorithm can be expressed in different languages, because an algorithm is abstracted from implementation details. How to design an algorithm a) Define the problem to solve. b) Specify the inputs c) Specify the outputs. d) Describe the steps needed to convert or manipulate inputs to produce outputs (Processing). e)Test the algorithm: Choose data sets and verify the algorithm works. Tools for designing algorithms a) Flowchart b) Pseudo code c) Top down chart/Hierarchy charts d) Decision tables 1.5. Flowchart This is a schematic representation of an algorithm. It can also be defined as a step by step solution of a problem using geometric figures connected by flow lines for the purpose of designing or documenting a program. Symbol Name Use Flow line To show progress to the next step Decision Used for logic or comparison operations Process Used to show arithmetic or data manipulation operations Input/output Used to show input/output operations e.g. read or display Terminal Used to show the start or end of a task On page connector Used to connect different flows in the same page Off page connector Used to connect different flows from two pages Advantages of flowchart i). Flowcharts are a better way of communicating the logic of the system. ii). With the help of a flowchart, problem can be analyzed easily. iii). They serve as good program documentation. iv). They help in program debugging. Disadvantages of flowchart i). For a complex problem, the flowchart becomes complex and clumsy. ii). If alterations are required, the flowchart may require redrawing completely. iii). The flow chart symbols cannot be typed and so reproduction of a flowchart becomes difficult. Guidelines for drawing a flowchart i). List all necessary requirements in a logical order. ii).The flowchart must be neat, clear and easy to follow. iii).The flowchart is read from left to right and top to bottom. iv).A process symbol can have only one flow line coming out of it. v).For a decision symbol, only one flow line can enter it but multiple lines can leave it to denote possible answers. vi).Terminal symbols can only have one flow line in conjunction with them. Example: Using a flowchart design an algorithm to compare two integers and return the largest. Star t Declare x and y Enter x and y X>y? Display y Display x Sto p 1.6. Pseudo code It is a representation of an algorithm using natural language statements e.g. structured English. It describes the entire logic of the algorithm. Pseudo code cannot be compiled nor executed and does not follow any syntax rules. Guidelines for developing algorithm using pseudo code: 1. Give a valid name for the pseudo code procedure. 2. Identify the inputs, processes and outputs 3. Use natural language e.g. English. 4. Present the statements in clear details. 5. The variables must be descriptive. 6. Each activity appears in a single line 7. The steps must be numbered. 8. Use proper indentation for every statement in a block structure. 9. The selection control statements e.g. if-else, always end an if statement with an end-if. Both the if…else and end-if must be aligned vertically in the same line. 10. If there is more than one condition, use “and”. e.g. if a>0 and a<=40. 11. Use: = or ← operators for assignments. 12. Array elements can be represented by specifying the array name followed by the index in square brackets e.g. age[i]. 13. For looping or iteration control structure, use for and while which must end with end-for, and end-while respectively. Advantages of pseudo code i).Reduced complexity compared to other tools e.g. flowchart ii).Easy to read and understand than conventional programming language. iii).Easy to translate to code iv).No special symbols required v).Saves time spent during coding, testing and debugging. Disadvantages of pseudo code i).Can be ambiguous because it uses natural language. ii).Pseudo code has few rules and it is hard to standardize. iii).The pseudo code focuses on details than the bigger picture of the algorithm. Example: An algorithm to find the largest of numbers entered by user. Solution 1.start 2.declare variables a,b,c,x 3.enter value of a,b,c 4.x=a 5.if(b>x) x=b 6. if(c>x) x=c 7.End-if 8.display x 1.7. Revision questions a) Compare and contrast flowchart and pseudo code as algorithm development tools. b) Identify the flow chart symbols in each case. i). Compare x and y integer values ii). Enter value of x and y iii). Multiply value of x with 5 and subtract 4 from the product iv). Display the result of 5x-4 1.8.Summary In this lecture we have learned how to design an algorithm using a flowchart and pseudo code. The strengths and weaknesses of each tool were discussed. We also described important guidelines when drawing a flow chart and when writing a pseudo code. Finally when designing an algorithm there are three important control structures: sequence, selection and iteration structures. 1.9.Suggested reading . Data structures using C and C++, 2nd Edition by Yedidyah Langsam, Aaron J.Augenstein and Aaron M.Tenebaum: Pubslisher: Pearson. . Data structures and algorithms in c++ by Michael T.Goodrich,Robertio Tamassia and David Mount: Publisher: Wiley . Fundamentals of data structures in c++ by Ellis Horowitz,Sartaj Sahni and Dinesh Mehta: Publisher:Galgotia . Introduction to data structures and algorithms with c++ by Glenn W.Rowe . Publisher: Prentice Hall.