Data Structures Guidelines and Practical List
Course Objective: This course aims at developing the ability to use basic data structures like array, stacks, queues, lists, trees and hash tables to solve problems. C++ is chosen as the language to understand implementation of these data structures.
Data Structures Guidelines
Arrays: single and multi-dimensional arrays, analysis of insert, delete and search operations in arrays (both linear search and binary search), implementing sparse matrices, applications of arrays to sorting: selection sort, insertion sort, bubble sort, comparison of sorting techniques via empirical studies. Introduction to Vectors.
Linked Lists: Singly- linked, doubly-linked and circular lists, analysis of insert, delete and search operations in all the three types, implementing sparse matrices. Introduction to Sequences.
Queues: Array and linked representation of queue, de-queue, comparison of the operations on queues in the two representations. Applications of queues.
Stacks: Array and linked representation of stacks, comparison of the operations on stacks in the two representations, implementing multiple stacks in an array; applications of stacks: prefix, infix and postfix expressions, utility and conversion of these expressions from one to another; applications of stacks to recursion: developing recursive solutions to simple problems, advantages and limitations of recursion.
Trees: Introduction to tree as a data structure; binary trees, binary search trees, analysis of insert, delete, search operations, recursive and iterative traversals on binary search trees. Height-balanced trees (AVL), B trees, analysis of insert, delete, search operations on AVL and B trees.
Heaps: Introduction to heap as a data structure. analysis of insert, extract-min/max and delete-min/max operations, applications to priority queues.
Hash Tables: Introduction to hashing, hash tables and hashing functions -insertion, resolving collision by open addressing, deletion, searching and their analysis, properties of a good hash function.
Data Structures Reference Books:
- Drozdek, A., (2012), Data Structures and algorithm in C++. 3rd edition. Cengage Learning.
- Goodrich, M., Tamassia, R., & Mount, D., (2011). Data Structures and Algorithms Analysis in C++. 2nd edition. Wiley
Data Structures Practicals List
- Write a program to search an element from a list. Give user the option to perform Linear or Binary search. Use Template functions.
- WAP using templates to sort a list of elements. Give user the option to perform sorting using Insertion sort, Bubble sort or Selection sort.
- Implement Linked List using templates. Include functions for insertion, deletion and search of a number, reverse the list and concatenate two linked lists.
- Implement Doubly Linked List using templates. Include functions for insertion, deletion and search of a number, reverse the list.
- Implement Circular Linked List using templates. Include functions for insertion, deletion and search of a number, reverse the list.
- Perform Stack operations using Linked List implementation.
- Perform Stack operations using Array implementation. Use Templates.
- Perform Queues operations using Circular Array implementation. Use Templates.
- Create and perform different operations on Double-ended Queues using Linked List implementation.
- WAP to scan a polynomial using linked list and add two polynomial.
- WAP to calculate factorial and to compute the factors of a given no. (i)using recursion, (ii)using iteration
- WAP to display fibonacci series (i)using recursion, (ii) using iteration
- WAP to calculate GCD of 2 number (i) with recursion (ii) without recursion
- WAP to create a Binary Search Tree and include following operations in tree: (a) Insertion (b) Deletion by copying (c) Deletion by Merging (d)Search a no. in BST (e) Display its preorder, postorder and inorder traversals Recursively (f) Display its preorder, postorder and inorder traversals Iteratively (g) Display its level-by-level traversals (h) Count the non-leaf nodes and leaf nodes (i) Display height of tree (j) Create a mirror image of tree (k) Check whether two BSTs are equal or not
- WAP to convert the Sparse Matrix into non-zero form and vice-versa.
- WAP to reverse the order of the elements in the stack using additional stack.
- WAP to reverse the order of the elements in the stack using additional Queue.
- WAP to implement Diagonal Matrix using one-dimensional array.
- WAP to implement Lower Triangular Matrix using one-dimensional array.
- WAP to implement Upper Triangular Matrix using one-dimensional array.
- WAP to implement Symmetric Matrix using one-dimensional array.
- WAP to create a Threaded Binary Tree as per inorder traversal, and implement operations like finding the successor / predecessor of an element, insert an element, inorder traversal.
- WAP to implement various operations on AVL Tree.
- WAP to implement heap operations.