SECOND YEAR

BCS3B04 – Data Structures Using C

Course Number: 16

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

Objective

Prerequisites

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

• Seymour Lipschutz, “Data Structures”, Tata McGraw- Hill Publishing Company Limited, Schaum‟s Outlines, New Delhi.
• YedidyanLangsam, Moshe J. Augenstein, and Aaron M. Tenenbaum, “Data Structures Using C”, Pearson Education., New Delhi.
• Horowitz and Sahani, “Fundamentals of data Structures”, Galgotia Publication Pvt. Ltd., NewDelhi.

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.