Syllabus Data Structures - (CS3301) 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. (Chapter - 1) 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. (Chapters - 2, 3) UNIT III TREES Tree ADT - Tree Traversals - Binary Tree ADT - Expression trees - Binary Search Tree ADT - AVL Trees - Priority Queue (Heaps) - Binary Heap. (Chapter - 4) 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. (Chapter - 5) 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. (Chapters - 6, 7)
