Data Structures using C++
- To impart the basic concepts of data structure
- To understand the concepts about linear and non linear data structures
- To understand basic concepts and implementation about stacks, queues, arrays, lists, trees and graphs
After the completion of the course, students will be able to –
- To introduce the concepts of Abstract data Type, data structure, performance measurement, time and space complexities of algorithms.
- To discuss the implementation linear data structures such as stacks, queues and lists and their applications.
- To discuss the implementation of different non linear data structures such as trees and graphs.
- To introduce various search data structures such as hashing, binary search trees and b-trees.
- To introduce various internal sorting techniques and analyze their time complexities.
Concept of Structured data – Data structure definition, Different types and classification of data structures, Arrays – Memory allocation and implementation of arrays in memory, array operations, Applications – sparse matrix representation and operations, polynomials representation and addition, Concept of search and sort – linear search, binary search, selection sort, insertion sort, quick sort.
Stacks – Concepts, organization and operations on stacks using arrays (static), examples, Applications – Conversion of infix to postfix and infix to prefix, postfix evaluation, subprogram calls and execution, Multiple stacks representation. Queues – Concepts, organization and operations on queues, examples. Circular queue – limitations of linear queue, organization and operations on circular queue. Double ended queue, Priority queue.
Linked list: Concept of dynamic data structures, linked list, types of linked list, linked list using pointers, insertion and deletion examples, circular linked list, doubly linked lists Applications- linked stacks and queues, memory management basic concepts, garbage collection.
Trees – Concept of recursion, trees, tree terminology, binary trees, representation of binary trees, strictly binary trees, complete binary tree, extended binary trees, creation and operations on binary tree, binary search trees, Creation of binary search tree, tree traversing methods – examples, binary tree representation of expressions.
File – Definition, Operations on file (sequential), File organizations – sequential, Indexed sequential, random files, linked organization, inverted files, cellular partitioning, hashing – hash tables, hashing functions, collisions, collision resolving methods.
Module 1 : Introduction to DS and Concepts of Arrays
This module covers the concepts of Structured data, arrays, searching and sorting techniques.
- Basics of DS
- Introduction to Structured Data
- Array Conepts
- Array Operations- Insertion
- Array Operations- Deletion
- Array Applications- Sparse
- Sparse Matrix Implementation
- Operations on Sparse Matrix
- Generating Original Matrix from Triplet
- Transpose of Sparse Matrix
- Searching Techniques
- Sorting Methods
- Quiz on Module 1
Module 2 : Stacks and Queues