Bsc. I.T.

Data Structures Syllabus

UnitDetails
I Introduction: Data and Information, Data Structure, Classification of Data Structures, Primitive Data Types, Abstract Data Types, Data structure vs. File Organization, Operations on Data Structure, Algorithm, Importance of Algorithm Analysis, Complexity of an Algorithm, Asymptotic Analysis and Notations, Big O Notation, Big Omega Notation, Big Theta Notation, Rate of Growth and Big O Notation.

Array: Introduction, One Dimensional Array, Memory Representation of One Dimensional Array, Traversing, Insertion, Deletion, Searching, Sorting, Merging of Arrays, Multidimensional Arrays, Memory Representation of Two Dimensional Arrays, General Multi-Dimensional Arrays, Sparse Arrays, Sparse Matrix, Memory Representation of Special kind of Matrices, Advantages and Limitations of Arrays.
II Linked List: Linked List, One-way Linked List, Traversal of Linked List, Searching, Memory Allocation and De-allocation, Insertion in Linked List, Deletion from Linked List, Copying a List into Other List, Merging Two Linked Lists, Splitting a List into Two Lists, Reversing One way linked List, Circular Linked List, Applications of Circular Linked List, Two way Linked List, Traversing a Two way Linked List, Searching in a Two way linked List, Insertion of an element in Two way Linked List, Deleting a node from Two way Linked List, Header Linked List, Applications of the Linked list, Representation of Polynomials, Storage of Sparse Arrays, Implementing other Data Structures.
III Stack: Introduction, Operations on the Stack Memory Representation of Stack, Array Representation of Stack, Applications of Stack, Evaluation of Arithmetic Expression, Matching Parenthesis, infix and postfix operations, Recursion.

Queue: Introduction, Queue, Operations on the Queue, Memory Representation of Queue, Array representation of queue, Linked List Representation of Queue, Circular Queue, Some special kinds of queues, Deque, Priority Queue, Application of Priority Queue, Applications of Queues.
IV Sorting and Searching Techniques: Bubble, Selection, Insertion, Merge Sort. Searching: Sequential, Binary, Indexed Sequential Searches, Binary Search.

Tree: Tree, Binary Tree, Properties of Binary Tree, Memory Representation of Binary Tree, Operations Performed on Binary Tree, Reconstruction of Binary Tree from its Traversals, Huffman Algorithm, Binary Search Tree, Operations on Binary Search Tree, Heap, Memory Representation of Heap, Operation on Heap, Heap Sort.

Advanced Tree Structures: Red Black Tree, Operations Performed on Red Black Tree, AVL Tree, Operations performed on AVL Tree, 2-3 Tree, B-Tree.
V Hashing Techniques: Hash function, Address calculation techniques, Common hashing functions Collision resolution, Linear probing, Quadratic, Double hashing, Bucket hashing, Deletion and rehashing

Graph: Introduction, Graph, Graph Terminology, Memory Representation of Graph, Adjacency Matrix Representation of Graph, Adjacency List or Linked Representation of Graph, Operations Performed on Graph, Graph Traversal, Applications of the Graph, Reachability, Shortest Path Problems, Spanning Trees.

Data Structures Practicals

Practical NoDetails
1 Implement the following:
a Write a program to store the elements in 1-D array and perform the operations like searching, sorting and reversing the elements. [Menu Driven]
b Read the two arrays from the user and merge them and display the elements in sorted order.[Menu Driven]
c Write a program to perform the Matrix addition, Multiplication and Transpose Operation. [Menu Driven]
2 Implement the following for Linked List:
a Write a program to create a single linked list and display the node elements in reverse order
b Write a program to search the elements in the linked list and display the same
c Write a program to create double linked list and sort the elements in the linked list.
3 Implement the following for Stack:
a Write a program to implement the concept of Stack with Push, Pop, Display and Exit operations.
b Write a program to convert an infix expression to postfix and prefix conversion.
c Write a program to implement Tower of Hanoi problem.
4 Implement the following for Queue:
a Write a program to implement the concept of Queue with Insert, Delete, Display and Exit operations.
b Write a program to implement the concept of Circular Queue
c Write a program to implement the concept of Deque.
5 Implement the following sorting techniques:
a Write a program to implement bubble sort.
b Write a program to implement selection sort.
c Write a program to implement insertion sort.
6 Implement the following data structure techniques:
a Write a program to implement merge sort.
b Write a program to search the element using sequential search.
c Write a program to search the element using binary search.
7 Implement the following data structure techniques:
a Write a program to create the tree and display the elements.
b Write a program to construct the binary tree.
c Write a program for inorder, postorder and preorder traversal of tree
8 Implement the following data structure techniques:
a Write a program to insert the element into maximum heap.
b Write a program to insert the element into minimum heap.
9 Implement the following data structure techniques:
a Write a program to implement the collision technique.
b Write a program to implement the concept of linear probing.
10 Implement the following data structure techniques:
a Write a program to generate the adjacency matrix.
b Write a program for shortest path diagram.

Data Structures Reference Books

Title A Simplified Approach to Data Structures
Authors Lalit Goyal, Vishal Goyal, Pawan Kumar
Publisher SPD
Edition 1st
Year 2014
Download Here
Title An Introduction to Data Structure with Applications
Authors Jean – Paul Tremblay and Paul Sorenson
Publisher Tata MacGraw Hill
Edition 2nd
Year 2007
Download Here
Title Data Structure and Algorithm
Authors Maria Rukadikar
Publisher SPD
Edition 1st
Year 2017
Download Here
Title Schaum’s Outlines Data structure
Authors Seymour Lipschutz
Publisher Tata McGraw Hill
Edition 2nd
Year 2005
Download Here
Title Data structure – A Pseudocode Approach with C
Authors AM Tanenbaum, Y Langsam and MJ Augustein
Publisher Prentice Hall India
Edition 2nd
Year 2006
Download Here
Title Data structure and Algorithm Analysis in C
Authors Weiss, Mark Allen
Publisher Addison Wesley
Edition 1st
Year 2006
Download Here