Data Structure & Analysis of Algorithms – MCA (205)

Table of Content

UNIT I – Introduction to data structure: Data, Entity, Information, Difference between Data and Information, Data type , Build in data type, Abstract datatype, Definition of data structures, Types of Data Structures: Linear and Non-Linear Data Structure, Introduction to Algorithms: Definition of Algorithms, Difference between algorithm and programs, properties of algorithm, Algorithm Design Techniques, Performance Analysis of Algorithms, Complexity of various code structures, Order of Growth, Asymptotic Notations.
Arrays: Definition, Single and Multidimensional Arrays, Representation ofArrays: Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-D,2-D Array Application of arrays, Sparse Matrices and their representations.Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction & Multiplications of Single variable.
UNIT II – Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Arrayand Linked Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Iteration and Recursion- Principles of recursion, Tail recursion, Removal of recursion Problem solving using iteration and recursion with examples such as binary search, Fibonacci numbers, and Hanoi towers.
Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Dequeue and Priority Queue.Searching: Concept of Searching, Sequential search, Index SequentialSearch, Binary Search. Concept of Hashing & Collision resolutionTechniques used in Hashing.
UNIT III – Sorting: Insertion Sort, Selection Sort, Bubble Sort, Heap Sort, Comparisonof Sorting Algorithms, Sorting in Linear Time: Counting Sort and BucketSort.Graphs: Terminology used with Graph, Data Structure for Graph Representations: Adjacency Matrices, Adjacency List, Adjacency. Graph Traversal: Depth First Search and Breadth First Search, Connected Component.
UNIT IV – Trees: Basic terminology used with Tree, Binary Trees, Binary TreeRepresentation: Array Representation and Pointer (Linked List) Representation, Binary Search Tree, Complete Binary Tree, A Extended Binary Trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Constructing Binary Tree from given Tree Traversal, Operation of Insertion, Deletion, Searching & Modification of data in Binary Search Tree. Threaded Binary trees, Huffman coding using Binary Tree, AVL Tree and B Tree.
UNIT V – Divide and Conquer with Examples Such as Merge Sort, Quick Sort, MatrixMultiplication: Strassen’s AlgorithmDynamic Programming: Dijikstra Algorithm, Bellman Ford Algorithm, All- pair Shortest Path: Warshal Algorithm, Longest Common Sub-sequence Greedy Programming: Prims and Kruskal algorithm.