1. Introduction to Data Structures and Algorithm Analysis………………… 7
1.1. Introduction
1.1.1 Need of Data Structure
1.1.2 Definitions-Data and Information, Data type, Data object, ADT, Data Structure
1.1.3 Types of Data Structures
1.2 Algorithm Analysis
1.2.1 Space and Time Complexity
1.2.2 Best, Worst, Average case analysis, Asymptotic notations (Big-O (O) , Omega Ω, Theta (Θ) ), Problems on time complexity calculation
2. Array as a Data Structure……………………………………………………………. 21
2.1 ADT of array, Operations and Applications of Array
2.2 Searching Techniques
2.2.1 Sequential / Linear search 2.2.2 Binary Search
2.2.3 Comparison of Searching Techniques
2.3 Sorting Techniques
2.3.1 Terminology- Internal, External, Stable, In-place Sorting
2.3.2 Comparison Based Sorting Techniques – Bubble Sort, Insertion Sort, Selection Sort
2.3.3 Algorithm design strategies -Divide and Conquer strategy, Merge Sort, Quick Sort
2.3.4 Non Comparison Based Sorting: Counting Sort, Radix Sort
2.3.5 Analysis of sorting techniques.
2.3.6 Comparison of sorting Techniques
3. Linked List………………………………………………………………………………….. 34
3.1 Introduction to Linked List
3.2 Implementation of Linked List – Static & Dynamic representation,
3.3 Types of Linked List-– Singly, Doubly, Circular (Singly)
3.4 Operations on Linked List – create, display, insert, delete, reverse, search,
sort, concatenate and merge3.5 Applications of Linked List – Polynomial Representation, Addition of
two polynomials
3.5.1 Generalized linked list – Concept, Representation)
4. Stack ………………………………………………………………………………………….. 71
4.1 Introduction to Stack
4.2 Operations – init(), push(), pop(), isEmpty(), isFull(), peek(), time
complexity of operations.
4. 3 Representation – Static (Array) and Dynamic (Linked List)
4.4 Applications of stack
4.4.1 Function call and recursion, String reversal, palindrome checking
4.4.2 Expression types – infix, prefix and postfix, expression conversion
and evaluation (Implementation of infix to prefix , infix to postfix,
evaluation of postfix)
5. Queue…………………………………………………………………………………………. 101
5.1 Introduction to Queue
5.2 Operations – init(), enqueue(), dequeue(), isEmpty(), isFull(), peek(),time complexity of operations, differences with stack.
5.3 Implementation – Static (Array) and Dynamic (Linked List) with comparison
5.4 Types of Queue – Linear Queue, Circular Queue, Priority Queue, Double Ended Queue (only Concept of Doubly Ended Queue)
5.5 Applications of queue