Course Overview:
Contact Hours per Week: 7 (3T + 4L)
Number of Credits: 3
Number of Contact Hours: 112 Hrs.
Course Evaluation: Internal – 15 Marks + External – 60 Marks
Course Summary:
- This course provides an in-depth understanding of data structures, fundamental to computer science and essential for developing efficient algorithms.
- Students will learn how to organize, manage, and store data for efficient access and modification.
- The course covers a range of data structures, their applications, and their role in solving computational problems.
Course Objective:
- Understand the core concepts of various data structures.
- Implement and manipulate data structures in C programming language .
- Analyze the performance of different data structures in terms of time and space complexity.
- Choose the appropriate data structure for a given problem.
- Apply data structures in real-world applications and algorithm development.
Course Outcome:
- CO1 To be familiar with fundamental data structures and with the manner in which these data structures can
best be implemented; become accustomed to the description of algorithms in both functional and proceduralstyles - CO2 To have knowledge of complexity of basic operations like insert, delete, search on these data structures.
- CO3 Ability to choose a data structure to suitably model any data used in computer applications.
- CO4 Design programs using various data structures including hash tables, Binary and general search trees, graphs etc.
- CO5 Implement and know the applications of algorithms for sorting, pattern matching
Course Outline:
UNIT I [9 T + 7L]
Introduction: Elementary data organization, Data Structure definition, Data type vs. data structure, Categories of data
structures, Data structure operations, Applications of data structures, Algorithms complexity and time-space trade off,
Big-O notation.
Strings: Introduction, strings, String operations, Pattern matching algorithms
UNIT II [10 T + 14 L]
Arrays: Introduction, Linear arrays, Representation of linear array in memory, Traversal, Insertions, Deletion in an
array, Multidimensional arrays, Parallel arrays, sparse matrix.
Linked List: Introduction, Array vs. linked list, Representation of linked lists in memory, Traversal, Insertion,
Deletion, Searching in a linked list, Header linked list, Circular linked list, Two-way linked list, Applications of linked
lists, Algorithm of insertion/deletion in Singly Linked List (SLL).
UNIT III [10 T + 14 L]
Stack: primitive operation on stack, algorithms for push and pop. Representation of Stack as Linked List and array,
Stacks applications: polish notation, recursion.
Introduction to queues: Primitive Operations on the Queues, Circular queue, Priority queue, Representation of Queues
as Linked List and array, Applications of queue: Algorithm on insertion and deletion in simple queue and circular
queue.
UNIT IV [10 T + 14 L]
Trees - Basic Terminology, representation, Binary Trees, Tree Representations using Array & Linked List, Basic
operation on Binary tree: insertion, deletion and processing, Traversal of binary trees: In order, Pre-order & post-order,
Algorithm of tree traversal with and without recursion, Binary Search Tree, Operation on Binary Search Tree,
expression trees, implementation using pointers, applications.
UNIT V [10 T + 14 L]
Introduction to graphs, Definition, Terminology, Directed, Undirected & Weighted graph, Representation of graphs,
graph traversal- depth-first and breadth-first traversal of graphs, applications.
Searching: sequential searching, binary searching, Hashing – linear hashing, hash functions, hash table searching;
Sorting: Quick Sort, Exchange sort, Selection sort and Insertion sort.
Text Books :
1. Seymour Lipschutz, “Data Structures”, Tata McGraw- Hill Publishing Company Limited, Schaum’s Outlines, New Delhi.
2. Yedidyan Langsam, Moshe J. Augenstein, and Aaron M. Tenenbaum, “Data Structures Using C”, Pearson
Education., New Delhi.
3. Horowitz and Sahani, “Fundamentals of data Structures”, Galgotia Publication Pvt. Ltd., New Delhi.
Reference Books
1. Trembley, J.P. And Sorenson P.G., “An Introduction to Data Structures With Applications”, Mcgraw- Hill
International Student Edition, New York.
2. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”, Addison- Wesley, (An Imprint of Pearson Education), Mexico City.
3. A.K.Sharma, Data Structures Using C, Pearson, Second edition, 2011
4. Nair A.S., Makhalekshmi, Data Structures in C, PHI, Third edition 2011.
5. R. Kruse etal, “Data Structures and Program Design in C”, Pearson Education Asia, Delhi-2002
6. K Loudon, “Mastering Algorithms with C”, Shroff Publisher & Distributors Pvt. Ltd.
- Teacher: JENCY J FACULTY