DS SYLLABUS

 UNIT – I Introduction to C++ and Algorithms: Object oriented Design, Data Abstraction and

Encapsulation, Basics of C++: Program organization in C++, Input/output in C++, Classes

and Constructors, Access Modifiers, Dynamic Memory Allocation in C++, Templates in

C++, Exception Handling. Algorithms: Introduction, Algorithm Specifications, Recursive

Algorithms, Performance Analysis of an algorithm- Time and Space Complexity, Asymptotic

Notations.

UNIT – II Arrays: Abstract Data Types and the C++ Class, Array as an Abstract Data Type,

Polynomial Abstract Data Type, Sparse Matrices, Representation of Arrays, String Abstract

Data Type. Stacks and Queues: Templates in C++, Stack Abstract Data Type, Queue Abstract

Data type, Sub typing and Inheritance in C++, Evaluation of Expressions.

UNIT – III Linked Lists: Singly Linked Lists and Chains, Representing Chains in C++,

Template Class Chain, Circular Lists, Available Space Lists, Linked Stacks and Queues,

Polynomials, Doubly Linked Lists. Hashing: Static Hashing, Hash Tables, Hash Functions,

Overflow Handling, Theoretical Evaluation of Overflow Techniques

UNIT – IV Trees: Introduction, Binary Trees, Binary Tree Traversal and Tree Iterators,

Copying Binary Trees, Threaded Binary Trees, Heaps, Efficient Binary Search Trees:

AVLTrees.

UNIT – V Sorting and Searching: Insertion sort, Quick sort, Best computing time for

Sorting, Merge sort, Heap sort, shell sort, Sorting on Several Keys, List and Table Sorts,

Summary of Internal Sorting, Linear and Binary Search algorithms Graphs: Graph Abstract

Data Type, Elementary Graph operations (DFS and BFS), Minimum Cost Spanning Trees

(Prim‘s and Kruskal‘s Algorithms).