Credit:4
Lecture
per week:3
Practical
per week:2
Course Outcomes (CO):
CO1 Differentiate basic data structures (arrays, linked lists, stacks, queues) based on their characteristics,operations, and real-world applications.
CO2 Perform basic operations (e.g., )insertion, deletion, search) on fundamental data structures using a chosen programming language.
CO3 Identify the properties and applications of advanced data structures (trees,graphs).
CO4 investigate the properties of various searching and sorting Techniques
CO5 Demonstrate critical thinking and problem-solving skills by applying data structures and algorithms to address complex computational challenges.
CO6 Implement and analyse different data structure algorithms(to solve practical problems
Detailed Syllabus:
Module
Unit Content Hrs
(45+30)
Marks(70)
I Introduction to Data Structures and Basic Algorithms
1 Overview of Data Structures: Data type Vs. Data structure, ADT,Definition of Data structure, Data structure Classification – Linear, Non- Linear (Array, Linked List, Stack, Queue, Tree, Graph)
Introduction to Arrays: Definition, Types (1 Dimensional, 2Dimensional, Multi-Dimensional, Sparse matrix), Different Array Operations with Algorithm (insertion, deletion, traversal
Structures and Self-referential structures Introduction to Linked list: Definition, Types (Single linked list,Doublelinked list, Circular linked list- concept only). Singly Linked List Operations with Algorithm (insertion, deletion,traversal)
2 Introduction to Stack: Definition, stack operations with Algorithm, Applications: recursion, infix to postfix - example and Algorithm Implementation of Stack: using array (overflow & underflow) and
Linkedlist (with algorithm)
Introduction to Queue: Definition, queue operations with Algorithm, Types: Double ended queue (Input Restricted and Output restricted), Circular queue, Applications
Implementation of Queue: using array and Linked list (withalgorithm)I
3 Non- Linear Data Structures Introduction to Trees: Basic terminology, Types(Binary tree-
complete,full, skewed etc., Expression Tree)
Properties of Binary tree, Applications. Binary tree representations- using array and linked list 2
Operations on Binary tree- Insertion, Deletion, Traversal- inorder, preorder, postorder - (concepts with examples)
Algorithm of non-recursive Binary tree traversal
Introduction to Graph: Definition, Basic terminology, Types (Directed,Undirected, Weighted). Graph representation –Adjacency list and Adjacency Matrix, Applications.
4 Sorting and Searching : Introduction to Sorting: Definition, Classification (Internal, External)
Internal Sorting Algorithms: Selection sort- Selection sort algorithm,
Exchange sort- Bubble sort algorithm
External Sorting Algorithms: Merge sort- Demonstrate with example.(NoAlgorithm needed)
Advanced sorting Algorithm-: Quick sort- Demonstrate with example.
Introduction to Searching: Linear search and Binary search(Algorithm needed) with example. Hashing: Hash Tables, Hash Functions, Different Hash Functions –Division method, Multiplication method, Mid square method, Folding Method, Collision and Collision resolution Techniques: Open
hashing- Chaining, Closed hashing- Probing5
5 Hands-on Programming in Data Structures: Practical
Implement the following:
1. Basic Operations in a single linked list (Menu driven)
2. Sort the elements in given singly linked list
3. Stack using array.
4. Stack using Linked list
5. Queue using Array
6. Queue using Linked list
7. Sorting algorithms- Selection, Bubble Sort
8. Searching Algorithms- Linear and Binary search
- Teacher: Prabitha M