Data Structures and Algorithms

Subject code – CS113

L-T-P Scheme: 3-0-0

Prerequisite
Students must have already registered for the course, “Computer
Programming” (CS101).

Scope and Objectives:

This course develops:

 problem solving ability using programming
 ability to express solutions to problems clearly and precisely
 ability to design and analyze algorithms
 introduces with fundamental data structures
 Strengthen ability to design and evaluate ADTs, nonlinear
temporary and persistent data structures and related
algorithms.
Learning Outcome:

The students shall acquire the generic skills to design and

implement data structures and related algorithms for a
broad-based set of computing problems.
Course Outcome
Course Description
Outcome
CO1 Summarize the various types of data structures and concept of
algorithmic complexity.
CO2 Examine the various searching and sorting algorithms based on
their complexity.
CO3 Apply linear and non-linear data structures techniques to solve a
problem.
CO4 Analyze various data structure to design optimum algorithm for a
given problem.
Syllabus

UNIT 1: Introduction to Data Structures, Algorithm and Complexity

Data structure overview, need of data structure and how to select relevant data
structure for given problem, basic C data types and ADT. Algorithm overview and its
properties, problem analysis and construction of algorithm, difference among
algorithm, program, and software, algorithm analysis and complexity, asymptotic
notations to represent the time complexity.

UNIT II: Searching and Sorting

Overview, memory representation of 1D and 2D array, sparse matrix, operation

supported by an array, Linear search, binary search (iterative), binary search
(recursive), Sorting, Types of sorting algorithms, bubble sort, selection sort, insertion
sort, quick sort, merge sort, heap sort, radix sorting, counting sorting, Bucket
Sorting.
Syllabus

UNIT III: Linear data structures

Linked list, types of linked list, and operations on linked lists. Stack overview,
stack implementation using array and linked list, basic operations on stack,
applications of stack – evaluation of mathematical expression, conversion of
expression from one form to another (Polish Notation), Tower of Hanoi problem.
Queue overview, basic operations on queue – enqueue, dequeue, implementation
of queue using array and linked list, types of queue - linear queue, circular queue.
Syllabus

UNIT IV: Non-linear data structures

Tree definition and its terminology, representation of graph using array and linked
list, tree traversals – preorder, inorder and postorder, binary search tree (BST) with
insertion, deletion and searching operations, extended binary tree and its application
in Huffman tree, Introduction to graph, types of graph, traversal algorithms in graph
– breadth first search, depth first search.

Unit V: Heap, Priority Queues, B-Tree, AVL, Splay Tree, Red-Black Tree, Threaded
Tree. Elementary Graph algorithms: Minimum spanning trees, Kruskal’s algorithm,
Prim’s algorithm. Single source shortest path, all pair shortest path.
Recommended Books

Text Books:
1. Sartaj Sahni, “Fundamentals of Data Structures”, Tata Mc Graw Hill, New York
2. Seymour Lipschutz., “Data Structures with C”, Schaum's Outline Series
3. Narasimha Karumanchi, “Data Structures and Algorithms” Made Easy
4. Corman et al: “Introduction to Computer Algorithms”, the Massachusetts institute of
Technology, Cambridge, Massachusetts
Reference Books:
1. Langsam, Augestein, Tenenbaum: Data Structures using C and C++
2. Weiss: Data Structures and Algorithm Analysis in C/C++
3. Samir K. Bandyopadhyay,” Data Structures using C”
4. Hopcraft, Ullman: Data Structures and Algorithms
Marks Distribution(Data Structures)

Component & Nature Duration Marks /

Weightage
T1 1 hr 15
T2 1&1/2 hrs 25
T3 2hrs 35
Tutorials 05
Attendance 05
Quiz 05
Assignments 10
Total 100
Prerequisite Knowledge

1. Basic programming constructs from C programming, like

data types, operators, decision control, loops, string and
functions etc.
2. Dynamic memory allocation
3. Pointers
4. Structures
 Why This Course?
 Students will be able to write fast programs

 Students will be able to solve new problems

 Students will be able to evaluate the quality of a program (Analysis of Algorithms:

Running time and memory space )

 Students will be able to give non-trivial methods to solve problems.

 Your algorithm (program) will be faster than others.

 Preface of Data structure
Data: simply a value or a set of values of different type which is called data types like string,
integer, char etc.
Structure: Way of organizing information, so that it is easier to use.

Unorganized Well
room organized
room

Data Structure ?
A data structure is a particular way of organizing data in a computer memory so that it can
be used efficiently.
Although computers can perform millions of mathematical computations per second, when
a problem gets larger and complicated, the performance can be an important consideration.
One of the most crucial aspects to how quickly a problem can be solved is how the data is
stored in memory.
Why Data Structures

Human requirement with computers are going to complex day by

day.
To solve the complex requirements in efficient way we need this
study.
 Provide fastest solution of human requirements.
Provide efficient solution of complex problem
Space
 Time
Data Types

Primitive data types (System defined data types): Basic data types available in
programming languages; examples: integers, floats ,doubles, etc.

User defined data types: allow user to defined their own data types.
example:
struct newType{
int data 1;
float data 2;
…….
char data;
};
Classification of Data Structure
Linear Vs Non-linear Data Structures

Linear Data Structures: A linear data structure traverses the data

elements sequentially, in which only one data element can directly be
reached. Ex: Arrays, Linked Lists

Non-Linear Data Structures: Every data item is attached to several

other data items. The data items are not arranged in a sequential
structure. Ex: Trees, Graphs
Operations on Data Structures

Basic operations –
1. Traversing – Accessing and processing record exactly once
2. Insertion – Adding new record to data structure
3. Deletion – Removing particular record from the data structure
4. Searching – Finding the location of the record in data structure
Special operations –
1. Sorting – Arranging the record in some specific order
2. Merging – Combining the records from different data structures
to a single data structure
Commonly used data structures

1. Array
2. Linked list
3. Stack
4. Queue
5. Tree
6. Graph

Note: No single data structure works well for all purposes, so need to
learn several of them:
Example of array
Example of array
Example of Linked list
Example of Linked list
Example of stack and queue
Example of Tree
Example of Graph
Abstract Data Type (ADT)

A data type is considered abstract when it is defined in terms of operations on

it, and its implementation is hidden. i.e. an ADT is implementation independent.
Hence, in case of ADT we know what it does, but not necessarily how it does.

Examples of ADT:

1. Stack: operations are “Push: insert an item onto the stack", “Pop: delete an
item from the stack", "ask if the stack is empty"; stack implementation may be
done using array or linked list or any other data structure.

2. Queue: operations are “Enqueue: add to the end of the queue", “Dequeue:
delete from the beginning of the queue", "ask if the queue is empty"; The
implementation may be as array or linked list or heap.
Cost of Data Structures

Cost of data structure or algorithm is always calculated in terms of following

parameters –
1. Time Complexity: Time required to perform a basic operation on data
2. Space Complexity: Memory space required to store the data items of data
structure
3. Programming efforts to write code for basic operations.
Space – Time Tradeoff

Reduction of required memory space could increase the time of execution.

Example –
1. Compressed and uncompressed data –
A space–time tradeoff can be applied to the problem of data storage. If data is stored
uncompressed, it takes more space but less time than if the data were stored compressed
(since compressing the data reduces the amount of space it takes, but it takes time to run
the decompression algorithm).
Depending on the particular instance of the problem, either way is practical.
2. Smaller code and loop unrolling –
 Larger code size can be traded for higher program speed when applying loop unrolling (A
basic compiler optimization is known as 'loop unrolling. Loop unrolling means going back
to some previous statement.)
 This technique makes the code longer for each iteration of a loop, but saves the
computation time required for jumping back to the beginning of the loop at the end of
each iteration.
Selection of data structure

 Organization of data in memory affects the performance of algorithm

 So, selection of data structure plays important role to make algorithm efficient
But, it depends on the nature of problem and operations to be supported.

Typically, following steps are to be followed to select an efficient data structure –

1. Analyze the problem very carefully and estimate the resources so that solution
must meet.
2. Determine the basic operation to be supported
3. Select the best data structure which meets the above requirements.