**Data Structures**

Subject Code | Subject Name | Credits | |||||||||||

MCA201 |
Data Structures |
04 |
|||||||||||

Subject
Code |
Subject Name | Teaching
Scheme |
Credits
Assigned |
||||||||||

Theory | Pract | Tut | Theory | TW | Tut. | Total | |||||||

MCA201 |
Data Structures |
04 |
— |
— |
04 |
— |
— |
04 |
|||||

Subject Code | Subject Name | Examination Scheme | |||||||||||

MCA 201 |
Data Structures |
Theory Marks | TW | Pract | Oral | Total | |||||||

Internal Assessment | End Semester Exam | ||||||||||||

Test1 (T1) | Test2 (T2) | Average of T1 & T2 | |||||||||||

20 | 20 | 20 | 80 | – | – | – | 100 | ||||||

## Pre-requisites:

Understanding of Algorithms

## Course Educational Objectives (CEO):

** **

CEO 1 |
To teach efficient storage mechanisms of data for an easy access. |

CEO 2 |
To design and implement various basic and advanced data structures. |

CEO 3 |
To introduce various techniques for representation of the data in the real world. |

** **

**Course Outcomes: At the end of the course, the students will be able to :**

** **

MCA201.1 |
Analyze and compute efficiency of various algorithms. |

MCA201.2 |
Effectively choose the data structure that efficiently model the information in a problem |

MCA201.3 |
Describe how Linear data structures are represented in memory and used by algorithms and their applications |

MCA201.4 |
Identify the benefits of Non-linear Data Structures and their applications |

** **

** **

** **

** **

** **

** **

**Syllabus**

Sr |
Module |
Detailed Contents |
Hours |

1 |
Introduction to Data Structures & Algorithms |
Introduction of Data structures, Abstract Data Types,
Performance Analysis: Space Complexity, Time Complexity, Asymptotic Notations (Big O, Omega, Theta), Performance measurement, Divide and Conquer, Back Tracking Method, Dynamic programming |
4 |

2 |
Sorting and searching algorithms |
Bubble sort, Insertion sort, Radix Sort, Quick sort, Merge sort,
Heap sort, Selection sort, shell Sort, Linear Search, Sequential search, Binary search |
6 |

3 |
Hashing |
Different Hashing Techniques, Address calculation
Techniques, Common hashing functions, Collision resolution techniques: Linear probe, Quadratic probe, Key offset. Rehashing, Double hashing, Link list addressing. |
8 |

4 |
Linear Data Structures |
Stack Definition, Operations, Implementation of Stacks (Array and Linked list) and applications-Evaluation of postfix expression, Balancing of parenthesis
Queue: Definition, Operations, Implementation of simple queue (Array and Linked list) and applications of queue-BFS Types of queues: Circular, Double ended, Priority, Implementation using linked list Types of Linked List: Singly, Doubly and Circular Linked list Definition, Operations (Insert, delete, traverse, count, search ) Applications of Linked List: Polynomial Addition and Subtraction |
14 |

5 |
Non-linear Data Structures |
Tree Definition and concepts,
General Tree- Definition, Insertion and Deletion into general tree, Binary Tree- Definition, Insertion and Deletion into binary tree, Traversal of a binary tree, Reconstruction of a binary tree from traversal, Conversion of general tree into binary tree, Huffman tree, Expression tree, Binary threaded three Binary Search Tree- Definition, Operation, Implementation AVL tree- Definition, AVL tree rotation with examples, Heaps-Definition, Operations (insertion, delete, build) M way Tree- Introduction, B tree-definition and examples and B* |
14 |

6 |
Graphs |
Definition, Types, Operations, Representation, Networks,
Traversals of graph, Minimum spanning tree, Kruskal‟s Algorithm, Prim‟s Algorithm, Warshall‟s Algorithm,Shortest path algorithm-dijsktra‟s algorithm |
6 |

** **

**Reference Books**

- Richard F Gilberg Behrouz A Forouzan , “Data Structure A Pseudocode Approach with C“. Second edition

- Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein, “Introduction to ALGORITHMS”, PHI, India Second Edition.
- Shaum‟s Outlines Data Structure Seymour Lipschutz TMH
- Michael T.Goodrich “Data Structures and Algorithms in C++-“ Wiley Publications

**Theory paper **will be of **80 **marks. **Internal **assessment will be of **20 **marks, which will be the average of two tests (T1 and T2) of 20 marks each.