FACULTY OF ENGINEERING & TECHNOLOGY

Second Year Bachelor of Engineering

Course Code: 102040301

Course Title: Data structures

Type of Course:Professional Core Course

Course Objectives:
To understand the concepts of data structures and how these concepts are useful in problem solving.
To get accustomed with elementary data structures: Linear, Non-linear
To practice programming techniques for efficient storage and retrieval for developing sophisticated
computer applications.

Teaching & Examination Scheme:

Contact hours per week Course Examination Marks (Maximum / Passing)
Credits Internal External
Lecture Tutorial Practical Total
Theory J/V/P* Theory J/V/P*
4 0 2 5 40/14 60/21 20/7 30/10 150/52
* J: Jury; V: Viva; P: Practical

Detailed Syllabus:
Sr. Contents Hours
1 Introduction to Data Structure 2
Introduction, Primitive Data Structure, Importance of Data Structure, Types
of Data Structure, Primitive & Non-Primitive Data types.
2 Elementary Data Structure - Linear 12
Array: Definition & concept, Representation & Application, 2D & 3D arrays,
Matrix representation
Stack: Definition & concept, Representation, applications, Expression: Infix,
prefix & postfix, Expression conversion, stack & expression, recursion.
Queues: Definition & concept, types, representation, applications
Linked List: Definition & concepts, types, representation, applications
3 Elementary Data Structure – Non-Linear 10
Trees: Definition & Concept, Representation & Application, types, Traversals,
Advanced Tree Concepts: AVL Tree, Balancing, Height/Weight Balancing,
Rotation
Graphs: Definition & Concept, Representation & Application, types,
Traversals.
Advanced Graph Concepts: Spanning Trees, Shortest Paths, DFS/BFS.

Page 1 of 4
 4 Sorting Techniques 8
Introduction, Types of sorting techniques: Bubble sort, Radix sort, Selection
sort, Quick sort, Merge sort, Insertion sort
5 Searching & Hashing Techniques 8
Introduction
Searching: Linear search, Binary search,
Hashing: The symbol table, Hashing Functions, Collision-Resolution
Techniques,
6 Advanced Data Structures 6
Heaps: Types of Heap, applications, Binary Heap, Fibonacci Heap, Building a
Heap, Heaps & Priority Queues, Heapify function.
Red-Black Trees: Introduction & concept, properties, applications, insert &
delete operation in Red-Black Trees, Balancing.
Forests: Sets, Dis-joint sets, Forest-trees, usage & applications, operations

Suggested Specification table with Marks (Theory) (Revised Bloom’s Taxonomy):

Distribution of Theory Marks R: Remembering; U: Understanding; A: Application,
R U A N E C N: Analyze; E: Evaluate; C: Create
10% 30% 40% 20% 0% 0%
Note: This specification table shall be treated as a general guideline for students and teachers. The actual distribution of
marks in the question paper may vary slightly from above table.

Reference Books:
1 Data Structures using C & C++ -By Ten Baum Publisher – Prenctice-Hall International.
2 Fundamentals of Computer Algorithms by Horowitz, Sahni, Galgotia Pub. 2001 ed.
3 Data Structures: A Pseudo-code approach with C -By Gilberg & Forouzan PublisherThomson
Learning.

Course Outcomes (CO):

Sr. Course Outcome Statements %weightage
CO-1 Describe the efficient methods of data storage and retrieval 10
CO-2 Implement dynamic memory allocation in for different data structures 10
CO-3 Design and implement linear data structures 30
CO-4 Design and implement Non-linear data structures 30
CO-5 Design and implement sorting and searching techniques 20

Page 2 of 4
List of Practicals / Tutorials:
1 Write a program to insert/delete in linear array at specific position.
Write a program to remove duplicate elements from liner array.
Write a program to read 10 integers in an array. Sort them out on the basis of number of digits
in each element.
2 Demonstrate the concept of Call by value and Call by Reference.
Write a program to prints array elements in reverse orders applying pointers
Write program to implement stack and simple queue using array
3 Write a program for stack using array for the following operations:
Push, Pop, Peek and IsEmpty.
Write a program for queue using array for the following operations:
Enqueue, Dequeue, IsEmpty, IsFull.
Write a program for circular queue using array for the following operations:
Enqueue, Dequeue, IsEmpty, IsFull.
4 Write a program for single linked list for the following operations:
1. Count the number of nodes in a given linked list
2. Delete the desired node from linked list
3. Insert the new node after the desired node into the linked list
4. Create a new list by reversing the list
5. Concatenates two linked list
Write a program for stack using linked list for the following operations:
Push, Pop, Peek and IsEmpty.
Write a program for queue using linked list for the following operations:
Enqueue, Dequeue, IsEmpty,
5 Write a program of conversion of an expression from infix to Postfix, Prefix.
Write a program to evaluate postfix expression.
6 Write a program to implement doubly linked list for the following operations:
1. Insert a new node after the desired node
2. Delete the desired note
3. Display the nodes of doubly linked list
Write a program to implement circular doubly linked list for the following operations:
1. Insert a new node after the desired node
2. Delete the desired note
3. Display the nodes of doubly linked list
7 Write a program to construct binary search tree.
Write a program to travers binary search tree.
8 Write a program to construct AVL tree

Page 3 of 4
9 Write a program to demonstrate DFS and BFS.
Write a program for given a directed graph, and check whether the graph contains a cycle or
not. It should print true if the given graph contains at least one cycle, else it should print false.
Write a program to implement minimum spanning tree algorithm
11 Write a program to implement binary search
Write a program to implement: Bubble sort, Radix sort, Selection
12 Write a program to implement: Quick sort, Merge sort, Insertion sort
Write a program to implement the mechanism to handle hash collision by:
1. Separate chaining
2. Open addressing
13 Write a program to implement max-heap.
Write a program to implement Red-Black tree.

Supplementary learning Material:

1 NPTEL courses

Curriculum Revision:
Version: 1
Drafted on (Month-Year): Feb-21
Last Reviewed on (Month-Year): Feb-21
Next Review on (Month-Year): Click or tap to enter a date.

Page 4 of 4