Data Structure and Algorithms
Course Introduction
Puneet Kumar Jain
CSE Department
National Institute of Technology Rourkela
Course Objective
To make students aware of efficient storage and systematic
operations on data using data structure
To make students aware of applications of data structure
COURSE OUTCOMES
The students gather generalized knowledge on representing,
storing, and operating on data in a systematic manner.
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Objective of the course
To answer questions like these
Which data structure should be used to store the data for the given
application/project?
What is the expected complexity of the operations to be performed
on the stored data?
Can we connect all of our telephone customers with less than 1,000
miles of cable?
To present the commonly used data structures.
To introduce the idea of tradeoffs between costs and benefits
associated with every data structure. This is done by describing, for
each data structure, the amount of space and time required for typical
operations.
To teach how to measure the effectiveness of a data structure or
algorithm.
Ref: Clifford A. Shaffer, “Data Structures and Algorithm, Analysis”, Edition 3.2 (C++ Version), 2013
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Course topics
Part A. Defining data, data types, data structure, classification of
data structures (linear and non-linear), understanding data
structure and storage structure
Part B. Defining an algorithm, its properties, growth of a function
complexity, asymptotic analysis, asymptotic notations for
complexity analysis, comparing standard growth rates
Part C. Linear array: its representation in memory, traversal, and
operations on it. 2D array: its representation in memory, traversal,
and operations on it Generalized representation of multi-
dimensional array on memory.
Part D. Linked List: Node structure, traversal, insertion and
deletion from a linked list, circular linked list, two way linked list.
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Course topics
Part E: Sparse matrix, representation using triplet array, chain
representations (single chain, row chain, orthogonal list)
Part F: Stack (operations on stack, array and linked list
representation, application in conversion of expression from infix
to postfix, and in evaluation of postfix notation)
Part G: Queue (operations on queue, array and linked list
representation, deque, priority queue)
Part H: Searching algorithms (linear search, binary search,
Fibonacci search)
Part I: Sorting algorithms (bubble sort, selection sort, insertion
sort, merge sort, quick sort)
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Course topics
Part J: Tree (Terminologies, representation, binary tree and its
traversal)
Part K: Binary search tree and operations on it, properties of BST,
binary expression tree
Part L: AVL tree and operations on it
Part M: m-way search tree and B-tree
Part N: Heap (min-heap and max-heap)
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Course topics
Part O: Graphs (terminologies, storage, Dijkstra's shortest path
algorithm, traversal: DFS, BFS, generalized shortest path
problems, Bellman-Ford algorithm, Floyd-Warshall Algorithm)
Part P: Spanning tree, Minimum spanning tree, Prim's and
Kruskal's algorithms
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Textbook references
Text Book:
S. Lipschutz, Data Structures, Tata McGraw-Hill, ISBN: 9780070601680
M. A. Weiss, Data Structures and Algorithm Analysis in C, Pearson Education ,
ISBN:9798178081679
E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structures, Computer
Science Press , ISBN: 978-0716780427
Michael T. Goodrich (Author), Roberto Tamassia (Author), Michael H. Goldwasser (Author),
Data Structures and Algorithms in Java, Willey, ISBN:1118771338
SUPPLEMENTARY READING
A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data Structures & Algorithms, Pearson Education
India , ISBN: 9788178081021
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, The MIT
Press , ISBN: 978-0262033848
OTHER RECOMMENDATIONS:
Lecture Series on Data Structures and Algorithms by Dr. Naveen Garg, Department of
Computer Science and Engineering, IIT Delhi.
Data Structures and Algorithms | NPTEL Online Videos, Courses - IIT Video Lectures (nptelvideos.in)
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Evaluation Methods:
Item Weightage
Quiz/Assignment/Project 20
Midterm 30
Endterm 50
** Tentative (subject to Institute guidelines)**
Quiz: There will be two announced quizzes for 10 marks
Assignments: Regular assignments will be given on the topics covered in the class
Project: You may select a research paper on recent data structures to implement.
Attendance requirements: As per the institute rules
Issues related to any evaluation component should be raised within 3 days from the
conduction or deadline of the respective component.
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
Feedback!!
Course material and delivery
Your expectations from the course
jainp@nitrkl.ac.in
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
• Let’s Get Started!!
NIT Rourkela Puneet Kumar Jain “Data Structure and Algorithms”
