LECUTURE FROM 8th JUNE TO 17th JUNE 2020
CS3 DS MODULE 1
By Abdul Samad C
Course Outline
UNIT – I [6 T + 4 L]
1. Introduction:
2. Elementary data organization
3. Data Structure definition
4. Data type vs. data structure ,Categories of data structures
5. Data structure operations
6. Applications of data structures
7. Algorithms complexity and time-space trade off
8. Big-O notation
9. Strings: Introduction
10. String operations
11. Pattern matching algorithms
1. Introduction
Data structures are used to store data in a computer in an organized form. In C language Different types of data
structures are; Array, Stack, Queue, Linked List, Tree. Structured data types hold a collection of data values. Way of
physical implementation of a data in the memory.
2. Elementary data organization
Data − Data are values or set of values.
Data Item − Data item refers to single unit of values.
Group Items − Data items that are divided into sub items are called as Group Items.
Elementary Items − Data items that cannot be divided are called as Elementary Items.
Attribute and Entity − An entity is that which contains certain attributes or properties, which may be assigned
values.
Entity Set − Entities of similar attributes form an entity set.
Field − Field is a single elementary unit of information representing an attribute of an entity.
Record − Record is a collection of field values of a given entity.
File − File is a collection of records of the entities in a given entity set.
3. Data Structure definition
The data structure is basically a technique of organizing and storing of different types of data items in computer
memory. It is considered as not only the storing of data elements but also the maintaining of the logical relationship
existing between individual data elements.
The Data structure can also be defined as a mathematical or logical model, which relates to a particular organization of
different data elements.
Data structures are considered as the main building blocks of a computer program. So, at the time of selection of data
structure, we should follow these two things so that our selection is efficient enough to solve our problem.
1. The data structure must be powerful enough to handle the different relationship existing between the data.
2. The structure of data also to be simple, so that we can efficiently process data when required.
LECUTURE FROM 8th JUNE TO 17th JUNE 2020
CS3 DS MODULE 1
By Abdul Samad C
Basically, the term data structure and algorithm both are somehow related to each other. Set of a well-defined algorithm and
data structure makes a computer program efficient.
Algorithm + Data Structure = Program
A program can be made using the different data structure to produce the same output. But the efficiency of the program will
depend on the choice of the best data structure to create that particular program. We have a classification of data structures to
choose to make this happen.
4. Data type vs. data structure
Data type describes pieces of data that all share a common property. For example an integer data type describes every integer
that the computer can handle.
Data types are primitive data structures. The primitive data structures are known as basic data structures. These data structures
are directly operated upon by the machine instructions. Normally, primitive data structures have different representation on
different computers.
Example of primitive data structure:
Integer
Float
Character
Pointer
5. Categories of data structures
Primitive data structures
LECUTURE FROM 8th JUNE TO 17th JUNE 2020
CS3 DS MODULE 1
By Abdul Samad C
Data types are primitive data structures. The primitive data structures are known as basic data structures. These data structures
are directly operated upon by the machine instructions. Normally, primitive data structures have different representation on
different computers.
Example of primitive data structure:
Integer
Float
Character
Pointer
Non-Primitive data structure:
The non-primitive data structures are highly developed complex data structures. Basically, these are developed from the
primitive data structure. The non-primitive data structure is responsible for organizing the group of homogeneous and
heterogeneous data elements. Example of Non-primitive data structure:
Arrays
Lists
Files
Non primitive data structures are divided into linear and nonlinear.
A data structures is said to be linear if its elements form a sequence or a linear list. In linear data structure, the data is arranged
in a linear fashion although the way they are stored in memory need not be sequential. Arrays, Linked lists, stacks and queues
are example of linear data structures.
Linked list example
A data structure is said to be nonlinear if the data is not arranged in sequence. The insertion and deletion of data is therefore not
possible in a linear fashion. Trees and graphs are examples of nonlinear data structure.
Tree example
LECUTURE FROM 8th JUNE TO 17th JUNE 2020
CS3 DS MODULE 1
By Abdul Samad C
6. Applications of data structures
Linked Lists: The circular linked list is used in our Personal Computers, where multiple applications are
running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for
running (Operating Systems). it can be used to implement Stacks , Queues , Graphs and Trees
Stack is used when a function is called. Microprocessor operations, Memory management in Operating System
as well as in Portable devices, Expression Evolution and Undo / Redo Operations in applications like photoshop
or Word Processing Softwares. Undo/redo operation in word processors, Expression evaluation and syntax
parsing, many virtual machines like JVM is stack oriented.
Queues are used for inter-process communications. Waiting List in Applications, Task Scheduling etc.
Transport and operations research where various entities are stored and held to be processed later in the queue
performs the function of a buffer. Priority queues - process scheduling in the kernel
Trees - Parsers, File system, Binary Search Trees are used for implementing maps and sets. BSP tree - 3D
computer graphics
Graphs - Connections/relations in social networking sites, Routing, networks of Communication, data
organization etc. DataBase Applications, File Systems in UNIX or LINUX, etc. Social Networking applications
like Facebook, Instagram, Twitter, and also used in Google Maps and Bing maps.
