Data Structure HandWritten Notes
At the end of course , the student will be able to understand
CO 1 Describe how arrays, linked lists, stacks, queues, trees, and graphs are represented in memory,
used by the algorithms and their common applications.
CO 2 Discuss the computational efficiency of the sorting and searching algorithms.
CO 3 Implementation of Trees and Graphs and perform various operations on these data structure.
CO 4 Understanding the concept of recursion, application of recursion and its implementation and
removal of recursion.
CO 5 Identify the alternative implementations of data structures with respect to its performance to
solve a real world problem
Unit-I Introduction: Basic Terminology, Elementary Data Organization, Built in Data Types in C.
Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big
Oh, Big Theta and Big Omega, Time-Space trade-off. Abstract Data Types (ADT)
Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major
Order, and Column Major Order, Derivation of Index Formulae for 1-D,2-D,3-D and n-D Array
Application of arrays, Sparse Matrices and their representations.
Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly
Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal,
Polynomial Representation and Addition Subtraction & Multiplications of Single variable & Two
Unit-II Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked
Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of
postfix expression, Iteration and Recursion- Principles of recursion, Tail recursion, Removal of
recursion Problem solving using iteration and recursion with examples such as binary search,
Fibonacci numbers, and Hanoi towers. Tradeoffs between iteration and recursion.
Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and
linked implementation of queues in C, Dequeue and Priority Queue
Unit-III Searching: Concept of Searching, Sequential search, Index Sequential Search, Binary Search.
Concept of Hashing & Collision resolution Techniques used in Hashing. Sorting: Insertion Sort,
Selection, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort
Unit-IV Graphs: Terminology used with Graph, Data Structure for Graph Representations: Adjacency
Matrices, Adjacency List, Adjacency. Graph Traversal: Depth First Search and Breadth First
Search, Connected Component, Spanning Trees, Minimum Cost Spanning Trees: Prims and
Kruskal algorithm. Transitive Closure and Shortest Path algorithm: Warshal Algorithm and
Unit-V Trees: Basic terminology used with Tree, Binary Trees, Binary Tree Representation: Array
Representation and Pointer(Linked List) Representation, Binary Search Tree, Strictly Binary Tree
,Complete Binary Tree . A Extended Binary Trees, Tree Traversal algorithms: Inorder, Preorder
and Postorder, Constructing Binary Tree from given Tree Traversal, Operation of Insertation ,
Deletion, Searching & Modification of data in Binary Search . Threaded Binary trees, Traversing
Threaded Binary trees. Huffman coding using Binary Tree. Concept & Basic Operations for AVL
Tree , B Tree & Binary Heaps