ON LINE EARNING FROM SKYLARKPPV.COM: Urdu News Papers

Data Structure

Reading Material Lecture No. 01 Reading Material Data Structures and algorithm analysis in C++ Chapter. 3 3.1, 3.2, 3.2.1 Summary • Introduction to Data Structures • Selecting a Data Structure • Data Structure Philosophy • Goals of this Course • Array • List data structure Welcome to the course of data structure. This is very important subject as the topics covered in it will be encountered by you again and again in the future courses. Due to its great applicability, this is usually called as the foundation course. You have already studied Introduction to programming using C and C++ and used some data structures. The focus of that course was on how to carry out programming with the use of C and C++ languages besides the resolution of different problems. In this course, we will continue problem solving and see that the organization of data in some cases is of immense importance. Therefore, the data will be stored in a special way so that the required result should be calculated as fast as possible. Following are the goals of this course: 􀂃 Prepare the students for (and is a pre-requisite for) the more advanced material students will encounter in later courses. 􀂃 Cover well-known data structures such as dynamic arrays, linked lists, stacks, queues, trees and graphs. 􀂃 Implement data structures in C++ You have already studied the dynamic arrays in the previous course. We will now discuss linked lists, stacks, queues, trees and graphs and try to resolve the problems with the help of these data structures. These structures will be implemented in C++ language. We will also do programming assignments to see the usage and importance of these structures. Information about Data Structure subject is available at: “http://www.vu.edu.pk/ds”. 3 CS301 – Data Structures ___________________________________________________________________ Introduction to Data Structures Let’s discuss why we need data structures and what sort of problems can be solved with their use. Data structures help us to organize the data in the computer, resulting in more efficient programs. An efficient program executes faster and helps minimize the usage of resources like memory, disk. Computers are getting more powerful with the passage of time with the increase in CPU speed in GHz, availability of faster network and the maximization of disk space. Therefore people have started solving more and more complex problems. As computer applications are becoming complex, so there is need for more resources. This does not mean that we should buy a new computer to make the application execute faster. Our effort should be to ensue that the solution is achieved with the help of programming, data structures and algorithm. What does organizing the data mean? It means that the data should be arranged in a way that it is easily accessible. The data is inside the computer and we want to see it. We may also perform some calculations on it. Suppose the data contains some numbers and the programmer wants to calculate the average, standard deviation etc. May be we have a list of names and want to search a particular name in it. To solve such problems, data structures and algorithm are used. Sometimes you may realize that the application is too slow and taking more time. There are chances that it may be due to the data structure used, not due to the CPU speed and memory. We will see such examples. In the assignments, you will also check whether the data structure in the program is beneficial or not. You may have two data structures and try to decide which one is more suitable for the resolution of the problem. As discussed earlier, a solution is said to be efficient if it solves the problem within its resource constraints. What does it mean? In the computer, we have hard disk, memory and other hardware. Secondly we have time. Suppose you have some program that solves the problem but takes two months. It will be of no use. Usually, you don’t have this much time and cannot wait for two months. Suppose the data is too huge to be stored in disk. Here we have also the problem of resources. This means that we have to write programs considering the resources to achieve some solution as soon as possible. There is always cost associated with these resources. We may need a faster and better CPU which can be purchased. Sometimes, we may need to buy memory. As long as data structures and programs are concerned, you have to invest your own time for this. While working in a company, you will be paid for this. All these requirements including computer, your time and computer time will decide that the solution you have provided is suitable or not. If its advantages are not obtained, then either program or computer is not good. So the purchase of a faster computer, while studying this course, does not necessarily help us in the resolution of the problem. In the course of “Computer Architecture” you will see how the more efficient solutions can be prepared with the hardware. In this course, we will use the software i.e. data structures, algorithms and the recipes through which the computer problems may be resolved with a faster solution. Selecting a Data Structure How can we select the data structure needed to solve a problem? You have already studied where to use array and the size of array and when and where to use the 4 CS301 – Data Structures ___________________________________________________________________ pointers etc. First of all, we have to analyze the problem to determine the resource constraints that a solution must meet. Suppose, the data is so huge i.e. in Gega bytes (GBs) while the disc space available with us is just 200 Mega bytes. This problem can not be solved with programming. Rather, we will have to buy a new disk. Secondly, it is necessary to determine the basic operations that must be supported. Quantify the resource constraints for each operation. What does it mean? Suppose you have to insert the data in the computer or database and have to search some data item. Let’s take the example of telephone directory. Suppose there are eight million names in the directory. Now someone asks you about the name of some particular person. You want that this query should be answered as soon as possible. You may add or delete some data. It will be advisable to consider all these operations when you select some data structure. Finally select the data structure that meets these requirements the maximum. Without, sufficient experience, it will be difficult to determine which one is the best data structure. We can get the help from internet, books or from someone whom you know for already getting the problems solved. We may find a similar example and try to use it. After this course, you will be familiar with the data structures and algorithms that are used to solve the computer problems. Now you have selected the data structure. Suppose a programmer has inserted some data and wants to insert more data. This data will be inserted in the beginning of the existing data, or in the middle or in the end of the data. Let’s talk about the arrays and suppose you have an array of size hundred. Data may be lying in the first fifty locations of this array. Now you have to insert data in the start of this array. What will you do? You have to move the existing data (fifty locations) to the right so that we get space to insert new data. Other way round, there is no space in the start. Suppose you have to insert the data at 25th location. For this purpose, it is better to move the data from 26th to 50th locations; otherwise we will not have space to insert this new data at 25th location. Now we have to see whether the data can be deleted or not. Suppose you are asked to delete the data at 27th position. How can we do that? What will we do with the space created at 27th position? Thirdly, is all the data processed in some well-defined order or random access allowed? Again take the example of arrays. We can get the data from 0th position and traverse the array till its 50th position. Suppose we want to get the data, at first from 50th location and then from 13th. It means that there is no order or sequence. We want to access the data randomly. Random access means that we can’t say what will be the next position to get the data or insert the data. Data Structure Philosophy Let’s talk about the philosophy of data structure. Each data structure has costs and benefits. Any data structure used in your program will have some benefits. For this, you have to pay price. That can be computer resources or the time. Also keep in mind 5 CS301 – Data Structures ___________________________________________________________________ that you are solving this problem for some client. If the program is not efficient, the client will not buy it. In rare cases, a data structure may be better than another one in all situations. It means that you may think that the array is good enough for all the problems. Yet this is not necessary. In different situations, different data structures will be suitable. Sometimes you will realize that two different data structures are suitable for the problem. In such a case, you have to choose the one that is more appropriate. An important skill this course is going to lend to the students is use the data structure according to the situation. You will learn the programming in a way that it will be possible to replace the one data structure with the other one if it does not prove suitable. We will replace the data structure so that the rest of the program is not affected. You will also have to attain this skill as a good programmer. There are three basic things associated with data structures. A data structure requires: – space for each data item it stores – time to perform each basic operation – programming effort Goals of this Course Reinforce the concept that costs and benefits exist for every data structure. We will learn this with practice. Learn the commonly used data structures. These form a programmer's basic data structure “toolkit”. In the previous course, you have learned how to form a loop, functions, use of arrays, classes and how to write programs for different problems. In this course, you will make use of data structures and have a feeling that there is bag full of different data structures. In case of some problem, you will get a data structure from the toolkit and use some suitable data structure. Understand how to measure the cost of a data structure or program. These techniques also allow you to judge the merits of new data structures that you or others might develop. At times, you may have two suitable data structures for some problem. These can be tried one by one to adjudge which one is better one. How can you decide which data structure is better than other. Firstly, a programmer can do it by writing two programs using different data structure while solving the same problem. Now execute both data structures. One gives the result before the other. The data structure that gives results first is better than the other one. But sometimes, the data grows too large in the problem. Suppose we want to solve some problem having names and the data of names grows to10 lakhs (one million). Now when you run both programs, the second program runs faster. What does it mean? Is the data structure used in program one not correct? This is not true. The size of the data, being manipulated in the program can grow or shrink. You will also see that some data structures are good for small data while the others may suit to huge data. But the problem is how can we determine that the data in future will increase or decrease. We should have some way to take decision in this regard. In this course we will do some mathematical analysis and see which data structure is better one.

Saturday, October 13, 2012

Urdu News Papers

1 comment: