CS3301 – SYLLABUS
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.
Unit I
- Singly Linked List
- Doubly Linked List
- Circularly Linked List
- Polynomial ADT
Unit II
- Applications of Stack
- Stack ADT
- DeQue
- Circular Queue
Unit III
- Tree Traversal
- Binary Search Tree
- Binary Heap
- AVL Tree
Unit IV
- B tree/ B+ tree
- BFS and DFS
- Dijkstra’s / Prim’s Algorithm
- Euler Circuit
Unit V
- Binary Search
- Insertion/Selection/Merge sort
- Closed hashing (Open Addressing)
- Extendible Hashing