CS- 305 Data Structures

Unit I

Introduction: Basic Terminology, Data types and its classification, Algorithm complexity notations

like big Oh,􀀀,􀀀. Array Definition, Representation and Analysis of Arrays, Single and

Multidimensional Arrays, Address calculation, Array as Parameters, Ordered List and operations,

Sparse Matrices, Storage pools, Garbage collection. Recursion-definition and processes, simulating

recursion, Backtracking, Recursive algorithms, Tail recursion, Removal of recursion. Tower of Hanoi

Problem.

UNIT II

Stack, Array Implementation of stack, Linked Representation of Stack, Application of stack:

Conversion of Infix to Prefix and Postfix Expressions and Expression evaluation, Queue, Array and

linked implementation of queues, Circular queues, D-queues and Priority Queues. Linked list,

Implementation of Singly Linked List, Two-way Header List, Doubly linked list, Linked List in Array.

Generalized linked list, Application: Garbage collection and compaction, Polynomial Arithmetic.

UNIT III

Trees: Basic terminology, Binary Trees, , algebraic Expressions, Complete Binary Tree,

Extended Binary Trees, Array and Linked Representation of Binary trees, Traversing Binary trees,

Threaded Binary trees, Binary Search Tree (BST ), AVL Trees, B-trees. Application: Algebraic

Expression, Huffman coding Algorithm.

UNIT IV

nternal and External sorting ,Insertion Sort, Bubble Sort, selection sort Quick Sort, Merge

Sort, Heap Sort, Radix sort, Searching & Hashing: Sequential search, binary search, Hash Table,

Hash Functions, Collision Resolution Strategies, Hash Table Implementation. Symbol Table, Static

tree table, Dynamic Tree table.

Unit V

Graphs: Introduction, Sequential Representations of Graphs, Adjacency Matrices, Traversal,

Connected Component and Spanning Trees, Minimum Cost Spanning Trees.

Reference:

1. R. Kruse et al, “Data Structures and Program Design in C”, Pearson Education Asia, Delhi-2002

2. ISRD Group; Data structures using C; TMH

3. Lipschutz; Data structure (Schaum); TMH

4. Horowitz and Sahani, “Fundamentals of data Structures”, Galgotia Publication Pvt. Ltd., N Delhi.

A. M. Tenenbaum, “Data Structures using C & C++”, Prentice-Hall of India Pvt. Ltd., New Delhi.

5. Data Structures Trembley and Sorenson, TMH Publications

6. Pai; Data structure and algorithm; TMH

7. Introduction to Algorithm- Corman, AWL

List of Experiments (expandable):

Programs in C relating to different theory units.