Syllabus
3CAI4-05: Data Structures and Algorithms
Unit 1. Stacks: Basic Stack Operations, Representation of a Stack using Static Array and Dynamic Array, Multiple stack implementation using single array, Stack Applications: Reversing list, Factorial Calculation, Infix to postfix Transformation, Evaluating Arithmetic Expressions and Towers of Hanoi.
Unit 2. Queues: Basic Queue Operations, Representation of a Queue using array, Implementation of Queue Operations using Stack, Applications of Queues- Round Robin Algorithm. Circular Queues, DeQueue Priority Queues.
Linked Lists: Introduction, single linked list, representation of a linked list in memory, Different Operations on a Single linked list, Reversing a single linked list, Advantages and disadvantages of single linked list, circular linked list, double linked list and Header linked list.
Unit 3. Searching Techniques: Sequential and binary search. Sorting Techniques: Basic concepts, Sorting by: bubble sort, Insertion sort, selection sort, quick sort, heap sort, merge sort, radix sort and counting sorting algorithms.
Unit 4. Trees: Definition of tree, Properties of tree, Binary Tree, Representation of Binary trees using arrays and linked lists, Operations on a Binary Tree, Binary Tree Traversals (recursive), Binary search tree, B-tree , B+ tree, AVL tree, Threaded binary tree.
Unit 5. Graphs: Basic concepts, Different representations of Graphs, Graph Traversals (BFS & DFS), Minimum Spanning Tree(Prims &Kruskal), Dijkstra’s shortest path algorithms.Hashing: Hash function, Address calculation techniques, Common hashing functions, Collision resolution: Linear and Quadratic probing, Double hashing.