Data Structures syllabus

Introduction of Data Structures & types. Complexity of algorithm: Space complexity, Time complexity, Asymptotic notation- Big-O, Theta and Omega, finding complexity using step count method, Analysis of programming constructs-Linear, Quadratic, Cubic, Logarithmic. Searching: Sequential Search, Binary Search. Sorting: Insertion sort, Bubble Sort, Merge sort, Selection Sort, Quick sort, Radix sort. Hash: Hash Table, Hash Function, Collision Resolution Techniques in Hashing-Chaining, Open Addressing-Linear, Quadratic Probing and Double Hashing. Hash table overflow open addressing and chaining.

Case Study: Employee Records Database Optimization, finding employees based on salary or sorting them by department using Array

Introduction to Static and Dynamic Memory Allocation. Linked List: Introduction of Linked Lists, Realization of linked list using dynamic memory management, operations on Linked Lists, Linked List as ADT, Types of Linked List: singly linked, linear and Circular Linked Lists, Doubly Linked List, Doubly Circular Linked List, Primitive Operations on Linked List-Create, Traverse, Search, Insert, Delete, Sort, Concatenate. Polynomial Manipulations- Polynomial addition. Generalized Linked List (GLL) concept.

Case Study : Growing employee database dynamically using LL.

Stack: Introduction of stack, stack Abstract Data Type, Representation of Stacks Using Sequential Organization, stack operations, Applications of Stack- Expression Evaluation and Conversion. Recursion- concept. Queue: Introduction of Queue, Queue as Abstract Data Type, Representation of Queue using Sequential organization. Queue Operations. Circular Queue and its advantages, Deque-introduction, Priority Queue.

Case study: Backtracking algorithmic strategy, Use of stack in backtracking.

Case study: Job scheduling using priority queue.

Tree: Introduction of tree, Representations, Traversals, Binary tree, Binary search tree, Threaded Binary search tree- concepts, threading, insertion and deletion of nodes, Optimal Binary Search Tree (OBST), Height Balanced Tree- AVL tree, Heap Tree

Case study : Compare the complexity of BST and Linear search

Graph: Introduction of graph, storage representation, Adjacency matrix, adjacency list, DFS, BFS, Minimum spanning Tree - Prims and Kruskal Algorithms, Dijkstra’s Single source shortest path, All pairs shortest paths- Flyod- Warshall Algorithm, Topological ordering.

Case study: Analyzing social interactions and influence within a social network.