CS302ES: DATA STRUCTURES THROUGH C++
B.Tech. II Year I Sem. L T P C
4 0 0 4

---

Course Objectives:

• To understand the basic concepts such as Abstract Data Types, Linear and Non Linear Data structures.
• To understand the notations used to analyze the Performance of algorithms.
• To understand the behavior of data structures such as stacks, queues, trees, hash tables, search trees, Graphs and their representations.
• To choose an appropriate data structure for a specified application.
• To understand and analyze various searching and sorting algorithms.
• To learn to implement ADTs such as lists, stacks, queues, trees, graphs, search trees in C++ to solve problems.

Course Outcomes:

• Ability to choose appropriate data structures to represent data items in real world problems.
• Ability to analyze the time and space complexities of algorithms.
• Ability to design programs using a variety of data structures such as stacks, queues, hash tables, binary trees, search trees, heaps, graphs, and B-trees.
• Able to analyze and implement various kinds of searching and sorting techniques.

UNIT - I

C++ Programming Concepts: Review of C, input and output in C++, functions in C++- value parameters, reference parameters, Parameter passing, function overloading, function templates, Exceptions-throwing an exception and handling an exception, arrays, pointers, new and delete operators, class and object, access specifiers , friend functions, constructors and destructor, Operator overloading, class templates, Inheritance and Polymorphism.

Basic Concepts - Data objects and Structures, Algorithm Specification-Introduction, Recursive algorithms, Data Abstraction, Performance analysis- time complexity and space complexity, Asymptotic Notation-Big O, Omega and Theta notations, Complexity Analysis Examples, Introduction to Linear and Non Linear data structures.

UNIT - II

Representation of single, two dimensional arrays, sparse matrices-array and linked representations.

Linear list ADT-array representation and linked representation, Singly Linked Lists- Operations-Insertion, Deletion, Circularly linked lists-Operations for Circularly linked lists, Doubly Linked Lists- Operations- Insertion, Deletion.

Stack ADT, definition, array and linked implementations, applications-infix to postfix conversion, Postfix expression evaluation, recursion implementation, Queue ADT, definition, array and linked Implementations, Circular queues-Insertion and deletion operations.

UNIT - III

Trees – definition, terminology, Binary trees-definition, Properties of Binary Trees, Binary Tree ADT, representation of Binary Trees-array and linked representations, Binary Tree traversals, Threaded binary trees, Priority Queues –Definition and applications, Max Priority Queue ADT-implementation-Max Heap-Definition, Insertion into a Max Heap, Deletion from a Max Heap.

UNIT - IV

Searching - Linear Search, Binary Search, Hashing-Introduction, hash tables, hash functions, Overflow Handling, Comparison of Searching methods.

Sorting-Insertion Sort, Selection Sort, Radix Sort, Quick sort, Heap Sort, Merge sort, Comparison of Sorting methods.

UNIT - V

Graphs–Definitions, Terminology, Applications and more definitions, Properties, Graph ADT, Graph Representations- Adjacency matrix, Adjacency lists, Graph Search methods - DFS and BFS, Complexity analysis,

Search Trees-Binary Search Tree ADT, Definition, Operations- Searching, Insertion and Deletion, Balanced search trees-AVL Trees-Definition and Examples only, B-Trees- Definition and Examples only, Red-Black Trees-Definitions and Examples only, Comparison of Search Trees.

TEXT BOOKS:

1. Data structures, Algorithms and Applications in C++, 2nd Edition, Sartaj Sahni, Universities Press.
2. Data structures and Algorithms in C++, Adam Drozdek, 4th edition, Cengage learning.

REFERENCE BOOKS:

1. Data structures with C++, J. Hubbard, Schaum’s outlines, TMH.
2. Data structures and Algorithms in C++, M.T. Goodrich, R. Tamassia and D. Mount, Wiley India.
3. Data structures and Algorithm Analysis in C++, 3rd edition, M. A. Weiss, Pearson.
4. Classic Data Structures, D. Samanta, 2nd edition, PHI.