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.

Data Structures

Reading Material
Data Structures and algorithm analysis in C++
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.

KEY DATA COMMUNICATION TERMINOLOGY

• Link: connects adjacent nodes Wires, Cables, Any thing that physically connects two nodes
  

• Path: end-to-end route within a network

• Circuit: the conduit over which data travels

• Packetzing: dividing messages into fixed-length packets prior to transmission over a network’s communication media
  

• Routing: determining a message’s path from sending to receiving nodes

• The transmission medium may itself be a network, so route needs to be specified

Network
“A NETWORK is a set of devices (Nodes) connected by Communication Links”

• Node: Can be a Computer, Printer or any other device capable of sending or receiving
  

• The links connecting Nodes are called COMMUNICATION CHANNELS Networks- Why we need them?

Networks- Why we need them?
It is often impractical for devices to be directly connected for two major reasons:

• The devices are very far apart. They are expensive to connect just two devices with one in Lahore and other in Islamabad
  

• Large set of devices would need impractical number of connections e .g. Telephone Lines in the world and all the computers owned by a single organization

Solution to the Problem=Networks

• Solution is to connect all devices to a central system known as a NETWORK in which all terminals or computers share the links.
  

• Two Main Classifications of the Networks

• LANS
• WANS

DISTRIBUTED PROCESSING

• Instead of a single large machine being responsible for all aspects of a process ,each separate computer handles a subset of the task
  

• Example – Project Given as a part of the Course
• Example – Office Work

Advantages of Distributed Processing

• Security

A system designer can limit the kind of interaction that a given user can have with
the entire system.

• For example : Bank’s ATM

• Distributed Data bases

No one system need to provide storage capacity for the entire database

• For example WWW gives user access to pages stored anywhere on Internet

• Faster Problem Solving

Multiple computers working on a problem can solve a problem faster than a
computer working alone

• Security through Redundancy

Multiple computers running the same program provide security through redundancy
If one computer's hardware breaks down others cover up

• Collaborative Processing

Both multiple computers and multiple users can interact for a task