**CS3301
**

**DATA
STRUCTURES**

**COURSE
OBJECTIVES: **

•
To understand the concepts of ADTs.

•
To Learn linear data structures – lists, stacks, and queues.

•
To understand non-linear data structures – trees and graphs.

•
To understand sorting, searching and hashing algorithms.

•
To apply Tree and Graph structures.

**UNIT
I LISTS **

Abstract
Data Types (ADTs) – List ADT – Array-based implementation – Linked list
implementation – Singly linked lists –
Circularly linked lists – Doubly-linked lists – Applications of lists –
Polynomial ADT – Radix Sort –
Multilists.

**UNIT
II STACKS AND QUEUES**

Stack
ADT – Operations – Applications – Balancing Symbols – Evaluating arithmetic
expressions Infix to Postfix conversion – Function Calls – Queue ADT –
Operations – Circular Queue – DeQueue –
Applications of Queues.

**UNIT
III TREES **

Tree
ADT – Tree Traversals - Binary Tree ADT – Expression trees – Binary Search Tree
ADT – AVL Trees – Priority Queue (Heaps)
– Binary Heap.

**UNIT
IV MULTIWAY SEARCH TREES AND GRAPHS **

B-Tree
– B+ Tree – Graph Definition – Representation of Graphs – Types of Graph -
Breadth-first traversal – Depth-first
traversal –– Bi-connectivity – Euler circuits – Topological Sort – Dijkstra's algorithm – Minimum Spanning Tree – Prim's
algorithm – Kruskal's algorithm

**UNIT
V SEARCHING, SORTING AND HASHING TECHNIQUES **

Searching
– Linear Search – Binary Search. Sorting – Bubble sort – Selection sort –
Insertion sort – Shell sort –. Merge
Sort – Hashing – Hash Functions – Separate Chaining – Open Addressing –Rehashing – Extendible Hashing.

**COURSE
OUTCOMES: **

At
the end of this course, the students will be able to:

CO1:
Define linear and non-linear data structures.

CO2:
Implement linear and non–linear data structure operations.

CO3:
Use appropriate linear/non–linear data structure operations for solving a given
problem. CO4: Apply appropriate graph algorithms for graph applications.

CO5:
Analyze the various searching and sorting algorithms.

**TEXT
BOOKS **

1.
Mark Allen Weiss, Data Structures and Algorithm Analysis in C, 2nd Edition,
Pearson Education, 2005.

2.
Kamthane, Introduction to Data Structures in C, 1st Edition, Pearson Education,
2007

**REFERENCES
**

1.
Langsam, Augenstein and Tanenbaum, Data Structures Using C and C++, 2nd
Edition, Pearson Education, 2015.

2.
Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein,
Introduction to Algorithms", Fourth
Edition, Mcgraw Hill/ MIT Press, 2022.

3.
Alfred V. Aho, Jeffrey D. Ullman,John E. Hopcroft ,Data Structures and
Algorithms, 1st edition, Pearson, 2002.

4.
Kruse, Data Structures and Program Design in C, 2nd Edition, Pearson Education,
2006.