Unit 1 Introduction to Algorithm and Data Structures lntroduction : From Problem to Proqram (Problem, Solution, Alqorithm, Data Structure and Proqram). Data Structures : Data, Information, Knowledqe, and Data structure, Abstract Data Types (ADT), Data Structure Classification (Linear and Non-linear, Static and Dynamic, Persistent and Ephemeral data structures). Algorithms: Problem Solvinq, Introduction to alqorithm, Characteristics of alqorithm, Alqorithm desiqn tools: Pseudo-code and flowchart. Complexity of algorithm: Space complexity, Time complexity, Asymptotic notation- Biq-0, Theta and Omeqa, Findinq complexity usinq step count method, Analysis of proqramminq constructs-Linear, Quadratic, Cubic, Loqarithmic. Algorithmic Strategies : Introduction to alqorithm desiqn strateqies - Divide and Conquer, and Greedy strateqy. (Chapter - 1) Unit II Linear Data Structure using Sequential Organization Concept of Sequential Orqanization, Overview of Array, Array as an Abstract Data Type, Operations οη Array, Merqinq of two arrays, Storaqe Representation and their Address Calculation : Row major and Column Major, Multidimensional Arrays : Two-dimensional arrays, n-dimensional arrays. Concept of Ordered List, Single Variable Polynomial : Representation usinq arrays, Polynomial as array of structure, Polynomial addition, Polynomial multiplication. Sparse Matrix : Sparse matrix representation usinq array, Sparse matrix addition, Transpose of sparse matrix- Simple and Fast Transpose, Time and Space tradeoff. (Chapter - 2), Unit III Searching and Sorting Searching: Search Techniques-Sequential Search/Linear Search, Variant of Sequential Search- Sentinel Search, Binary Search, Fibonacci Search, and Indexed Sequential Search. Sorting: Types of Sorting-Internal and External Sorting, General Sort Concepts-Sort Order, Stability, Efficiency, and Number of Passes, Comparison Based Sorting Methods-Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Shell Sort, Non-comparison Based Sorting Methods-Radix Sort, Counting Sort, and Bucket Sort, Comparison of All Sorting Methods and their complexities. (Chapter - 3) Unit IV Linked List Introduction to Static and Dynamic Memory Allocation, Linked List: Introduction of Linked Lists, Realization of linked list using dynamic memory management operations, 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, Representation of Polynomial using GLL. (Chapter - 4) Unit V Stack Basic concept, stack Abstract Data Type, Representation of Stacks Using Sequential Organization, stack operations, Multiple Stacks, Applications of Stack- Expression Evaluation and Conversion, Polish notation and expression conversion, Need for prefix and postfix expressions, Postfix expression evaluation, Linked Stack and Operations. Recursion - concept, variants of recursion - direct, indirect, tail and tree, Backtracking algorithmic strategy, use of stack in backtracking. (Chapter - 5) Unit VI Queue Basic concept, Queue as Abstract Data Type, Representation of Queue using Sequential organization, Queue Operations, Circular Queue and its advantages, Multi-queues, Linked Queue and Operations. Deque-Basic concept, types (Input restricted and Output restricted), Priority Queue- Basic concept, types(Ascending and Descending). (Chapter - 6)
