• Explain fundamental concepts and importance of data structures.
• Define and classify different types of data structures.
• Differentiate   between   data   structures    and abstract data types (ADTs).
• Analyze and evaluate algorithms in terms of time and space complexity.

Unit I: Introduction to data Structure [3 Hrs.]

1. Introduction
2. Definition,
3. Classification of data structure
4. Abstract Data Type
5. Comparison between Data structure and ADT,
6. Algorithm
7. Analysis algorithm
8. Design algorithm
   • Incremental approach
   • Divide and conquer
9. Performance analysis and measurement
   • Space complexity
   • Time complexity

• Discuss the principles and characteristics of recursion. 
• Apply recursion to solve problems and implement algorithms efficiently.

Unit II: Recursion [4 Hrs.]

1. Introduction to Recursion
2. Principle of Recursion
3. Types of Recursion    
   • Direct    
   • Indirect    
   • Linear    
   • Tail recursion
4. Recursion Examples    
   • TOH    
   • Fibonacci Series
5. Application of Recursion

• Become proficient in using stacks and understanding their terms.
• Proficiency in implementing stack algorithms such as POP and PUSH.
• Application of stacks in solving problems like reverse string, postfix expression evaluation, and infix to postfix conversion.

Unit III: Stacks [4 Hrs.]

1. Introduction
2. Operation stack
3. Stack terminology
4. Algorithm for POP and PUSH
5. Stack Applications    
   • Stack frame    
   • Reverse string    
   • Calculation of postfix expression    
   • A notation conversion
6. Algorithm for converting infix expression to postfix form

• Discuss of queue terminology and operations.
• Gain proficiency in implementing queue insertion and deletion algorithms.
• Recognize queue variations and their applications, such as circular queues and priority queues.

Unit IV: Queue [4 Hrs.]4.1 

Introduction

1. Queue terminology
2. Algorithm for insertion in queue
3. Algorithm for deletion in queue
4. Limitation of simple queue
5. Variation in queue    
   • Circular queue    
   • Priority queue
6. Application of queue

• Comprehend the advantages and disadvantages of linked lists.
• Define key terms associated with linked lists, such as data field and linked field.
• Demonstrate the representation of a linear linked list.
• Execute operations on linked lists including creation, insertion, deletion, traversal, searching, concatenation, and display.
• Identify and differentiate between various types of linked lists, including single, double, circular, and circular double linked lists.

Unit V: Linked List [5 Hrs.]

1. Introduction
2. Linked List
3. Advantage and disadvantage
4. Key terms    
   • Data field    
   • Link field
5. Representation of linear linked list
6. Operations of linked list    
   • Creation    
   • Insertion    
   • Deletion    
   • Traversing   
   •  Searching   
   •  Concatenation
   •  Display
7. Types of linked list    
   • Singly linked list    
   • Doubly linked list    
   • Circular linked list    
   • Circular doubly linked list
8. Create single linked list
9. Insertion at specific position
10. Deletion at specific position
11. Application: Addition of two polynomials

• Define tree terminology and apply it, including concepts like strictly binary trees and complete binary trees.
• Understand different representations of binary trees, like array and linked list representations.
• Create a binary tree and implement various traversal methods.
• Perform operations on binary search trees, including insertion, search, and deletion, and understand their properties.
• Learn about AVL balanced trees, their principles, properties, and how they ensure efficient data structure operations by maintaining balance and minimizing search times

Unit VI: Trees [7 Hrs.]

1. Introduction
2. Tree terminology
3. Binary tree    
   • Strictly binary tree
   • Complete binary tree    
   • Extended binary tree
4. Binary tree representation    
   • Array representation    
   • Linked list representation
5. Create binary tree
6. Tree traversal    
   • Preorder    
   • Inorder    
   • Postorder
7. Binary Search Tree (BST)    
   • Insertion    
   • Search    
   • Deletion
8. Tree height, level, depth
9. AVL Tree
10. Huffman Algorithm
11. B-Tree

• Understand the distinction between internal and external sorting techniques.
• Learn various common sorting algorithms such as Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort, Shell Sort, and Binary Sort.
• Analyze the efficiency of sorting algorithms and their performance using Big O notation.
• Implement sorting algorithms and evaluate their effectiveness in sorting large datasets.

Unit VII: Sorting [7 Hrs.]

1. Introduction
2. Internal and External sorting
3. Sorting algorithms    
   • Bubble sort    
   • Insertion sort    
   • Selection sort    
   • Quick sort    
   • Merge sort    
   • Shell sort    
   • Binary sort
4. Efficiency of sorting and Big O notation

• Various searching techniques including Sequential Search, Binary Search, and Tree Search.
• Learn about hashing techniques, including hash functions and hash tables, and their applications.
• Explore collision resolution techniques such as linear probing, quadratic probing, and double hashing.
• Compare the efficiency of different search techniques and hashing methods to determine their suitability for various applications.

Unit VIII: Searching [5 Hrs.]

1. Introduction
2. Searching techniques    
   • Sequential search    
   • Binary search    
   • Tree search
3. Hashing    
   • Hash functions    
     • Characteristics of good hash function    
     • Types of hash function    
   • Hash tables and applications
4. Collision resolution techniques    
   • Linear probing    
   • Quadratic probing    
   • Double hashing    
   • Chaining
5. Rehashing
6. Efficiency comparison

• Understand the fundamental concepts and terminology related to graphs.
• Learn about different types of graphs, including undirected and directed graphs.
• Explore graph representation techniques and graph traversal algorithms such as Breadth-First Search (BFS) and Depth-First Search (DFS).
• Study spanning trees, minimum spanning trees, and algorithms such as Kruskal's algorithm and Prim's algorithm for their construction.

Unit IX: Graph [7 Hrs.]

1. Introduction
2. Graph terminology
3. Types of graph    
   • Undirected graph    
   • Directed graph
4. Graph representation
5. Graph traversal    
   • BFS    
   • DFS
6. Spanning tree and MST    
   • Kruskal’s algorithm    
   • Prim’s algorithm
7. Shortest path (Dijkstra’s Algorithm)
8. Applications

• Learn the concept of asymptotic notations, including Big O, Omega, and Theta notation.
• Learn the limitations of Big O notation and its applicability in analyzing algorithmic complexity.

Unit X: Growth Functions [2 Hrs.]

1. Introduction to asymptotic notation
2. Big O notation
3. Omega notation
4. Theta notation
5. Limitation of Big O notation

Semester-End examination

50

30

20