We're going to learn today some basic terminology regarding data structures and the that notations we will be following in the rest of this course we'll begin with just some very simple definitions an algorithm, which is an outline of the steps that a program has to take or that any computational procedure has to take a program on the other hand is an implementation of an algorithm it could be in any programming language a data structure is the way we need to organise the data so that it can be used effectively by the program you all are familiar with certain data structures an array or a list for instance so this course is about you will be seeing a lot more data structures in this course and you'll see how to use them in various algorithms so we take a particular problem try to solve that problem and in the process develop data structures the best way of organising the data associated with that problem so what's an algorithmic problem? an algorithmic problem is essentially you have a certain specification of an input as is given here and you specify what the output should be like and the specification of an input could be well here is one specification a sorted, non-decreasing sequence of natural numbers of non-zero finite length that's an input that's a completely specified input i have given two examples here of inputs which meet the specification i've not given any output specification yet now what is an instance? these are two instances of the input this is a specification for the input and you can have any possible instance you can take any sequence of sorted, non-decreasing numbers and tht would form an input instance so there are infinitely many input instances possible here so an algorithm is essentially describing the actions that one should take on the input instance to get an output as is desired, as is specified and again just as there can be inifinitely many input instances there can be infinitely many algorithms for solving a certain problem each one of you could do it in a slightly different way so that brings us to the notion of a good algorithm if there are so many different algorithms for solving a certain problem what is a good algorithm so a good algorithm for us is an efficient algorithm anything that is efficient is good and what is efficient? efficient is something which has small running time and takes less memory these are the two measure of efficient that we will be working with there could be other measures of efficiency but these are the only two we will be considering in this course and most of our time we will be spending with running time space of course, we'll also be analysing the space but most of the time we'll only be worrying about the running time of our algorithm and we will be interested in the efficiency of algorithms as a function of the input size so clearly you can imagine that if i have a small input and my algorithm running on that input, or my program running on that input, will take less amount of time if the input becomes ten times larger then the time taken by the program will also grow maybe it becomes 10 times maybe it becomes twenty times, maybe it becomes 100 times, i do not know so it is this behaviour of the increase in the running time with the increase in the size of the input that will also be of interest to us so we'll come to all of these in a short while as we go through these slides ok now how does one measure running time? so i said efficiency, running time, very important for us how does one measure the running time for an algorithm? so one way would be to what i have put down here as an experimental study you have a certain algorithm, you implement that algorithm which means you write a program in a certain programming language you run the program with varying datasets so some smaller, some larger datasets some would be of some kind some would be of a different kind so varying composition and then you clock the time that the program takes and clock doesn't mean that sit down with a stopwatch you would perhaps just use a system utility such as system current time mililis to clock the time that the program takes and then from that you try and figure out how good your algorithm is so that's what one would call an experimental study of the algorithm now this has certain limitations i've put them down first you have to implement the algorithm to be able to determine how good your algorithm is you have to implement it now that's already a huge overhead you have to -- a considerable amount of time has to be spent doing this then your experiments can only be done on a limited set of inputs 