MCA 203 : Data Structures Using C++

Lectures: 4 Periods/Week Sessional Marks: 30
University Exam: 3 Hours University Examination Marks: 70


UNIT-I
Software Engineering Principles and C++ Classes
Classes: Variable - Accessing Class members - Operators - Functions and Classes - Reference parameters and Class Objects - Implementation of member function - Constructors - Destructors ; Data Abstraction, Classes and ADT- Information Hiding.
Pointers and Array based Lists
Pointer Data types and Pointer variables: Declaring Pointer Variables - Address of Operator - Dereferencing Operator - Classes, Structures and Pointer Variables - Initializing Pointer Variables - Dynamic Variables - Operators on Pointer Variables.

UNIT-II
Linked Lists
Linked List - Properties - Item Insertion and Deletion - Building a Linked List - Linked List as an ADT - Ordered Linked Lists - Doubly Linked Lists - Linked Lists with header and trailer nodes - Circular Linked Lists.
Recursion
Recursive Definitions - Problem solving using recursion - Recursion or iteration - Recursion and Backtracking : n- Queens Puzzle.
Search Algorithms
Search Algorithms: Sequential - Binary search - Performance of binary search - insertion into ordered list; Hashing : Hash functions - Collision Resolution - Hashing : Implementation using Quadratic Probing - Collision Resolution : Chaining.

UNIT-III
Stacks
Stack operations - Implementation of stacks as arrays - Linked implementation of stacks - Application of stacks.
Queues
Queues : Queue operations - Implementation of Queues as arrays ; Linked implementation of Queues ; PriorityQueue ; Application of Queues.
Sorting Algorithms
Selection Sort - Insertion Sort - Quick Sort - Merge Sort - Heap Sort.

UNIT-IV
Trees
Binary Trees - Binary Tree Traversal - Binary Search Tree - Nonrecursive Binary Tree Traversal Algorithms - AVL Trees.
Graphs
Graphs : Graph Definitions and Notations - Graph Representation - Operations on graphs - Graph as ADT - Graph Traversals - shortest path Algorithm - Minimal Spanning Tree.

Prescribed Book

  1. D.S.Malik , '' Data Structures using C++ '' , Cengage Learning India Edition (2008).
    (Chapters 1, 3, 5, 6, 7, 8, 9, 10, 11 and 12.)
Reference Books
  1. Mark Allen Weiss , ''Data structures and Algorithem Analysis in C++'' , Third Edition , Pearson Education (2008).
  2. Adam Drozdek , ''Data Structures and Algorithms in C++'' , Cengage Learning , India Edition .