CA-C3T: DATA STRUCTURES
Total Teaching Hours: 48 No. of Hours / Week: 03
UNIT-I [12 Hours]
Introduction and Overview: Definition, Elementary data organization, Data Structures, data Structures
operations, Abstract data types, algorithms complexity, time-space trade off. Preliminaries: Mathematical
notations and functions, Algorithmic notations, control structures, Complexity of algorithms, asymptotic
notations for complexity of algorithms. Arrays: Definition, Linear arrays, arrays as ADT, Representation of
Linear Arrays in Memory,Traversing Linear arrays, Inserting and deleting, Multi-dimensional arrays,
Matrices and Sparse matrices.
UNIT-II [12 Hours]
Linked list: Definition, Representation of Singly Linked List in memory,Traversing a Singly linked list,
Searching in a Singly linked list, Memory allocation, Garbage collection, Insertion into a singly linked list,
Deletion from a singly linked list; Doubly linked list, Header linked list, Circular linked list. Stacks:
Definition, Array representation of stacks, Linked representation of stacks, Stack as ADT, Arithmetic
Expressions: Polish Notation, Conversion of infix expression to postfix expression, Evaluation of Post fix
expression, Application of Stacks, Recursion, Towers of Hanoi, Implementation of recursive procedures by
stack. Queues: Definition, Array representation of queue, Linked list representation of queues. Types of
queue: Simple queue, Circular queue, Double-ended queue, Priority queue, Operations on Queues,
Applications of queues.
UNIT-III [12 Hours]
Binary Trees: Definitions, Tree Search, Traversal of Binary Tree, Tree Sort, Building a Binary Search Tree,
Height Balance: AVL Trees, Contiguous Representation of Binary Trees: Heaps, Lexicographic Search Trees:
Tries, External Searching: B-Trees, Applications of Trees. Graphs: Mathematical Back ground, Computer
Representation, Graph Traversal, Topological Sorting
UNIT-IV [12 Hours]
Searching: Introduction and Notation, Sequential Search, Binary Search, Comparison of Methods. Sorting:
Introduction and Notation, Insertion Sort, Selection Sort, Shell Sort, Divide And Conquer, Merge sort for
Linked List, Quick sort for Contiguous List. Hashing: Sparse Tables, Choosing a Hash function, Collision
Resolution with Open Addressing, Collision Resolution by Chaining.
Text Books:
1. Seymour Lipschutz, “Data Structures with C”, Schaum’s outLines, Tata Mc Graw Hill, 2011.
2. Robert Kruse, C.L.Tondo, Bruce Leung,Shashi Mogalla,“Data Structures and Program Design using C”,
Pearson Education, 2009.
ReferenceBooks:
1. Mark Allen Weiss,“ Data Structures and Algorithm Analysis in C”, Second Edition, Pearson Education,
2013.
2. Forouzan,“A Structured Programming Approach using C”,2 nd Edition, Cengage LearningIndia,2008
