Data Structures Using C

Program Class: Certificate/ B.SC.

Year: First

Semester: Second

Subject: Computer Science

                Course Title: Data Structure Using C

Course Learning Outcomes: To provide the knowledge of basic data structures and their implementation. To understand the importance of data structures in context of writing efficient programs. To develop skills to apply appropriate data structures in problem solving.

Credits: 4

Core Compulsory

Max. Marks: –25+75

Min. Passing Marks: 33

Unit

Topics

I

Introduction to Data Structures: Time and Space Complexities, Asymptotic Notation, Recurrence Relations, Abstract data types, Sparse Matrices, Recursion definition and processes, Tower of Hanoi, Stacks –Operations: Push & Pop, Array Representation of Stack, Linked Representation of stack, Stack applications, Queues- Array and Linked representation and Implementation of queues, Operations on Queues.

II

Linked List: Representation and Implementation of Singly Linked Lists, Insertion, Deletion and Searching operation, Two-way Traversing and Searching of Linked Lists.

III

Trees and Binary Search Trees: Basic Terminology, Binary trees, Traversing of Binary trees, Binary Search Trees, Definition, Implementation, Insertion and Deletion in BST Operation-Searching, B-Trees, B+ Trees, AVL Trees, Definition, Height of an AVL Trees,

IV

Sorting and Searching: Insertion Sort, Bubble Sort, Quick Sort, Merge Sort, Heap Sort, Sequential Search, binary search, Comparison and Analysis, Hash Table, Hash Functions, Collision Resolution Strategies, Hash Table Implementation.

V

Graphs: Terminology & Representation, Graphs & Multi-graphs, Directed Graphs, Sequential Representation of Graphs, Adjacency Matrices, Traversal, Connected Component and Spanning Trees, Minimum Cost Spanning Trees.